The Redei--Berge symmetric function of a directed graph

Abstract

Let $D=\left(V,A\right)$ be a digraph with $n$ vertices, where each arc $a\in A$ is a pair $\left(u,v\right)$ of two vertices. We study the \emph{Redei--Berge symmetric function} $U_D$, defined as the quasisymmetric function% \[ \sum L_{\operatorname*{Des}\left( w,D\right) ,\ n}\in\operatorname*{QSym}. \] Here, the sum ranges over all lists $w=\left(w_1,w_2,\dots ,w_n\right)$ that contain each vertex of $D$ exactly once, and the corresponding addend is% \[ L_{\operatorname*{Des}\left( w,D\right) ,\ n}:=\sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq i_{n};\ı_{p}<i_{p+1}\text{ for each }p\text{ satisfying }\left( w_{p},w_{p+1}\right) \in A}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}% \] (an instance of Gessel's fundamental quasisymmetric functions). While $U_D$ is a specialization of Chow's path-cycle symmetric function, which has been studied before, we prove some new formulas that express $U_D$ in terms of the power-sum symmetric functions. We show that $U_D$ is always $p$-integral, and furthermore is $p$-positive whenever $D$ has no $2$-cycles. When $D$ is a tournament, $U_D$ can be written as a polynomial in $p_1,2p_3,2p_5,2p_7,\dots$ with nonnegative integer coefficients. By specializing these results, we obtain the famous theorems of Redei and Berge on the number of Hamiltonian paths in digraphs and tournaments, as well as a modulo-$4$ refinement of Redei's theorem.

66 pages. Draft (proofs in Sections 3-8 are still somewhat of an outline), posted for reference. Detailed version (for Section 2) as ancillary file