The Redei--Berge symmetric function of a directed graph

arXiv2307.05569MaRDI QIDQ6443372FDOQ6443372

Authors: Darij Grinberg, Richard P. Stanley 

Publication date: 10 July 2023

Abstract: Let $D=left(V,Aight)$ be a digraph with $n$ vertices, where each arc $ainA$ is a pair $left(u,vight)$ 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 ight) , n}inoperatorname*{QSym}. ] Here, the sum ranges over all lists $w=left(w_1,w_2,ldots,w_{n}ight)$ that contain each vertex of $D$ exactly once, and the corresponding addend is% [ L_{operatorname*{Des}left( w,D ight) , n}:=sum_{substack{i_{1}leq i_{2}leqcdotsleq i_{n};\i_{p}<i_{p+1} ext{ for each }p ext{ satisfying }left( w_{p},w_{p+1} ight) 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,ldots$ 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.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Symmetric functions and generalizations (05E05) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30)

This page was built for publication: The Redei--Berge symmetric function of a directed graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443372)