The Redei--Berge symmetric function of a directed graph

Let $D=(V,A)$ be a digraph with $n$ vertices, where each arc $a\in A$ is a pair $(u,v)$ of two vertices. We study the \emph{Redei–Berge symmetric function} $U_D$, defined as the quasisymmetric function% $$\sum L_{\mathrm{Des}(w,D),n}\in \mathrm{QSym}\mathrm{.}$$ Here, the sum ranges over all lists $w=(w_1,w_2,\dots ,w_n)$ that contain each vertex of $D$ exactly once, and the corresponding addend is% $$L_{\mathrm{Des}(w,D),n}:=\sum _{\begin{array}{c}{i}_1\le i_2\le \cdots \le i_n;{\text{ı}}_p<i_{p+1}\text{ for each }p\text{ satisfying }(w_p,w_{p+1})\in A\end{array}}{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.