Appears in collection : Combinatorics and Arithmetic for Physics: special days 2023

In 1934, Laszlo Redei observed a peculiar property of tournaments (directed graphs that have an arc between every pair of distinct vertices): Each tournament has an odd number of Hamiltonian paths. In 1996, Chow introduced the “path-cycle symmetric function” of a directed graph, a symmetric function in two sets of arguments, which was later used in rook theory. We study Chow’s symmetric function in the case when the y-variables are 0. In this case, we give new nontrivial expansions of the function in terms of the power-sum basis; in particular, we find that it is p-positive as long as the directed graph has no 2-cycles. We use our expansions to reprove Redei’s theorem and refine it to a mod-4 congruence. Joint work with with Richard P. Stanley.