Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
The Redei--Berge symmetric function of a directed graph
arXiv.org
10 Jul 2023
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},\ldots ,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};\\i_{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},\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.
Metrics
4 Record Views
Details
- Title
- The Redei--Berge symmetric function of a directed graph
- Creators
- Darij GrinbergRichard P Stanley
- Publication Details
- arXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021862234904721