Darij Grinberg: The Redei–Berge symmetric function of a directed graph

ABSTRACT: 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.

This is joint work with Richard P. Stanley.