The Redei-Berge Symmetric Function of a Directed Graph

Explore the fascinating world of graph theory and symmetric functions in this 44-minute lecture by Darij Grinberg from the Department of Mathematics at Drexel University. Delve into the intriguing property of tournaments observed by Laszlo Redei in 1934, where each tournament has an odd number of Hamiltonian paths. Examine Chow's path-cycle symmetric function of directed graphs, introduced in 1996, and its applications in rook theory. Investigate new nontrivial expansions of this function in terms of the power-sum basis when the y-variables are set to 0. Discover the p-positivity of the function for directed graphs without 2-cycles. Learn how these expansions lead to a reproof of Redei's theorem and its refinement to a mod-4 congruence. Gain insights into this joint work with Richard P. Stanley, presented at the Institut des Hautes Etudes Scientifiques (IHES).