The Redei–Berge symmetric functions page 0

# The Redei–Berge symmetric function of a directed graph

Darij Grinberg and Richard P. Stanley

(draft (Sections 1–2 finished, 3–8 outlined), July 9, 2023)

###### Abstract

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
_Redei–Berge symmetric function_ $U_{D}$, defined as the quasisymmetric
function

$\sum\limits 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\limits_{\begin{subarray}{c}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\end{subarray}}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.

Keywords: directed graph, symmetric function, tournament, Hamiltonian path,
power sum symmetric function.

Mathematics Subject Classification 2020: 05A05, 05A19, 05E05, 05C30.

###### Contents

  1. 1 Definitions and the main theorems
    1. 1.1 Digraphs, $V$-listings and $D$-descents
    2. 1.2 Quasisymmetric functions
    3. 1.3 The Redei–Berge symmetric function
    4. 1.4 Arcs and cyclic arcs
    5. 1.5 Permutations and their cycles
    6. 1.6 $D$-paths and $D$-cycles
    7. 1.7 The sets $\mathfrak{S}_{V}\left(D\right)$ and $\mathfrak{S}_{V}\left(D,\overline{D}\right)$
    8. 1.8 Formulas for $U_{D}$
      1. 1.8.1 The power-sum symmetric functions
      2. 1.8.2 The first main theorem: general digraphs
      3. 1.8.3 The second main theorem: tournaments
      4. 1.8.4 The third main theorem: digraphs with no $2$-cycles
  2. 2 Proof of Theorem 1.30
    1. 2.1 Basic conventions
    2. 2.2 Path covers and linear sets
    3. 2.3 The arrow set of a permutation
    4. 2.4 Counting hamps by inclusion-exclusion
    5. 2.5 Level decomposition and maps $f$ satisfying $f\circ\sigma=f$
    6. 2.6 An alternating sum involving permutations $\sigma$ with $f\circ\sigma=f$
    7. 2.7 $\left(f,D\right)$-friendly $V$-listings
    8. 2.8 A bit of Pólya counting
    9. 2.9 A final alternating sum
    10. 2.10 A trivial lemma
    11. 2.11 The proof of Theorem 1.30
  3. 3 Proof of Theorem 1.38
  4. 4 Proving the corollaries
  5. 5 Proof of Theorem 1.40
  6. 6 Recovering Redei’s and Berge’s theorems
  7. 7 A modulo-$4$ improvement of Redei’s theorem
  8. 8 The antipode and the omega involution
  9. 9 A multiparameter deformation

##  1 Definitions and the main theorems

We begin with introducing the notations, some of which come from [EC2sup22,
Problem 120]. We use standard notations as defined, e.g., in [Stanle01,
Chapter 7] and [GriRei20, Chapters 2 and 5].

###  1.1 Digraphs, $V$-listings and $D$-descents

We let $\mathbb{N}:=\left\\{0,1,2,\ldots\right\\}$ and
$\mathbb{P}:=\left\\{1,2,3,\ldots\right\\}$. We set
$\left[n\right]:=\left\\{1,2,\ldots,n\right\\}$ for each $n\in\mathbb{Z}$.
(This set $\left[n\right]$ is empty if $n\leq 0$.)

The words “list” and “tuple” will be used interchangeably, and will always
mean finite ordered tuples.

We shall next introduce some basic notations regarding digraphs (i.e.,
directed graphs):

######  Definition 1.1.

A _digraph_ means a pair $\left(V,A\right)$, where $V$ is a finite set and
where $A$ is a subset of $V\times V$. The elements of $V$ are called the
_vertices_ of this digraph, and the elements of $A$ are called the _arcs_ of
this digraph. For any further notations, we refer to standard literature (the
definitions in [Grinbe17, §1.1-§1.2] should suffice) and common sense. (Our
digraphs are allowed to have loops, but this has no effect on what follows.)

######  Definition 1.2.

Let $D=\left(V,A\right)$ be a digraph. Then, the digraph $\left(V,\
\left(V\times V\right)\setminus A\right)$ will be denoted by $\overline{D}$
and called the _complement_ of the digraph $D$. Its arcs will be called the
_non-arcs_ of $D$ (since they are precisely the pairs $\left(u,v\right)\in
V\times V$ that are not arcs of $D$).

######  Example 1.3.

If $D$ is the digraph

$\left(\left\\{1,2,3\right\\},\ \left\\{\left(1,2\right),\ \left(2,2\right),\
\left(3,3\right)\right\\}\right),$

then its complement $\overline{D}$ is the digraph

$\left(\left\\{1,2,3\right\\},\ \left\\{\left(1,1\right),\ \left(1,3\right),\
\left(2,1\right),\ \left(2,3\right),\ \left(3,1\right),\
\left(3,2\right)\right\\}\right).$

Here are the two digraphs, drawn side by side:

$\begin{tabular}[c]{|c|c|}\hline\cr$\leavevmode\hbox to134.13pt{\vbox
to125.59pt{\pgfpicture\makeatletter\hbox{\hskip
59.95096pt\lower-62.79597pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-59.75096pt}{-62.59598pt}\pgfsys@moveto{-59.75096pt}{-62.59598pt}\pgfsys@lineto{-59.75096pt}{62.59598pt}\pgfsys@lineto{73.97734pt}{62.59598pt}\pgfsys@lineto{73.97734pt}{-62.59598pt}\pgfsys@closepath\pgfsys@moveto{73.97734pt}{62.59598pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{51.46503pt}{0.0pt}\pgfsys@curveto{51.46503pt}{4.85237pt}{47.53151pt}{8.78589pt}{42.67914pt}{8.78589pt}\pgfsys@curveto{37.82677pt}{8.78589pt}{33.89325pt}{4.85237pt}{33.89325pt}{0.0pt}\pgfsys@curveto{33.89325pt}{-4.85237pt}{37.82677pt}{-8.78589pt}{42.67914pt}{-8.78589pt}\pgfsys@curveto{47.53151pt}{-8.78589pt}{51.46503pt}{-4.85237pt}{51.46503pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{42.67914pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{40.17914pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-12.55368pt}{36.96132pt}\pgfsys@curveto{-12.55368pt}{41.81369pt}{-16.4872pt}{45.74721pt}{-21.33957pt}{45.74721pt}\pgfsys@curveto{-26.19194pt}{45.74721pt}{-30.12546pt}{41.81369pt}{-30.12546pt}{36.96132pt}\pgfsys@curveto{-30.12546pt}{32.10895pt}{-26.19194pt}{28.17543pt}{-21.33957pt}{28.17543pt}\pgfsys@curveto{-16.4872pt}{28.17543pt}{-12.55368pt}{32.10895pt}{-12.55368pt}{36.96132pt}\pgfsys@closepath\pgfsys@moveto{-21.33957pt}{36.96132pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-23.83957pt}{33.7391pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-12.55368pt}{-36.96132pt}\pgfsys@curveto{-12.55368pt}{-32.10895pt}{-16.4872pt}{-28.17543pt}{-21.33957pt}{-28.17543pt}\pgfsys@curveto{-26.19194pt}{-28.17543pt}{-30.12546pt}{-32.10895pt}{-30.12546pt}{-36.96132pt}\pgfsys@curveto{-30.12546pt}{-41.81369pt}{-26.19194pt}{-45.74721pt}{-21.33957pt}{-45.74721pt}\pgfsys@curveto{-16.4872pt}{-45.74721pt}{-12.55368pt}{-41.81369pt}{-12.55368pt}{-36.96132pt}\pgfsys@closepath\pgfsys@moveto{-21.33957pt}{-36.96132pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-23.83957pt}{-40.18353pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$3$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@beginscope\pgfsys@invoke{ }
{{}}{}{{}}{}{{}}{}\hbox{\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{ }{}{{ {\pgfsys@beginscope
\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys@roundjoin{} {}{}{} {}{}{}
\pgfsys@moveto{-3.63998pt}{4.74835pt}\pgfsys@curveto{-2.97498pt}{1.8993pt}{-1.49307pt}{0.55397pt}{0.0pt}{0.0pt}\pgfsys@curveto{-1.49307pt}{-0.55397pt}{-2.97498pt}{-1.8993pt}{-3.63998pt}{-4.74835pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{34.72392pt}{4.59294pt}\pgfsys@lineto{-11.91226pt}{31.51839pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,1}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{
}\pgfsys@transformcm{-0.86603}{0.5}{-0.5}{-0.86603}{-12.64838pt}{31.94337pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}
{{}{}{{}}{}}{{}{}{{}}{}}{{}{}}{{}}
{{}{}{{}}{}}{{{}}{{}}}{{}}{{}{}{{}}{}}{{{}}{{}}}{{}}{}{{}}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{{{{{{}}{}{}{}{}{{}}}}}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-30.21245pt}{34.58385pt}\pgfsys@curveto{-44.54086pt}{30.74457pt}{-44.54086pt}{43.17807pt}{-32.82042pt}{40.0376pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,1}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{
}\pgfsys@transformcm{0.96593}{-0.25882}{0.25882}{0.96593}{-31.9994pt}{39.81761pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}
{{}{}{{}}{}}{{}{}{{}}{}}{{}{}}{{}}
{{}{}{{}}{}}{{{}}{{}}}{{}}{{}{}{{}}{}}{{{}}{{}}}{{}}{}{{}}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{{{{{{}}{}{}{}{}{{}}}}}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-30.21245pt}{-39.33879pt}\pgfsys@curveto{-44.54086pt}{-43.17807pt}{-44.54086pt}{-30.74457pt}{-32.82042pt}{-33.88504pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,1}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{
}\pgfsys@transformcm{0.96593}{-0.25882}{0.25882}{0.96593}{-31.9994pt}{-34.10503pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$&$\leavevmode\hbox
to134.13pt{\vbox to125.59pt{\pgfpicture\makeatletter\hbox{\hskip
59.95096pt\lower-62.79597pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-59.75096pt}{-62.59598pt}\pgfsys@moveto{-59.75096pt}{-62.59598pt}\pgfsys@lineto{-59.75096pt}{62.59598pt}\pgfsys@lineto{73.97734pt}{62.59598pt}\pgfsys@lineto{73.97734pt}{-62.59598pt}\pgfsys@closepath\pgfsys@moveto{73.97734pt}{62.59598pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{51.46503pt}{0.0pt}\pgfsys@curveto{51.46503pt}{4.85237pt}{47.53151pt}{8.78589pt}{42.67914pt}{8.78589pt}\pgfsys@curveto{37.82677pt}{8.78589pt}{33.89325pt}{4.85237pt}{33.89325pt}{0.0pt}\pgfsys@curveto{33.89325pt}{-4.85237pt}{37.82677pt}{-8.78589pt}{42.67914pt}{-8.78589pt}\pgfsys@curveto{47.53151pt}{-8.78589pt}{51.46503pt}{-4.85237pt}{51.46503pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{42.67914pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{40.17914pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-12.55368pt}{36.96132pt}\pgfsys@curveto{-12.55368pt}{41.81369pt}{-16.4872pt}{45.74721pt}{-21.33957pt}{45.74721pt}\pgfsys@curveto{-26.19194pt}{45.74721pt}{-30.12546pt}{41.81369pt}{-30.12546pt}{36.96132pt}\pgfsys@curveto{-30.12546pt}{32.10895pt}{-26.19194pt}{28.17543pt}{-21.33957pt}{28.17543pt}\pgfsys@curveto{-16.4872pt}{28.17543pt}{-12.55368pt}{32.10895pt}{-12.55368pt}{36.96132pt}\pgfsys@closepath\pgfsys@moveto{-21.33957pt}{36.96132pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-23.83957pt}{33.7391pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-12.55368pt}{-36.96132pt}\pgfsys@curveto{-12.55368pt}{-32.10895pt}{-16.4872pt}{-28.17543pt}{-21.33957pt}{-28.17543pt}\pgfsys@curveto{-26.19194pt}{-28.17543pt}{-30.12546pt}{-32.10895pt}{-30.12546pt}{-36.96132pt}\pgfsys@curveto{-30.12546pt}{-41.81369pt}{-26.19194pt}{-45.74721pt}{-21.33957pt}{-45.74721pt}\pgfsys@curveto{-16.4872pt}{-45.74721pt}{-12.55368pt}{-41.81369pt}{-12.55368pt}{-36.96132pt}\pgfsys@closepath\pgfsys@moveto{-21.33957pt}{-36.96132pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-23.83957pt}{-40.18353pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$3$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@beginscope\pgfsys@invoke{ }
{{}}{}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}
{{}{}{{}}{}}{{}{}{{}}{}}{{}{}}{{}}
{{}{}{{}}{}}{{{}}{{}}}{{}}{{}{}{{}}{}}{{{}}{{}}}{{}}{}{{}}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{{{{{{}}{}{}{}{}{{}}}}}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{51.55202pt}{2.37747pt}\pgfsys@curveto{65.88043pt}{6.21675pt}{65.88043pt}{-6.21675pt}{54.15999pt}{-3.07628pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\pgfsys@transformcm{-0.96593}{0.25882}{-0.25882}{-0.96593}{53.33897pt}{-2.8563pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{}{{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{}{}}{{}} {}{}{}{{{}}{{}}{{}}}
{{{}}{{}}{{}}} {}{{}}{}{{}}{}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{36.77467pt}{-7.03687pt}\pgfsys@curveto{22.53604pt}{-24.00613pt}{9.52193pt}{-31.51959pt}{-10.61899pt}{-35.07106pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\pgfsys@transformcm{-0.98482}{-0.17365}{0.17365}{-0.98482}{-11.45607pt}{-35.21864pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-13.38435pt}{32.36838pt}\pgfsys@lineto{33.25183pt}{5.44293pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.86603}{-0.5}{0.5}{0.86603}{33.98795pt}{5.01794pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{}{{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{}{}}{{}} {}{}{}{{{}}{{}}{{}}}
{{{}}{{}}{{}}} {}{{}}{}{{}}{}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-18.19777pt}{28.32938pt}\pgfsys@curveto{-10.64063pt}{7.56653pt}{-10.64063pt}{-7.56653pt}{-17.61633pt}{-26.73192pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\pgfsys@transformcm{-0.34203}{-0.9397}{0.9397}{-0.34203}{-17.90704pt}{-27.53064pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{}{{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{}{}}{{}} {}{}{}{{{}}{{}}{{}}}
{{{}}{{}}{{}}} {}{{}}{}{{}}{}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-15.4351pt}{-29.92445pt}\pgfsys@curveto{-1.19647pt}{-12.95518pt}{11.81764pt}{-5.44173pt}{31.95856pt}{-1.89026pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.98482}{0.17365}{-0.17365}{0.98482}{32.79564pt}{-1.74268pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{}{{}}{{}}{{{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{}{}{}{}{{}}}} }{{}{}}{{}} {}{}{}{{{}}{{}}{{}}}
{{{}}{{}}{{}}} {}{{}}{}{{}}{}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@rgb@stroke{1}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.7pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-24.48137pt}{-28.32938pt}\pgfsys@curveto{-32.03851pt}{-7.56653pt}{-32.03851pt}{7.56653pt}{-25.0628pt}{26.73192pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,0,0}\pgfsys@color@rgb@fill{1}{0}{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.34203}{0.9397}{-0.9397}{0.34203}{-24.7721pt}{27.53064pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$\\\
$D$&$\overline{D}$\\\ \hline\cr\end{tabular}\ \ \ \ \ \ \ \ \ \ .$

######  Definition 1.4.

Let $V$ be a finite set. A $V$_-listing_ will mean a list of elements of $V$
that contains each element of $V$ exactly once.

For example, $\left(2,1,3\right)$ is a $\left\\{1,2,3\right\\}$-listing.

Of course, if $V$ is a finite set, then there are exactly $\left|V\right|!$
many $V$-listings. They are in a canonical bijection with the bijective maps
from $\left[\left|V\right|\right]$ to $V$, and in a non-canonical bijection
with the permutations of $V$.

######  Convention 1.1.

If $w$ is any list (i.e., tuple), and if $i$ is a positive integer, then
$w_{i}$ shall denote the $i$-th entry of $w$. (Thus,
$w=\left(w_{1},w_{2},\ldots,w_{k}\right)$, where $k$ is the length of $w$.)

######  Definition 1.5.

Let $D=\left(V,A\right)$ be a digraph. Let
$w=\left(w_{1},w_{2},\ldots,w_{n}\right)$ be a $V$-listing. Then:

  1. (a)

A $D$_-descent_ of $w$ means an $i\in\left[n-1\right]$ satisfying
$\left(w_{i},w_{i+1}\right)\in A$.

  2. (b)

We let $\operatorname*{Des}\left(w,D\right)$ denote the set of all
$D$-descents of $w$.

######  Example 1.6.

Let $D$ be the digraph $D$ from Example 1.3, and let $w$ be the $V$-listing
$\left(3,1,2\right)$. Then, $2$ is a $D$-descent of $w$ (since
$\left(w_{2},w_{3}\right)=\left(1,2\right)\in A$), but $1$ is not a
$D$-descent of $w$ (since $\left(w_{1},w_{2}\right)=\left(3,1\right)\notin
A$). Hence, $\operatorname*{Des}\left(w,D\right)=\left\\{2\right\\}$.

######  Example 1.7.

Let $n\in\mathbb{N}$, and let $V=\left[n\right]$. Let $D$ be the digraph whose
vertices are the elements of $V$ and whose arcs are all the pairs
$\left(i,j\right)\in\left[n\right]^{2}$ satisfying $i>j$. Let $w$ be a
$V$-listing. Then, the $D$-descents of $w$ are exactly the descents of $w$ in
the usual sense (i.e., the numbers $i\in\left[n-1\right]$ satisfying
$w_{i}>w_{i+1}$).

We note that $D$-descents for general digraphs $D$ have already implicitly
appeared in the work of Foata and Zeilberger [FoaZei96], which considers the
number
$\operatorname*{maj}\nolimits_{D}^{\prime}w:=\sum\limits_{i\in\operatorname*{Des}\left(w,D\right)}i$
for each $V$-listing $w$. We would not be surprised if what follows can shed
some new light on the results of [FoaZei96], but so far we have not found any
deeper connections.

###  1.2 Quasisymmetric functions

Next, we introduce some notations from the theory of quasisymmetric functions
(see, e.g., [Stanle01, §7.19] or [GriRei20, Chapter 5]):

######  Definition 1.8.

  1. (a)

A _composition_ means a finite list of positive integers. If
$\alpha=\left(\alpha_{1},\alpha_{2},\ldots,\alpha_{k}\right)$ is a
composition, then the number $k$ is called the _length_ of $\alpha$, whereas
the number $\alpha_{1}+\alpha_{2}+\cdots+\alpha_{k}$ is called the _size_ of
$\alpha$. If $n\in\mathbb{N}$, then a _composition of_ $n$ shall mean a
composition having size $n$.

  2. (b)

A _partition_ (or _integer partition_) means a composition that is weakly
decreasing.

For example, $\left(2,5,3\right)$ is a composition of $10$ that has length $3$
and is not a partition (since $2<5$).

######  Definition 1.9.

Let $n\in\mathbb{N}$. For any subset $I$ of $\left[n-1\right]$, we let
$\operatorname*{comp}\left(I,n\right)$ be the list

$\left(i_{1}-i_{0},\ i_{2}-i_{1},\ i_{3}-i_{2},\ \ldots,\
i_{k}-i_{k-1}\right),$

where $i_{0},i_{1},\ldots,i_{k}$ are the elements of $\left\\{0\right\\}\cup
I\cup\left\\{n\right\\}$ listed in strictly increasing order. This list
$\operatorname*{comp}\left(I,n\right)$ is a composition of $n$.

######  Example 1.10.

If $n=6$ and $I=\left\\{2,3,5\right\\}$, then
$\operatorname*{comp}\left(I,n\right)=\left(2,1,2,1\right)$.

Note that $\operatorname*{comp}\left(I,n\right)$ is denoted by
$\operatorname*{co}\left(I\right)$ in [Stanle01, §7.19], but we prefer to make
the dependence on $n$ explicit here. In the notation of [GriRei20, Definition
5.1.10], the composition $\operatorname*{comp}\left(I,n\right)$ is the
preimage of $I$ under the bijection
$D:\operatorname*{Comp}\nolimits_{n}\rightarrow 2^{\left[n-1\right]}$.

For any $n\in\mathbb{N}$, the map

$\displaystyle\left\\{\text{subsets of }\left[n-1\right]\right\\}$
$\displaystyle\rightarrow\left\\{\text{compositions of }n\right\\},$
$\displaystyle I$ $\displaystyle\mapsto\operatorname*{comp}\left(I,n\right)$

is a bijection.

######  Definition 1.11.

Consider the ring
$\mathbb{Z}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ of formal power
series in countably many indeterminates $x_{1},x_{2},x_{3},\ldots$. Two
subrings of this ring
$\mathbb{Z}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ are:

  * •

the ring $\Lambda$ of _symmetric functions_ (defined, e.g., in [Stanle01,
§7.1] or in [GriRei20, §2.1]);

  * •

the ring $\operatorname*{QSym}$ of _quasisymmetric functions_ (defined, e.g.,
in [Stanle01, §7.19] or in [GriRei20, §5.1]).

We will not actually use any properties of these rings $\Lambda$ and
$\operatorname*{QSym}$ anywhere except in Sections 8, 6 and 7 (and even there,
only $\Lambda$ will be used); thus, a reader unfamiliar with symmetric
functions can read
$\mathbb{Z}\left[\left[x_{1},x_{2},x_{3},\ldots\right]\right]$ instead of
$\Lambda$ or $\operatorname*{QSym}$ everywhere else.

######  Definition 1.12.

Let $\alpha$ be a composition. Then, $L_{\alpha}$ will denote the _fundamental
quasisymmetric function_ corresponding to $\alpha$. This is a formal power
series in $\operatorname*{QSym}$, and is defined as follows: Let $I$ be the
unique subset of $\left[n-1\right]$ satisfying
$\alpha=\operatorname*{comp}\left(I,n\right)$. Then, we set

$L_{\alpha}=\sum\limits_{\begin{subarray}{c}i_{1}\leq i_{2}\leq\cdots\leq
i_{n};\\\ i_{p}<i_{p+1}\text{ for each }p\in
I\end{subarray}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\in\operatorname*{QSym}$

(where the summation indices $i_{1},i_{2},\ldots,i_{n}$ range over
$\mathbb{P}$).

See [Stanle01, §7.19] or [GriRei20, §5] for more about these fundamental
quasisymmetric functions $L_{\alpha}$ (originally introduced by Ira
Gessel)111Note that the definition of $L_{\alpha}$ given in [GriRei20,
Definition 5.2.4] differs from ours. However, it is equivalent to ours, since
[GriRei20, Proposition 5.2.9] shows that the $L_{\alpha}$ defined in
[GriRei20, Definition 5.2.4] satisfy the same formula that we used to define
our $L_{\alpha}$.. We will actually find it easier to index them not by the
compositions $\alpha$ but rather by the corresponding subsets $I$ of
$\left[n-1\right]$. Thus, we define:

######  Definition 1.13.

Let $n\in\mathbb{N}$, and let $I$ be a subset of $\left[n-1\right]$. Then, we
will use the notation $L_{I,n}$ for
$L_{\operatorname*{comp}\left(I,n\right)}$. Explicitly, we have

$L_{I,n}=\sum\limits_{\begin{subarray}{c}i_{1}\leq i_{2}\leq\cdots\leq
i_{n};\\\ i_{p}<i_{p+1}\text{ for each }p\in
I\end{subarray}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\in\operatorname*{QSym}$ (1)

(where the summation indices $i_{1},i_{2},\ldots,i_{n}$ range over
$\mathbb{P}$).

######  Example 1.14.

If $n=3$ and $I=\left\\{2\right\\}$, then

$\displaystyle L_{I,n}$
$\displaystyle=L_{\left\\{2\right\\},3}=\sum\limits_{\begin{subarray}{c}i_{1}\leq
i_{2}\leq i_{3};\\\ i_{p}<i_{p+1}\text{ for each
}p\in\left\\{2\right\\}\end{subarray}}x_{i_{1}}x_{i_{2}}x_{i_{3}}=\sum\limits_{i_{1}\leq
i_{2}<i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}$
$\displaystyle=x_{1}x_{1}x_{2}+x_{1}x_{1}x_{3}+\cdots+x_{1}x_{2}x_{3}+x_{1}x_{2}x_{4}+\cdots+\cdots+x_{2}x_{2}x_{3}+\cdots.$

###  1.3 The Redei–Berge symmetric function

We are now ready to define the main protagonist of this paper:

######  Definition 1.15.

Let $n\in\mathbb{N}$. Let $D=\left(V,A\right)$ be a digraph with $n$ vertices.
We define the _Redei–Berge symmetric function_ $U_{D}$ to be the
quasisymmetric function

$\sum\limits_{w\text{ is a
}V\text{-listing}}L_{\operatorname*{Des}\left(w,D\right),\
n}\in\operatorname*{QSym}.$

######  Example 1.16.

Let $D$ be the digraph $D$ from Example 1.3. Then,

$\displaystyle U_{D}$ $\displaystyle=\sum\limits_{w\text{ is a
}V\text{-listing}}L_{\operatorname*{Des}\left(w,D\right),\ 3}$
$\displaystyle=L_{\operatorname*{Des}\left(\left(1,2,3\right),D\right),\
3}+L_{\operatorname*{Des}\left(\left(1,3,2\right),D\right),\
3}+L_{\operatorname*{Des}\left(\left(2,1,3\right),D\right),\ 3}$
$\displaystyle\ \ \ \ \ \ \ \ \ \
+L_{\operatorname*{Des}\left(\left(2,3,1\right),D\right),\
3}+L_{\operatorname*{Des}\left(\left(3,1,2\right),D\right),\
3}+L_{\operatorname*{Des}\left(\left(3,2,1\right),D\right),\ 3}$
$\displaystyle=L_{\left\\{1\right\\},\ 3}+L_{\varnothing,\ 3}+L_{\varnothing,\
3}+L_{\varnothing,\ 3}+L_{\left\\{2\right\\},\ 3}+L_{\varnothing,\ 3}$
$\displaystyle=4\cdot\underbrace{L_{\varnothing,\ 3}}_{=\sum\limits_{i_{1}\leq
i_{2}\leq
i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}}+\underbrace{L_{\left\\{1\right\\},\
3}}_{=\sum\limits_{i_{1}<i_{2}\leq
i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}}+\underbrace{L_{\left\\{2\right\\},\
3}}_{=\sum\limits_{i_{1}\leq i_{2}<i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}}$
$\displaystyle=4\cdot\sum\limits_{i_{1}\leq i_{2}\leq
i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}+\sum\limits_{i_{1}<i_{2}\leq
i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}+\sum\limits_{i_{1}\leq
i_{2}<i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}.$

From this expression, we can easily see that $U_{D}$ is actually a symmetric
function, and can be written (e.g.) as $p_{1}^{3}+2p_{1}p_{2}+p_{3}$, where
$p_{k}:=x_{1}^{k}+x_{2}^{k}+x_{3}^{k}+\cdots$ is the $k$-th power-sum
symmetric function for each $k\geq 1$.

The name “Redei–Berge symmetric function” for the power series $U_{D}$ was
chosen because (as we will soon see) it is actually a symmetric function and
is related to two classical results of Redei and Berge on the number of
Hamiltonian paths in digraphs. In [EC2sup22, Problem 120], it is called
$U_{X}$, where $X$ is what we call $A$ (that is, the set of arcs of $D$); but
we shall here put the entire digraph $D$ into the subscript.

The Redei–Berge symmetric function $U_{D}$ equals the quasisymmetric function
$\Xi_{\overline{D}}\left(x,0\right)$ from Chow’s [Chow96].222Indeed, this
equality follows immediately from [Chow96, Proposition 7], since the
quasisymmetric function we call $L_{I,n}$ appears under the name of $Q_{I,n}$
in [Chow96], and since our $\operatorname*{Des}\left(w,\overline{D}\right)$ is
what is called $S\left(w\right)$ in [Chow96]. It also is denoted by
$\Pi_{\overline{D}}$ in [Wisema07].333Indeed, comparing the definition of
$\Pi_{D}$ in [Wisema07, Definition 2.2] with the definition of $\Xi_{D}$ in
[Chow96, §2] shows that $\Pi_{D}=\Xi_{D}\left(x,0\right)$. Thus,
$\Pi_{\overline{D}}=\Xi_{\overline{D}}\left(x,0\right)=U_{D}$ (as we already
know). Several properties of $U_{D}$ have been shown in [Chow96] and in
[Wisema07], and some of them will be reproved here for the sake of self-
containedness and variety. However, our main results – Theorems 1.30, 1.38 and
1.40 – appear to be new.

######  Question 1.17.

Can these results be extended to the more general functions
$\Xi_{D}\left(x,y\right)$ from [Chow96]?

###  1.4 Arcs and cyclic arcs

The main results of this paper are explicit (albeit not, in general,
subtraction-free) expansions of $U_{D}$ in terms of the power-sum symmetric
functions. To state these, we need some more notations. We shall soon define
cycles of digraphs and cycles of permutations, and we will then connect the
two notions. First, some auxiliary notations:

######  Definition 1.18.

Let $V$ be a set. Let $v=\left(v_{1},v_{2},\ldots,v_{k}\right)\in V^{k}$ be a
nonempty tuple of elements of $V$.

  1. (a)

We define a subset $\operatorname*{Arcs}v$ of $V\times V$ by

$\displaystyle\operatorname*{Arcs}v:=\ $
$\displaystyle\left\\{\left(v_{i},v_{i+1}\right)\ \mid\
i\in\left[k-1\right]\right\\}$ $\displaystyle=\ $
$\displaystyle\left\\{\left(v_{1},v_{2}\right),\ \left(v_{2},v_{3}\right),\
\ldots,\ \left(v_{k-1},v_{k}\right)\right\\}$ (2) $\displaystyle\subseteq\ $
$\displaystyle V\times V.$

This subset $\operatorname*{Arcs}v$ is called the _arc set_ of the tuple $v$.
Its elements $\left(v_{i},v_{i+1}\right)$ are called the _arcs_ of $v$.

  2. (b)

We define a subset $\operatorname*{CArcs}v$ of $V\times V$ by

$\displaystyle\operatorname*{CArcs}v:=\ $
$\displaystyle\left\\{\left(v_{i},v_{i+1}\right)\ \mid\
i\in\left[k\right]\right\\}$ $\displaystyle=\ $
$\displaystyle\left\\{\left(v_{1},v_{2}\right),\ \left(v_{2},v_{3}\right),\
\ldots,\ \left(v_{k-1},v_{k}\right),\ \left(v_{k},v_{1}\right)\right\\}$ (3)
$\displaystyle\subseteq\ $ $\displaystyle V\times V,$

where we set $v_{k+1}:=v_{1}$. This subset $\operatorname*{CArcs}v$ is called
the _cyclic arc set_ of the tuple $v$. Its elements
$\left(v_{i},v_{i+1}\right)$ are called the _cyclic arcs_ of $v$.

  3. (c)

The _reversal_ of $v$ is defined to be the tuple
$\left(v_{k},v_{k-1},\ldots,v_{1}\right)\in V^{k}$.

######  Example 1.19.

Let $V=\mathbb{N}$ and $v=\left(1,4,2,6\right)\in V^{4}$. Then,

$\displaystyle\operatorname*{Arcs}v$ $\displaystyle=\left\\{\left(1,4\right),\
\left(4,2\right),\ \left(2,6\right)\right\\}\ \ \ \ \ \ \ \ \ \ \text{and}$
$\displaystyle\operatorname*{CArcs}v$
$\displaystyle=\left\\{\left(1,4\right),\ \left(4,2\right),\
\left(2,6\right),\ \left(6,1\right)\right\\}.$

Note that if we cyclically rotate a nonempty tuple $v\in V^{k}$, then the set
$\operatorname*{CArcs}v$ remains unchanged: i.e., for any
$\left(v_{1},v_{2},\ldots,v_{k}\right)\in V^{k}$, we have

$\operatorname*{CArcs}\left(v_{1},v_{2},\ldots,v_{k}\right)=\operatorname*{CArcs}\left(v_{2},v_{3},\ldots,v_{k},v_{1}\right).$

###  1.5 Permutations and their cycles

Now, let us discuss permutations and their cycles. We start with some basic
notations:

######  Definition 1.20.

Let $V$ be a finite set. Then, $\mathfrak{S}_{V}$ shall denote the symmetric
group of $V$ (that is, the group of all permutations of $V$).

Note that the order of this group is
$\left|\mathfrak{S}_{V}\right|=\left|V\right|!$.

######  Definition 1.21.

Let $V$ be a set.

  1. (a)

Two tuples $v\in V^{k}$ and $w\in V^{\ell}$ of elements of $V$ are said to be
_rotation-equivalent_ if $w$ can be obtained from $v$ by cyclic rotation,
i.e., if $\ell=k$ and
$w=\left(v_{i},v_{i+1},\ldots,v_{k},v_{1},v_{2},\ldots,v_{i-1}\right)$ for
some $i\in\left[k\right]$.

  2. (b)

The relation “rotation-equivalent” is an equivalence relation on the set of
all nonempty tuples of elements of $V$. Its equivalence classes are called the
_rotation-equivalence classes_. In other words, the rotation-equivalence
classes are the orbits of the operation

$\left(a_{1},a_{2},\ldots,a_{k}\right)\mapsto\left(a_{2},a_{3},\ldots,a_{k},a_{1}\right)$

on the set of all nonempty tuples of elements of $V$.

  3. (c)

The rotation-equivalence class that contains a given nonempty tuple $v\in
V^{k}$ will be denoted by $v_{\sim}$.

For instance, the tuple $\left(1,2,3,4\right)$ is rotation-equivalent to
$\left(3,4,1,2\right)$, but not to $\left(4,3,2,1\right)$. Thus,

$\left(1,2,3,4\right)_{\sim}=\left(3,4,1,2\right)_{\sim}\neq\left(4,3,2,1\right)_{\sim}.$

Also,

$\left(1,3,6\right)_{\sim}=\left\\{\left(1,3,6\right),\ \left(3,6,1\right),\
\left(6,1,3\right)\right\\}.$

######  Definition 1.22.

Let $V$ be a set. Let $\gamma$ be a rotation-equivalence class (of nonempty
tuples of elements of $V$). Then:

  1. (a)

All tuples $v\in\gamma$ have the same length (i.e., number of entries). This
length is denoted by $\ell\left(\gamma\right)$, and is called the _length_ of
$\gamma$. Thus, if $\gamma=v_{\sim}$ for some tuple $v\in V^{k}$, then
$\ell\left(\gamma\right)=k$.

  2. (b)

All tuples $v\in\gamma$ have the same cyclic arc set $\operatorname*{CArcs}v$
(since $\operatorname*{CArcs}v$ remains unchanged if we cyclically rotate
$v$). This cyclic arc set is denoted by $\operatorname*{CArcs}\gamma$, and is
called the _cyclic arc set_ of $\gamma$. Thus, the cyclic arc set of a
rotation-equivalence class
$\gamma=\left(v_{1},v_{2},\ldots,v_{k}\right)_{\sim}$ is

$\operatorname*{CArcs}\gamma=\left\\{\left(v_{1},v_{2}\right),\
\left(v_{2},v_{3}\right),\ \ldots,\ \left(v_{k-1},v_{k}\right),\
\left(v_{k},v_{1}\right)\right\\}.$

  3. (c)

All tuples $v\in\gamma$ have the same entries (up to order). These entries are
called the _entries_ of $v$. Thus, the entries of a rotation-equivalence class
$\gamma=\left(v_{1},v_{2},\ldots,v_{k}\right)_{\sim}$ are
$v_{1},v_{2},\ldots,v_{k}$.

  4. (d)

The reversals of all tuples $v\in\gamma$ are the elements of a single
rotation-equivalence class $\operatorname*{rev}\gamma$. This latter class will
be called the _reversal_ of $\gamma$. Thus, the reversal of a rotation-
equivalence class $\gamma=\left(v_{1},v_{2},\ldots,v_{k}\right)_{\sim}$ is the
rotation-equivalence class $\left(v_{k},v_{k-1},\ldots,v_{1}\right)_{\sim}$.

  5. (e)

We say that $\gamma$ is _nontrivial_ if $\ell\left(\gamma\right)>1$.

For instance, the rotation-equivalence class $\left(3,1,4\right)_{\sim}$ has
length $3$, cyclic arc set $\left\\{\left(3,1\right),\ \left(1,4\right),\
\left(4,3\right)\right\\}$, and entries $3,1,4$. Its reversal is
$\left(4,1,3\right)_{\sim}$, and it is nontrivial (since
$\ell\left(\left(3,1,4\right)_{\sim}\right)=3>1$).

######  Definition 1.23.

Let $V$ be a finite set. Let $\sigma\in\mathfrak{S}_{V}$ be any permutation.

  1. (a)

The _cycles_ of $\sigma$ are the rotation-equivalence classes of the tuples of
the form

$\left(\sigma^{0}\left(i\right),\ \sigma^{1}\left(i\right),\ \ldots,\
\sigma^{k-1}\left(i\right)\right),$

where $i$ is some element of $V$, and where $k$ is the smallest positive
integer satisfying $\sigma^{k}\left(i\right)=i$.

For example, the permutation $w_{0}\in\mathfrak{S}_{\left[7\right]}$ that
sends each $i\in\left[7\right]$ to $8-i$ has cycles $\left(1,7\right)_{\sim}$,
$\left(2,6\right)_{\sim}$, $\left(3,5\right)_{\sim}$ and
$\left(4\right)_{\sim}$. (Note that we do allow a cycle to have length $1$.)

  2. (b)

The _cycle type_ of $\sigma$ means the partition whose entries are the lengths
of the cycles of $\sigma$. We denote this cycle type by
$\operatorname*{type}\sigma$. It is a partition of the number
$\left|V\right|$.

  3. (c)

We let $\operatorname*{Cycs}\sigma$ denote the set of all cycles of $\sigma$.

######  Example 1.24.

Let $w_{0}\in\mathfrak{S}_{\left[7\right]}$ be the permutation that sends each
$i\in\left[7\right]$ to $8-i$. We have already seen that $w_{0}$ has cycles
$\left(1,7\right)_{\sim}$, $\left(2,6\right)_{\sim}$,
$\left(3,5\right)_{\sim}$ and $\left(4\right)_{\sim}$. Their respective
lengths are $2,2,2,1$. Thus, the cycle type of $w_{0}$ is
$\operatorname*{type}w_{0}=\left(2,2,2,1\right)$. We have
$\operatorname*{Cycs}\sigma=\left\\{\left(1,7\right)_{\sim},\
\left(2,6\right)_{\sim},\ \left(3,5\right)_{\sim},\
\left(4\right)_{\sim}\right\\}$. The first three of the four cycles
$\left(1,7\right)_{\sim}$, $\left(2,6\right)_{\sim}$,
$\left(3,5\right)_{\sim}$ and $\left(4\right)_{\sim}$ are nontrivial.

###  1.6 $D$-paths and $D$-cycles

Next, we define paths and cycles in a digraph:

######  Definition 1.25.

Let $D=\left(V,A\right)$ be a digraph.

  1. (a)

A $D$_-path_ (or _path of_ $D$) shall mean a nonempty tuple $v$ of distinct
elements of $V$ such that $\operatorname*{Arcs}v\subseteq A$.

  2. (b)

A $D$_-cycle_ (or _cycle of_ $D$) shall mean a rotation-equivalence class
$\gamma$ of nonempty tuples of distinct elements of $V$ such that
$\operatorname*{CArcs}\gamma\subseteq A$.

We note that our notion of “cycle of $D$” differs slightly from the common one
used in graph theory444Namely, cycles in graph theory have their first vertex
repeated at the end, whereas our cycles don’t. However, this difference is
purely notational: A cycle $\left(v_{1},v_{2},\ldots,v_{k}\right)_{\sim}$ in
our sense corresponds to the cycle
$\left(v_{1},v_{2},\ldots,v_{k},v_{1}\right)$ in the graph-theorists’
terminology..

######  Example 1.26.

Let $D$ be the digraph $D$ from Example 1.3. Then:

  1. (a)

The pair $\left(1,2\right)$ as well as the three $1$-tuples $\left(1\right)$,
$\left(2\right)$ and $\left(3\right)$ are $D$-paths. The triple
$\left(1,2,2\right)$ is not a $D$-path (even though it satisfies the
“$\operatorname*{Arcs}v\subseteq A$” condition), since its entries $1,2,2$ are
not distinct. The triple $\left(1,2,3\right)$ is not a $D$-path, since
$\left(2,3\right)$ is not an arc of $D$.

The triple $\left(2,3,1\right)$ is a $\overline{D}$-path (and there are
several others).

  2. (b)

The only $D$-cycles are the rotation-equivalence classes
$\left(2\right)_{\sim}$ and $\left(3\right)_{\sim}$. The $\overline{D}$-cycles
are $\left(1\right)_{\sim}$, $\left(1,3\right)_{\sim}$,
$\left(2,3\right)_{\sim}$ and $\left(2,1,3\right)_{\sim}$.

###  1.7 The sets $\mathfrak{S}_{V}\left(D\right)$ and
$\mathfrak{S}_{V}\left(D,\overline{D}\right)$

Now, we can connect digraphs with permutations by comparing their cycles:

######  Definition 1.27.

Let $D=\left(V,A\right)$ be a digraph. Then, we define555As we warned in
Definition 1.23 (a), we are being cavalier about the distinction between
rotation-equivalence classes and their representatives. Thus, when we say that
a certain cycle $\gamma$ of $\sigma$ is a $D$-cycle, we really mean that some
tuple in the rotation-equivalence class $\gamma$ (and therefore every tuple in
$\gamma$) is a $D$-cycle.

$\mathfrak{S}_{V}\left(D\right):=\left\\{\sigma\in\mathfrak{S}_{V}\ \mid\
\text{each nontrivial cycle of }\sigma\text{ is a }D\text{-cycle}\right\\}$

and

$\mathfrak{S}_{V}\left(D,\overline{D}\right):=\left\\{\sigma\in\mathfrak{S}_{V}\
\mid\ \text{each cycle of }\sigma\text{ is a }D\text{-cycle or a
}\overline{D}\text{-cycle}\right\\}.$

Note that we could just as well replace “each cycle” by “each nontrivial
cycle” in the definition of $\mathfrak{S}_{V}\left(D,\overline{D}\right)$,
since a cycle of length $1$ is always a $D$-cycle or a $\overline{D}$-cycle
(depending on whether its only cyclic arc belongs to $A$ or not). However, we
could not replace “nontrivial cycle” by “cycle” in the definition of
$\mathfrak{S}_{V}\left(D\right)$.

######  Example 1.28.

Let $D$ be the digraph $D$ from Example 1.3. Let $V=\left\\{1,2,3\right\\}$ be
its set of vertices. Then:

  1. (a)

We have
$\mathfrak{S}_{V}\left(D\right)=\left\\{\operatorname*{id}\nolimits_{V}\right\\}$,
since the only $D$-cycles have length $1$.

  2. (b)

We have

$\mathfrak{S}_{V}\left(D,\overline{D}\right)=\left\\{\operatorname*{id}\nolimits_{V},\
\operatorname*{cyc}\nolimits_{1,3},\ \operatorname*{cyc}\nolimits_{2,3},\
\operatorname*{cyc}\nolimits_{1,3,2}\right\\},$

where $\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{k}}$ denotes the
permutation that cyclically permutes the elements $i_{1},i_{2},\ldots,i_{k}$
while leaving all other elements of $V$ unchanged.

###  1.8 Formulas for $U_{D}$

####  1.8.1 The power-sum symmetric functions

We now introduce some of the best-known (and easiest to define) symmetric
functions:

######  Definition 1.29.

  1. (a)

For each positive integer $n$, we define the _power-sum symmetric function_

$p_{n}:=x_{1}^{n}+x_{2}^{n}+x_{3}^{n}+\cdots\in\Lambda.$

  2. (b)

If $\lambda=\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)$ is a
partition with $k$ positive entries, then we set

$p_{\lambda}:=p_{\lambda_{1}}p_{\lambda_{2}}\cdots p_{\lambda_{k}}\in\Lambda.$

For instance,
$p_{\left(2,2,1\right)}=p_{2}p_{2}p_{1}=\left(x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+\cdots\right)^{2}\left(x_{1}+x_{2}+x_{3}+\cdots\right)$.

####  1.8.2 The first main theorem: general digraphs

We now state our first main theorem (which will be proved in Section 2):

######  Theorem 1.30.

Let $D=\left(V,A\right)$ be a digraph. Set

$\varphi\left(\sigma\right):=\sum\limits_{\begin{subarray}{c}\gamma\in\operatorname*{Cycs}\sigma;\\\
\gamma\text{ is a
}D\text{-cycle}\end{subarray}}\left(\ell\left(\gamma\right)-1\right)\ \ \ \ \
\ \ \ \ \ \text{for each }\sigma\in\mathfrak{S}_{V}.$

Then,

$U_{D}=\sum\limits_{\sigma\in\mathfrak{S}_{V}\left(D,\overline{D}\right)}\left(-1\right)^{\varphi\left(\sigma\right)}p_{\operatorname*{type}\sigma}.$

######  Example 1.31.

Let $V=\left\\{1,2,3,4,5,6\right\\}$ and $D=\left(V,\ V\times V\right)$. Let
$\sigma\in\mathfrak{S}_{V}$ be the permutation whose cycles are
$\left(1,3\right)_{\sim}$, $\left(2,4,5\right)_{\sim}$ and
$\left(6\right)_{\sim}$. Then, every cycle of $\sigma$ is a $D$-cycle, and the
number $\varphi\left(\sigma\right)$ (as defined in Theorem 1.30) is

$\displaystyle\left(\ell\left(\left(1,3\right)_{\sim}\right)-1\right)+\left(\ell\left(\left(2,4,5\right)_{\sim}\right)-1\right)+\left(\ell\left(\left(6\right)_{\sim}\right)-1\right)$
$\displaystyle=\left(2-1\right)+\left(3-1\right)+\left(1-1\right)=3.$

######  Example 1.32.

Let $D$ be the digraph $D$ from Example 1.3. Recall that
$\mathfrak{S}_{V}\left(D,\overline{D}\right)=\left\\{\operatorname*{id}\nolimits_{V},\
\operatorname*{cyc}\nolimits_{1,3},\ \operatorname*{cyc}\nolimits_{2,3},\
\operatorname*{cyc}\nolimits_{1,3,2}\right\\}$. Thus, Theorem 1.30 yields

$\displaystyle U_{D}$
$\displaystyle=\underbrace{\left(-1\right)^{\varphi\left(\operatorname*{id}\nolimits_{V}\right)}}_{=\left(-1\right)^{0}=1}\underbrace{p_{\operatorname*{type}\left(\operatorname*{id}\nolimits_{V}\right)}}_{=p_{\left(1,1,1\right)}=p_{1}^{3}}+\underbrace{\left(-1\right)^{\varphi\left(\operatorname*{cyc}\nolimits_{1,3}\right)}}_{=\left(-1\right)^{0}=1}\underbrace{p_{\operatorname*{type}\left(\operatorname*{cyc}\nolimits_{1,3}\right)}}_{=p_{\left(2,1\right)}=p_{2}p_{1}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \
+\underbrace{\left(-1\right)^{\varphi\left(\operatorname*{cyc}\nolimits_{2,3}\right)}}_{=\left(-1\right)^{0}=1}\underbrace{p_{\operatorname*{type}\left(\operatorname*{cyc}\nolimits_{2,3}\right)}}_{=p_{\left(2,1\right)}=p_{2}p_{1}}+\underbrace{\left(-1\right)^{\varphi\left(\operatorname*{cyc}\nolimits_{1,3,2}\right)}}_{=\left(-1\right)^{0}=1}\underbrace{p_{\operatorname*{type}\left(\operatorname*{cyc}\nolimits_{1,3,2}\right)}}_{=p_{\left(3\right)}=p_{3}}$
$\displaystyle=p_{1}^{3}+p_{2}p_{1}+p_{2}p_{1}+p_{3}=p_{1}^{3}+2p_{1}p_{2}+p_{3}.$

This agrees with the result found in Example 1.16.

######  Example 1.33.

Let $D$ be the digraph $\left(V,A\right)$, where $V=\left\\{1,2,3\right\\}$
and

$A=\left\\{\left(1,3\right),\ \left(2,1\right),\ \left(3,1\right),\
\left(3,2\right)\right\\}.$

Then, a straightforward computation using Theorem 1.30 shows that
$U_{D}=p_{1}^{3}-p_{1}p_{2}+p_{3}$. (This example is due to Ira Gessel.)

The following two corollaries can be easily obtained from Theorem 1.30 (see
Section 4 for their proofs):

######  Corollary 1.34.

Let $D=\left(V,A\right)$ be a digraph. Then, $U_{D}$ is a $p$-integral
symmetric function (i.e., a symmetric function that can be written as a
polynomial in $p_{1},p_{2},p_{3},\ldots$). That is, we have
$U_{D}\in\mathbb{Z}\left[p_{1},p_{2},p_{3},\ldots\right]$.

######  Corollary 1.35.

Let $D=\left(V,A\right)$ be a digraph. Assume that every $D$-cycle has odd
length. Then,

$U_{D}=\sum\limits_{\sigma\in\mathfrak{S}_{V}\left(D,\overline{D}\right)}p_{\operatorname*{type}\sigma}\in\mathbb{N}\left[p_{1},p_{2},p_{3},\ldots\right].$

####  1.8.3 The second main theorem: tournaments

After we will have proved Theorem 1.30, we will use it to derive a simpler
formula, which however is specific to tournaments. First, we recall the
definition of a tournament:

######  Definition 1.36.

A _tournament_ means a digraph $D=\left(V,A\right)$ that satisfies the
following two axioms:

  * •

_Looplessness_ : We have $\left(u,u\right)\notin A$ for any $u\in V$.

  * •

_Tournament axiom_ : For any two distinct vertices $u$ and $v$ of $D$, exactly
one of the two pairs $\left(u,v\right)$ and $\left(v,u\right)$ is an arc of
$D$.

######  Example 1.37.

Neither the digraph $D$ from Example 1.3, nor its complement $\overline{D}$,
is a tournament. Here is a tournament:

$\leavevmode\hbox to141.9pt{\vbox
to148.26pt{\pgfpicture\makeatletter\hbox{\hskip
64.43103pt\lower-74.13072pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}
\pgfsys@beginscope\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{77.07233pt}{0.0pt}\pgfsys@curveto{77.07233pt}{4.85237pt}{73.13881pt}{8.78589pt}{68.28644pt}{8.78589pt}\pgfsys@curveto{63.43407pt}{8.78589pt}{59.50055pt}{4.85237pt}{59.50055pt}{0.0pt}\pgfsys@curveto{59.50055pt}{-4.85237pt}{63.43407pt}{-8.78589pt}{68.28644pt}{-8.78589pt}\pgfsys@curveto{73.13881pt}{-8.78589pt}{77.07233pt}{-4.85237pt}{77.07233pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{68.28644pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{65.78644pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{29.88782pt}{64.94484pt}\pgfsys@curveto{29.88782pt}{69.79721pt}{25.9543pt}{73.73073pt}{21.10193pt}{73.73073pt}\pgfsys@curveto{16.24956pt}{73.73073pt}{12.31604pt}{69.79721pt}{12.31604pt}{64.94484pt}\pgfsys@curveto{12.31604pt}{60.09247pt}{16.24956pt}{56.15895pt}{21.10193pt}{56.15895pt}\pgfsys@curveto{25.9543pt}{56.15895pt}{29.88782pt}{60.09247pt}{29.88782pt}{64.94484pt}\pgfsys@closepath\pgfsys@moveto{21.10193pt}{64.94484pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{18.60193pt}{61.72263pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-46.45926pt}{40.13765pt}\pgfsys@curveto{-46.45926pt}{44.99002pt}{-50.39278pt}{48.92354pt}{-55.24515pt}{48.92354pt}\pgfsys@curveto{-60.09752pt}{48.92354pt}{-64.03104pt}{44.99002pt}{-64.03104pt}{40.13765pt}\pgfsys@curveto{-64.03104pt}{35.28528pt}{-60.09752pt}{31.35176pt}{-55.24515pt}{31.35176pt}\pgfsys@curveto{-50.39278pt}{31.35176pt}{-46.45926pt}{35.28528pt}{-46.45926pt}{40.13765pt}\pgfsys@closepath\pgfsys@moveto{-55.24515pt}{40.13765pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-57.74515pt}{36.91544pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$3$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{-46.45926pt}{-40.13765pt}\pgfsys@curveto{-46.45926pt}{-35.28528pt}{-50.39278pt}{-31.35176pt}{-55.24515pt}{-31.35176pt}\pgfsys@curveto{-60.09752pt}{-31.35176pt}{-64.03104pt}{-35.28528pt}{-64.03104pt}{-40.13765pt}\pgfsys@curveto{-64.03104pt}{-44.99002pt}{-60.09752pt}{-48.92354pt}{-55.24515pt}{-48.92354pt}\pgfsys@curveto{-50.39278pt}{-48.92354pt}{-46.45926pt}{-44.99002pt}{-46.45926pt}{-40.13765pt}\pgfsys@closepath\pgfsys@moveto{-55.24515pt}{-40.13765pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-57.74515pt}{-43.35986pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$4$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@rgb@stroke{0}{0.6}{0}\pgfsys@invoke{
}{}\pgfsys@moveto{29.88782pt}{-64.94484pt}\pgfsys@curveto{29.88782pt}{-60.09247pt}{25.9543pt}{-56.15895pt}{21.10193pt}{-56.15895pt}\pgfsys@curveto{16.24956pt}{-56.15895pt}{12.31604pt}{-60.09247pt}{12.31604pt}{-64.94484pt}\pgfsys@curveto{12.31604pt}{-69.79721pt}{16.24956pt}{-73.73073pt}{21.10193pt}{-73.73073pt}\pgfsys@curveto{25.9543pt}{-73.73073pt}{29.88782pt}{-69.79721pt}{29.88782pt}{-64.94484pt}\pgfsys@closepath\pgfsys@moveto{21.10193pt}{-64.94484pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{18.60193pt}{-68.16705pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$5$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@beginscope\pgfsys@invoke{ }
{{}}{}\hbox{\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{ }{}{{ {\pgfsys@beginscope
\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys@roundjoin{} {}{}{} {}{}{}
\pgfsys@moveto{-3.04pt}{3.84514pt}\pgfsys@curveto{-2.4846pt}{1.53802pt}{-1.24696pt}{0.4486pt}{0.0pt}{0.0pt}\pgfsys@curveto{-1.24696pt}{-0.4486pt}{-2.4846pt}{-1.53802pt}{-3.04pt}{-3.84514pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{62.88657pt}{7.43149pt}\pgfsys@lineto{27.20618pt}{56.54195pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{-0.58778}{0.80902}{-0.80902}{-0.58778}{26.85353pt}{57.02734pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{59.54955pt}{-2.83846pt}\pgfsys@lineto{-45.36713pt}{-36.92786pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{-0.95107}{-0.30902}{0.30902}{-0.95107}{-45.93774pt}{-37.11327pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{62.88657pt}{-7.43149pt}\pgfsys@lineto{27.20618pt}{-56.54195pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{-0.58778}{-0.80902}{0.80902}{-0.58778}{26.85353pt}{-57.02734pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{21.10173pt}{55.75845pt}\pgfsys@lineto{21.10173pt}{-54.55847pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.0}{-1.0}{1.0}{0.0}{21.10173pt}{-55.15846pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-46.50838pt}{37.29868pt}\pgfsys@lineto{58.4083pt}{3.20927pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.95107}{-0.30902}{0.30902}{0.95107}{58.97891pt}{3.02386pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-46.50838pt}{42.97574pt}\pgfsys@lineto{11.22435pt}{61.73471pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.95105}{0.30902}{-0.30902}{0.95105}{11.79495pt}{61.92012pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}\hbox{\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-49.84538pt}{-32.70578pt}\pgfsys@lineto{14.99715pt}{56.54195pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.58778}{0.80902}{-0.80902}{0.58778}{15.3498pt}{57.02734pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-55.2445pt}{-30.95148pt}\pgfsys@lineto{-55.2445pt}{29.7515pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.0}{1.0}{-1.0}{0.0}{-55.2445pt}{30.35149pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{-46.50838pt}{-42.97574pt}\pgfsys@lineto{11.22435pt}{-61.73471pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{0.95105}{-0.30902}{0.30902}{0.95105}{11.79495pt}{-61.92012pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{1.2pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{15.70247pt}{-57.51276pt}\pgfsys@lineto{-49.14006pt}{31.73497pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@transformcm{-0.58778}{0.80902}{-0.80902}{-0.58778}{-49.4927pt}{32.22037pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\ \ .$

We can now state our second main theorem (which we will prove in Section 3):

######  Theorem 1.38.

Let $D=\left(V,A\right)$ be a tournament. For each
$\sigma\in\mathfrak{S}_{V}$, let $\psi\left(\sigma\right)$ denote the number
of nontrivial cycles of $\sigma$. Then,

$U_{D}=\sum\limits_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{V}\left(D\right);\\\
\text{all cycles of }\sigma\text{ have odd
length}\end{subarray}}2^{\psi\left(\sigma\right)}p_{\operatorname*{type}\sigma}.$

Once this is proved, the following corollary will be easy to derive (see
Section 4 for the details):

######  Corollary 1.39.

Let $D=\left(V,A\right)$ be a tournament. Then,

$U_{D}\in\mathbb{N}\left[p_{1},2p_{3},2p_{5},2p_{7},\ldots\right]=\mathbb{N}\left[p_{1},\
2p_{i}\ \mid\ i>1\text{ is odd}\right].$

(Here, $\mathbb{N}\left[p_{1},2p_{3},2p_{5},2p_{7},\ldots\right]$ means the
set of all values of the form
$f\left(p_{1},2p_{3},2p_{5},2p_{7},\ldots\right)$, where $f$ is a polynomial
in countably many indeterminates with coefficients in $\mathbb{N}$.)

####  1.8.4 The third main theorem: digraphs with no $2$-cycles

A more general version of Theorem 1.38 is the following:

######  Theorem 1.40.

Let $D=\left(V,A\right)$ be a digraph. Assume that there exist no two distinct
vertices $u$ and $v$ of $D$ such that both pairs $\left(u,v\right)$ and
$\left(v,u\right)$ belong to $A$.

  1. (a)

Then, $U_{D}$ is a $p$-positive symmetric function (i.e., a symmetric function
that can be written as a polynomial in $p_{1},p_{2},p_{3},\ldots$ with
coefficients in $\mathbb{N}$). That is, we have
$U_{D}\in\mathbb{N}\left[p_{1},p_{2},p_{3},\ldots\right]$.

  2. (b)

Let us say that a rotation-equivalence class $\gamma$ of nonempty tuples of
elements of $V$ is _risky_ if its length is even and it has the property that
either $\gamma$ or the reversal of $\gamma$ is a $D$-cycle. Then,

$U_{D}=\sum\limits_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{V}\left(D,\overline{D}\right);\\\
\text{no cycle of }\sigma\text{ is
risky}\end{subarray}}p_{\operatorname*{type}\sigma}.$

We will prove this in Section 5. Note that Theorem 1.40 (a) generalizes
[Chow96, Theorem 7].666To see how, one needs to observe that  1. any acyclic
digraph $D$ satisfies the assumption of Theorem 1.40; 2. the
$\omega_{x}\Xi_{D}$ from [Chow96] equals our $U_{D}$ in the case when $D$ is
acyclic. The first of these two observations is obvious. The second follows
from the equality (61) further below, combined with the fact that
$\Xi_{D}=\Xi_{D}\left(x,0\right)$ when $D$ acyclic (since the $y$-variables do
not actually appear in $\Xi_{D}$ for lack of cycles), and the fact that
$U_{\overline{D}}=\Xi_{D}\left(x,0\right)$ (stated above in the equivalent
form $U_{D}=\Xi_{\overline{D}}\left(x,0\right)$).

######  Remark 1.41.

The converse of Theorem 1.40 (a) does not hold. Indeed, consider the digraph
$D=\left(V,A\right)$ with $V=\left\\{1,2,3,4\right\\}$ and

$A=\left\\{\left(1,2\right),\ \left(2,1\right),\ \left(2,3\right),\
\left(2,4\right),\ \left(3,4\right)\right\\}.$

Then, $D$ does not satisfy the assumption of Theorem 1.40 (since the two
distinct vertices $1$ and $2$ satisfy both $\left(1,2\right)\in A$ and
$\left(2,1\right)\in A$), but the corresponding symmetric function $U_{D}$ is
$p$-positive (indeed, $U_{D}=p_{1}^{4}+p_{2}p_{1}^{2}+p_{3}p_{1}$). It would
be interesting to know some more precise criteria for the $p$-positivity of
$U_{D}$.

The next sections are devoted to the proofs of the above results. Afterwards,
we will proceed with further properties of the Redei-Berge symmetric functions
$U_{D}$ (Section 8), applications to reproving Redei’s and Berge’s theorems
(Section 6) and a (not very substantial) generalization (Section 9).

### Remark on alternative versions

This paper also has a detailed version [GriSta23], which includes more details
(and less handwaving) in some of the proofs (and some straightforward proofs
that have been omitted from the present version).

##  2 Proof of Theorem 1.30

In the following, we will outline the proof of Theorem 1.30. We hope that the
proof can still be simplified further.

###  2.1 Basic conventions

The following two conventions are popular in enumerative combinatorics, and we
too will use them on occasion:

######  Convention 2.1.

The symbol # shall mean “number”. For instance, $\left(\text{\\# of subsets of
}\left\\{1,2,3\right\\}\right)=8$.

######  Convention 2.2.

We shall use the _Iverson bracket notation_ : For any logical statement
$\mathcal{A}$, we let $\left[\mathcal{A}\right]$ denote the truth value of
$\mathcal{A}$. This is the number $\begin{cases}1,&\text{if }\mathcal{A}\text{
is true};\\\ 0,&\text{if }\mathcal{A}\text{ is false}.\end{cases}$

Our proof of Theorem 1.30 will rely on many lemmas. The first is a well-known
cancellation lemma (see, e.g., [Grinbe21, Proposition 7.8.10]):

######  Lemma 2.1.

Let $B$ be a finite set. Then, $\sum\limits_{F\subseteq
B}\left(-1\right)^{\left|F\right|}=\left[B=\varnothing\right]$.

###  2.2 Path covers and linear sets

We begin with some more notations:

######  Definition 2.2.

Let $V$ be a finite set.

  1. (a)

A _path_ of $V$ means a nonempty tuple of distinct elements of $V$.

  2. (b)

An element $v$ is said to _belong_ to a given tuple $t$ if $v$ is an entry of
$t$.

  3. (c)

A _path cover_ of $V$ means a set of paths of $V$ such that each $v\in V$
belongs to exactly one of these paths.

For example,
$\left\\{\left(1,4,3\right),\left(2,8\right),\left(5\right),\left(7,6\right)\right\\}$
is a path cover of $\left[8\right]$. We stress once again the words “exactly
one” in the definition of a path cover. Thus, the paths constituting a path
cover are disjoint (i.e., have no entries in common). For instance,
$\left\\{\left(1,2\right),\left(2,3\right)\right\\}$ is not a path cover of
$\left[3\right]$.

In Definition 1.18 (a), we have introduced the arc set of a path of $V$ (and,
more generally, of any nonempty tuple of elements of $V$). We now extend this
to path covers in the obvious way:

######  Definition 2.3.

Let $V$ be a finite set.

  1. (a)

If $C$ is a path cover of $V$, then the _arc set_ of $C$ is defined to be the
subset

$\bigcup\limits_{v\in C}\operatorname*{Arcs}v\ \ \ \ \ \ \ \ \ \ \text{of
}V\times V.$

This arc set will be denoted by $\operatorname*{Arcs}C$.

  2. (b)

A subset $F$ of $V\times V$ will be called _linear_ if it is the arc set of
some path cover of $V$.

For example, the path cover
$\left\\{\left(1,4,3\right),\left(2,8\right),\left(5\right),\left(7,6\right)\right\\}$
of $\left[8\right]$ has arc set

$\displaystyle\operatorname*{Arcs}\left\\{\left(1,4,3\right),\left(2,8\right),\left(5\right),\left(7,6\right)\right\\}$
$\displaystyle=\operatorname*{Arcs}\left(1,4,3\right)\cup\operatorname*{Arcs}\left(2,8\right)\cup\operatorname*{Arcs}\left(5\right)\cup\operatorname*{Arcs}\left(7,6\right)$
$\displaystyle=\left\\{\left(1,4\right),\
\left(4,3\right)\right\\}\cup\left\\{\left(2,8\right)\right\\}\cup\varnothing\cup\left\\{\left(7,6\right)\right\\}$
$\displaystyle=\left\\{\left(1,4\right),\ \left(4,3\right),\
\left(2,8\right),\ \left(7,6\right)\right\\}.$

Thus, the latter set is linear (as a subset of
$\left[8\right]\times\left[8\right]$).

Note that the notion of “path of $V$” depends on $V$ alone, not on any digraph
structure on $V$. Thus, if $V$ is the vertex set of a digraph
$D=\left(V,A\right)$, then a path of $V$ is not the same as a $D$-path; in
fact, the $D$-paths are precisely the paths $v$ of $V$ that satisfy
$\operatorname*{Arcs}v\subseteq A$.

We shall now see a few properties and characterizations of linear subsets of
$V\times V$. Here is a first one, which will not be used in what follows but
might help in visualizing the concept:

######  Proposition 2.4.

Let $V$ be a finite set. Let $F$ be a subset of $V\times V$. Then, $F$ is
linear if and only if the digraph $\left(V,F\right)$ has no cycles and no
vertices with outdegree $>1$ and no vertices with indegree $>1$.

We omit the proof of this proposition, since we shall have no use for it.

The following is also easy to see:

######  Proposition 2.5.

Let $V$ be a finite set. Let $F$ be a linear subset of $V\times V$. Then, any
subset of $F$ is linear as well.

######  Proof 2.6.

It suffices to show that removing a single element $e$ from a linear subset
$F$ of $V\times V$ yields a linear subset. But this follows from the fact that
if we remove an arc $f$ from a path, then the path breaks up into two smaller
paths (the “part before $f$” and the “part after $f$”).

This quickly leads to the following alternative characterization of linear
subsets:

######  Proposition 2.7.

Let $V$ be a finite set. Let $F$ be a subset of $V\times V$. Then:

  1. (a)

If the subset $F$ is not linear, then there exists no $V$-listing $v$
satisfying $F\subseteq\operatorname*{Arcs}v$.

  2. (b)

If $F=\operatorname*{Arcs}C$ for some path cover $C$ of $V$, then there are
exactly $\left|C\right|!$ many $V$-listings $v$ satisfying
$F\subseteq\operatorname*{Arcs}v$. (Note that $\left|C\right|$ is the number
of paths in $C$.)

  3. (c)

The subset $F$ is linear if and only if it is a subset of
$\operatorname*{Arcs}v$ for some $V$-listing $v$.

######  Proof 2.8.

(a) It clearly suffices to prove the contrapositive: i.e., that if
$F\subseteq\operatorname*{Arcs}v$ for some $V$-listing $v$, then $F$ is
linear.

Let us prove this. Assume that $F\subseteq\operatorname*{Arcs}v$ for some
$V$-listing $v$. Consider this $F$. Then, $\operatorname*{Arcs}v$ is linear
(since $\operatorname*{Arcs}v=\operatorname*{Arcs}\left\\{v\right\\}$ for the
path cover $\left\\{v\right\\}$), and thus Proposition 2.5 shows that $F$ is
also linear (since $F$ is a subset of $\operatorname*{Arcs}v$). This completes
the proof of part (a).

(b) Assume that $F=\operatorname*{Arcs}C$ for some path cover $C$ of $V$.
Consider this $C$.

Then, each $V$-listing $v$ satisfying $F\subseteq\operatorname*{Arcs}v$ can be
obtained by concatenating the paths in $C$ in some order (and conversely, each
such concatenation is a $V$-listing $v$ satisfying
$F\subseteq\operatorname*{Arcs}v$). There are clearly $\left|C\right|!$ many
such concatenations (since there are $\left|C\right|!$ many orders), and they
all lead to different $V$-listings $v$ (since the paths in $C$ are disjoint
and nonempty). Hence, there are exactly $\left|C\right|!$ many $V$-listings
$v$ satisfying $F\subseteq\operatorname*{Arcs}v$. This proves Proposition 2.7
(b).

(c) $\Longrightarrow:$ This follows from part (b) (since $\left|C\right|!>0$).

$\Longleftarrow:$ This is just the contrapositive of part (a).

Next, let us address a technical issue. We defined the notion of a “linear
subset of $V\times V$” using path covers of $V$. When we say that a certain
set is “linear”, we are thus tacitly assuming that it is clear what the
relevant set $V$ is. This may cause an ambiguity: Sometimes, two different
sets $V_{1}$ and $V_{2}$ can reasonably qualify as $V$, and we may have a
subset $F$ of $V_{1}\times V_{1}$ that is also a subset of $V_{2}\times
V_{2}$. In that case, when we say that $F$ is “linear”, do we mean that $F$ is
linear as a subset of $V_{1}\times V_{1}$ or as a subset of $V_{2}\times
V_{2}$ ? Fortunately, this does not matter (at least when $V_{1}$ is a subset
of $V_{2}$), as the following proposition shows:

######  Proposition 2.9.

Let $V$ be a finite set. Let $W$ be a subset of $V$. Let $F$ be a subset of
$W\times W$. Then, $F$ is linear as a subset of $W\times W$ if and only if $F$
is linear as a subset of $V\times V$.

######  Proof 2.10.

$\Longrightarrow:$ Assume that $F$ is linear as a subset of $W\times W$. Thus,
$F$ is the arc set of some path cover $C$ of $W$. If we add a trivial path
$\left(v\right)$ for each $v\in V\setminus W$ to this path cover $C$, then it
becomes a path cover of $V$, but its arc set does not change (and thus remains
$F$). Hence, $F$ is the arc set of the resulting path cover of $V$. In other
words, $F$ is linear as a subset of $V\times V$.

$\Longleftarrow:$ Assume that $F$ is linear as a subset of $V\times V$. Thus,
$F$ is the arc set of some path cover $C$ of $V$. Consider this $C$. For each
$v\in V\setminus W$, there must be a path in $C$ that contains $v$, and this
path must be the trivial path $\left(v\right)$ (since otherwise, this path
would have at least one arc containing $v$, and this arc would then belong to
$\operatorname{Arcs}C=F$; but this would contradict the fact that $F\subseteq
W\times W$). Hence, the path cover $C$ contains the trivial path
$\left(v\right)$ for each $v\in V\setminus W$. Removing all these trivial
paths will turn $C$ into a path cover of $W$, while leaving its arc set
unchanged (so it remains $F$). Hence, $F$ is the arc set of the resulting path
cover of $W$. In other words, $F$ is linear as a subset of $W\times W$.

We will also use the following fact:

######  Proposition 2.11.

Let $V$ be a finite set. Let $V_{1},V_{2},\ldots,V_{k}$ be several disjoint
subsets of $V$ such that $V=V_{1}\cup V_{2}\cup\cdots\cup V_{k}$. For each
$i\in\left[k\right]$, let $F_{i}$ be a subset of $V_{i}\times V_{i}$. Let
$F=F_{1}\cup F_{2}\cup\cdots\cup F_{k}$. Then, the set $F$ is linear (as a
subset of $V\times V$) if and only if all the subsets $F_{i}$ for
$i\in\left[k\right]$ are linear.

######  Proof 2.12.

This is straightforward.

###  2.3 The arrow set of a permutation

We will now see another way to obtain subsets of $V\times V$:

######  Definition 2.13.

Let $V$ be a finite set. Let $\sigma$ be a permutation of $V$. Then,
$\mathbf{A}_{\sigma}$ shall denote the subset

$\left\\{\left(v,\sigma\left(v\right)\right)\ \mid\ v\in
V\right\\}=\bigcup\limits_{c\in\operatorname*{Cycs}\sigma}\operatorname*{CArcs}c$

of $V\times V$.

######  Example 2.14.

Let $V=\left\\{1,2,3,4,5,6\right\\}$, and let $\sigma$ be the permutation of
$V$ that sends $1,2,3,4,5,6$ to $2,3,1,5,4,6$ (respectively). Then,

$\operatorname*{Cycs}\sigma=\left\\{\left(1,2,3\right),\ \left(4,5\right),\
\left(6\right)\right\\}$

and

$\displaystyle\mathbf{A}_{\sigma}$ $\displaystyle=\left\\{\left(1,2\right),\
\left(2,3\right),\ \left(3,1\right),\ \left(4,5\right),\ \left(5,4\right),\
\left(6,6\right)\right\\}$
$\displaystyle=\underbrace{\operatorname*{CArcs}\left(1,2,3\right)}_{=\left\\{\left(1,2\right),\
\left(2,3\right),\
\left(3,1\right)\right\\}}\cup\underbrace{\operatorname*{CArcs}\left(4,5\right)}_{=\left\\{\left(4,5\right),\
\left(5,4\right)\right\\}}\cup\underbrace{\operatorname*{CArcs}\left(6\right)}_{=\left\\{\left(6,6\right)\right\\}}.$

The following is a counterpart to Proposition 2.7 (b):

######  Proposition 2.15.

Let $V$ be a finite set. Let $F$ be a subset of $V\times V$. If
$F=\operatorname*{Arcs}C$ for some path cover $C$ of $V$, then there are
exactly $\left|C\right|!$ many permutations $\sigma\in\mathfrak{S}_{V}$
satisfying $F\subseteq\mathbf{A}_{\sigma}$. (Note that $\left|C\right|$ is the
number of paths in $C$.)

######  Proof 2.16.

Assume that $F=\operatorname*{Arcs}C$ for some path cover $C$ of $V$. Consider
this $C$. We shall refer to the paths in $C$ as “$C$-paths”.

Let $k=\left|C\right|$. Let $s_{1},s_{2},\ldots,s_{k}$ be the starting points
(i.e., first entries) of the $C$-paths, and let $t_{1},t_{2},\ldots,t_{k}$ be
their respective ending points (i.e., last entries). We note that a
permutation $\sigma\in\mathfrak{S}_{V}$ satisfies
$F\subseteq\mathbf{A}_{\sigma}$ if and only if it has the property that
$\sigma\left(v\right)=w$ whenever $v$ and $w$ are two consecutive entries of a
$C$-path. Thus, the condition $F\subseteq\mathbf{A}_{\sigma}$ uniquely
determines the value $\sigma\left(v\right)$ for each $v\in
V\setminus\left\\{t_{1},t_{2},\ldots,t_{k}\right\\}$ (namely,
$\sigma\left(v\right)$ has to be the next entry after $v$ on the $C$-path that
contains $v$), and uniquely determines the value $\sigma^{-1}\left(w\right)$
for each $w\in V\setminus\left\\{s_{1},s_{2},\ldots,s_{k}\right\\}$ (namely,
$\sigma^{-1}\left(w\right)$ has to be the entry just before $v$ on the
$C$-path that contains $v$).

Hence, in order to construct a permutation $\sigma\in\mathfrak{S}_{V}$
satisfying $F\subseteq\mathbf{A}_{\sigma}$, we only need to specify the $k$
values
$\sigma\left(t_{1}\right),\sigma\left(t_{2}\right),\ldots,\sigma\left(t_{k}\right)$
(since all other values $\sigma\left(v\right)$ are already decided by the
requirement $F\subseteq\mathbf{A}_{\sigma}$), and we must choose these $k$
values from the set $\left\\{s_{1},s_{2},\ldots,s_{k}\right\\}$ (since all
other elements of $V$ have already been assigned preimages under $\sigma$ by
the requirement $F\subseteq\mathbf{A}_{\sigma}$). Thus, we must choose a
bijection from the $k$-element set $\left\\{t_{1},t_{2},\ldots,t_{k}\right\\}$
to the $k$-element set $\left\\{s_{1},s_{2},\ldots,s_{k}\right\\}$. This can
be done in $k!$ many ways, i.e., in $\left|C\right|!$ many ways (since
$k=\left|C\right|$). Thus, there are exactly $\left|C\right|!$ many
permutations $\sigma\in\mathfrak{S}_{V}$ satisfying
$F\subseteq\mathbf{A}_{\sigma}$.

###  2.4 Counting hamps by inclusion-exclusion

Our next lemma will be about counting Hamiltonian paths – which we abbreviate
as “hamps”. Here is how they are defined:

######  Definition 2.17.

Let $D$ be a digraph. A _hamp_ of $D$ means a $D$-path that contains each
vertex of $D$. (The word “hamp” is short for “Hamiltonian path”.)

For a digraph $D=\left(V,A\right)$, there is an obvious connection between the
linear subsets of $A$ and the hamps of $D$: If $v$ is a hamp of $D$, then
$\operatorname*{Arcs}v$ is a maximum-size linear subset of $A$ (and this
maximum size is $\left|V\right|-1$ if $V$ is nonempty). More interestingly,
there is a far less obvious connection between the linear subsets of $A$ and
the hamps of the complement $\overline{D}$:

######  Lemma 2.18.

Let $D=\left(V,A\right)$ be a digraph with $V\neq\varnothing$. Then,

$\sum\limits_{F\subseteq A\text{ is
linear}}\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\# of
}\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\right)=\left(\text{\\# of hamps of
}\overline{D}\right).$

(We are using Convention 2.1 here.)

######  Proof 2.19.

We will use the Iverson bracket notation (as in Convention 2.2). We have

$\displaystyle\sum\limits_{v\text{ is a }V\text{-listing}}\ \
\underbrace{\sum\limits_{\begin{subarray}{c}F\subseteq A;\\\
F\subseteq\operatorname*{Arcs}v\end{subarray}}\left(-1\right)^{\left|F\right|}}_{\begin{subarray}{c}=\sum\limits_{F\subseteq
A\cap\operatorname*{Arcs}v}\left(-1\right)^{\left|F\right|}\\\
=\left[A\cap\operatorname*{Arcs}v=\varnothing\right]\\\ \text{(by Lemma
\ref{lem.cancel})}\end{subarray}}$ $\displaystyle=\sum\limits_{v\text{ is a
}V\text{-listing}}\left[A\cap\operatorname*{Arcs}v=\varnothing\right]$
$\displaystyle=\left(\text{\\# of }V\text{-listings }v\text{ satisfying
}A\cap\operatorname*{Arcs}v=\varnothing\right)$ $\displaystyle=\left(\text{\\#
of hamps of }\overline{D}\right)$

(since the hamps of $\overline{D}$ are precisely the $V$-listings $v$ such
that $A\cap\operatorname*{Arcs}v=\varnothing$). Thus,

$\displaystyle\left(\text{\\# of hamps of }\overline{D}\right)$
$\displaystyle=\sum\limits_{v\text{ is a }V\text{-listing}}\ \
\sum\limits_{\begin{subarray}{c}F\subseteq A;\\\
F\subseteq\operatorname*{Arcs}v\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\sum\limits_{F\subseteq A}\ \
\sum\limits_{\begin{subarray}{c}v\text{ is a }V\text{-listing;}\\\
F\subseteq\operatorname*{Arcs}v\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\sum\limits_{F\subseteq A\text{ is linear}}\ \
\sum\limits_{\begin{subarray}{c}v\text{ is a }V\text{-listing;}\\\
F\subseteq\operatorname*{Arcs}v\end{subarray}}\left(-1\right)^{\left|F\right|}$
(4)

(here, we have restricted the outer sum to only the linear subsets $F$ of $A$,
because if a subset $F$ of $A$ is not linear, then the inner sum
$\sum\limits_{\begin{subarray}{c}v\text{ is a }V\text{-listing;}\\\
F\subseteq\operatorname*{Arcs}v\end{subarray}}\left(-1\right)^{\left|F\right|}$
is empty777by Proposition 2.7 (a)).

Now, let $F$ be a linear subset of $A$. Thus, $F=\operatorname*{Arcs}C$ for
some path cover $C$ of $V$. Consider this $C$. Then, Proposition 2.15 yields
that

$\left(\text{\\# of }\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\right)=\left|C\right|!.$ (5)

On the other hand, Proposition 2.7 (b) yields that

$\left(\text{\\# of }V\text{-listings }v\text{ satisfying
}F\subseteq\operatorname*{Arcs}v\right)=\left|C\right|!.$

Hence,

$\displaystyle\sum\limits_{\begin{subarray}{c}v\text{ is a
}V\text{-listing;}\\\
F\subseteq\operatorname*{Arcs}v\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\underbrace{\left(\text{\\# of }V\text{-listings }v\text{
satisfying
}F\subseteq\operatorname*{Arcs}v\right)}_{\begin{subarray}{c}=\left|C\right|!\\\
=\left(\text{\\# of }\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\right)\\\ \text{(by (\ref{pf.lem.hamps-by-
lin.short.5}))}\end{subarray}}\cdot\left(-1\right)^{\left|F\right|}$
$\displaystyle=\left(\text{\\# of }\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\right)\cdot\left(-1\right)^{\left|F\right|}$
$\displaystyle=\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\# of
}\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\right).$ (6)

Forget that we fixed $F$. We thus have proved (6) for each linear subset $F$
of $A$. Now, (4) becomes

$\displaystyle\left(\text{\\# of hamps of }\overline{D}\right)$
$\displaystyle=\sum\limits_{F\subseteq A\text{ is linear}}\ \
\underbrace{\sum\limits_{\begin{subarray}{c}v\text{ is a }V\text{-listing;}\\\
F\subseteq\operatorname*{Arcs}v\end{subarray}}\left(-1\right)^{\left|F\right|}}_{\begin{subarray}{c}=\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\#
of }\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\right)\\\ \text{(by (\ref{pf.lem.hamps-by-
lin.short.6}))}\end{subarray}}$ $\displaystyle=\sum\limits_{F\subseteq A\text{
is linear}}\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\# of
}\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\right).$

This proves Lemma 2.18.

###  2.5 Level decomposition and maps $f$ satisfying $f\circ\sigma=f$

This entire subsection is devoted to building up some language that will only
ever be used in the proof of Lemma 2.35. All proofs are omitted, as they are
straightforward exercises in understanding the underlying definitions. (They
can be found in the detailed version [GriSta23], too.)

We shall study what happens when a function $f:V\rightarrow\mathbb{P}$ is
introduced into a digraph $D=\left(V,A\right)$. The nonempty fibers of $f$
(i.e., the sets $f^{-1}\left(j\right)$ for all $j\in f\left(V\right)$)
partition the vertex set $V$, and this leads to a decomposition of $D$ into
subdigraphs. Let us introduce some notation for this, starting with the case
of an arbitrary set $V$ (we will later specialize to digraphs):

######  Definition 2.20.

Let $V$ be any set. Let $f:V\rightarrow\mathbb{P}$ be any map.

  1. (a)

For each $v\in V$, we will refer to the number $f\left(v\right)$ as the
_level_ of $v$ (with respect to $f$).

  2. (b)

For each $j\in\mathbb{P}$, the subset $f^{-1}\left(j\right)$ of $V$ shall be
called the $j$_-th level set_ of $f$.

######  Example 2.21.

Let $V=\left\\{1,2,3\right\\}$. Let $f:V\rightarrow\mathbb{P}$ be given by
$f\left(1\right)=1$, $f\left(2\right)=4$ and $f\left(3\right)=1$. Then, the
level sets of $f$ are

$\displaystyle f^{-1}\left(1\right)$ $\displaystyle=\left\\{1,3\right\\},\ \ \
\ \ \ \ \ \ \ f^{-1}\left(4\right)=\left\\{2\right\\},\ \ \ \ \ \ \ \ \ \
\text{and}$ $\displaystyle f^{-1}\left(j\right)$
$\displaystyle=\varnothing\text{ for all
}j\in\mathbb{P}\setminus\left\\{1,4\right\\}.$

######  Remark 2.22.

Let $V$ be any set. Let $f:V\rightarrow\mathbb{P}$ be any map. Let
$j\in\mathbb{P}$. Then, the $j$-th level set $f^{-1}\left(j\right)$ is empty
if and only if $j\notin f\left(V\right)$. Hence, the nonempty level sets of
$f$ correspond to the elements of $f\left(V\right)$.

######  Definition 2.23.

Let $D=\left(V,A\right)$ be a digraph. Let $f:V\rightarrow\mathbb{P}$ be any
map.

  1. (a)

For each $j\in\mathbb{P}$, we define a subset $A_{j}$ of $A$ by

$\displaystyle A_{j}:$ $\displaystyle=\left\\{\left(u,v\right)\in A\ \mid\
u,v\in f^{-1}\left(j\right)\right\\}$ (7)
$\displaystyle=\left\\{\left(u,v\right)\in A\ \mid\
f\left(u\right)=f\left(v\right)=j\right\\}$ (8)
$\displaystyle=A\cap\left(f^{-1}\left(j\right)\times
f^{-1}\left(j\right)\right).$ (9)

This set $A_{j}$ is also a subset of $f^{-1}\left(j\right)\times
f^{-1}\left(j\right)$, of course.

  2. (b)

We let $A_{f}$ denote the subset

$\left\\{\left(u,v\right)\in A\ \mid\
f\left(u\right)=f\left(v\right)\right\\}$

of $A$.

  3. (c)

For each $j\in\mathbb{P}$, we let $D_{j}$ denote the digraph
$\left(f^{-1}\left(j\right),\ A_{j}\right)$. This digraph $D_{j}$ is the
restriction of the digraph $D$ to the subset $f^{-1}\left(j\right)$ (that is,
the digraph obtained from $D$ by removing all vertices that don’t belong to
$f^{-1}\left(j\right)$ and all arcs that contain any of these vertices).

This digraph $D_{j}$ will be called the $j$_-th level subdigraph_ of $D$ with
respect to $f$. (We should properly call it $D_{j,f}$ instead of $D_{j}$, but
we will usually keep $f$ fixed when we study it.)

######  Example 2.24.

Let $D$ be as in Example 1.3. Let $f:V\rightarrow\mathbb{P}$ be given by
$f\left(1\right)=1$, $f\left(2\right)=4$ and $f\left(3\right)=1$. Then,

$\displaystyle A_{1}$ $\displaystyle=\left\\{\left(3,3\right)\right\\},\ \ \ \
\ \ \ \ \ \ A_{4}=\left\\{\left(2,2\right)\right\\},$ $\displaystyle A_{j}$
$\displaystyle=\varnothing\text{ for all
}j\in\mathbb{P}\setminus\left\\{1,4\right\\},$

and

$A_{f}=\left\\{\left(3,3\right),\ \left(2,2\right)\right\\}.$

The level subdigraphs of $D$ are the two digraphs

$D_{1}=\left(\left\\{1,3\right\\},\ \left\\{\left(3,3\right)\right\\}\right)\
\ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \
D_{4}=\left(\left\\{2\right\\},\ \left\\{\left(2,2\right)\right\\}\right)$

(as well as the infinitely many empty digraphs $D_{j}$ for all
$j\in\mathbb{P}\setminus\left\\{1,4\right\\}$). Note that the arc
$\left(3,3\right)$ of $D$ is contained in $D_{1}$, and the arc
$\left(2,2\right)$ is contained in $D_{4}$, but the arc $\left(1,2\right)$ is
contained in none of the level subdigraphs (since its two endpoints $1$ and
$2$ have different levels).

######  Remark 2.25.

Let $D=\left(V,A\right)$ be a digraph. Let $f:V\rightarrow\mathbb{P}$ be any
map. Let $j\in\mathbb{P}$. Then, the $j$-th level subdigraph $D_{j}$ and its
arc set $A_{j}$ are empty if $j\notin f\left(V\right)$. (However, $A_{j}$ can
be empty even if $j$ does belong to $f\left(V\right)$.)

In the following, the symbols “$\sqcup$” and “$\bigsqcup\limits$” stand for
unions of disjoint sets. Thus, for example, “$A_{1}\sqcup A_{2}\sqcup
A_{3}\sqcup\cdots$” will mean the union of some (pairwise) disjoint sets
$A_{1},A_{2},A_{3},\ldots$.

######  Proposition 2.26.

Let $V$ and $J$ be two finite sets. Let $V_{j}$ be a subset of $V$ for each
$j\in J$. Assume that the sets $V_{j}$ for different $j\in J$ are disjoint.
Let $C_{j}$ be a path cover of $V_{j}$ for each $j\in J$. Then:

  1. (a)

The sets $C_{j}$ for different $j\in J$ are disjoint.

  2. (b)

Their union $\bigsqcup\limits_{j\in J}C_{j}$ is a path cover of
$\bigsqcup\limits_{j\in J}V_{j}$, and its arc set is
$\operatorname*{Arcs}\left(\bigsqcup\limits_{j\in
J}C_{j}\right)=\bigsqcup\limits_{j\in
J}\operatorname*{Arcs}\left(C_{j}\right)$.

######  Corollary 2.27.

Let $V$ and $J$ be two finite sets. Let $V_{j}$ be a subset of $V$ for each
$j\in J$. Assume that the sets $V_{j}$ for different $j\in J$ are disjoint.
For each $j\in J$, let $F_{j}$ be a linear subset of $V_{j}\times V_{j}$.
Then, the union $\bigcup\limits_{j\in J}F_{j}$ is a linear subset of $V\times
V$.

######  Proposition 2.28.

Let $D=\left(V,A\right)$ be a digraph. Let $f:V\rightarrow\mathbb{P}$ be any
map. Then, the sets $A_{1},A_{2},A_{3},\ldots$ are disjoint, and their union
is

$A_{1}\sqcup A_{2}\sqcup A_{3}\sqcup\cdots=\bigsqcup\limits_{j\in
f\left(V\right)}A_{j}=A_{f}.$

Let us now connect the level decomposition to linear sets:

######  Proposition 2.29.

Let $D=\left(V,A\right)$ be a digraph. Let $f:V\rightarrow\mathbb{P}$ be any
map. Let $F$ be any set. Then:

  1. (a)

The set $F$ is a linear subset of $A_{f}$ if and only if $F$ can be written as
$F=\bigsqcup\limits_{j\in f\left(V\right)}F_{j}$, where each $F_{j}$ is a
linear subset of $A_{j}$.

  2. (b)

In this case, the subsets $F_{j}$ are uniquely determined by $F$ (namely,
$F_{j}=F\cap A_{j}$ for each $j\in f\left(V\right)$).

Next, we return to studying permutations.

When a set $V$ is a union of two disjoint subsets $A$ and $B$, and we are
given a permutation $\sigma_{A}$ of $A$ and a permutation $\sigma_{B}$ of $B$,
then we can combine these two permutations to obtain a permutation
$\sigma_{A}\oplus\sigma_{B}$ of $V$: Namely, this latter permutation sends
each $a\in A$ to $\sigma_{A}\left(a\right)$, and sends each $b\in B$ to
$\sigma_{B}\left(b\right)$. That is, this permutation
$\sigma_{A}\oplus\sigma_{B}$ is “acting as $\sigma_{A}$” on the subset $A$ and
“acting as $\sigma_{B}$” on the subset $B$.

The same construction can be performed when $V$ is a union of more than two
disjoint subsets (and we are given a permutation of each of these subsets). We
will encounter this situation when a map $f:V\rightarrow\mathbb{P}$ subdivides
the set $V$ into its level sets $f^{-1}\left(1\right),\ f^{-1}\left(2\right),\
f^{-1}\left(3\right),\ \ldots$, and we are given a permutation
$\sigma_{j}\in\mathfrak{S}_{f^{-1}\left(j\right)}$ of each level set
$f^{-1}\left(j\right)$ (to be more precise, we only need $\sigma_{j}$ to be
given when $j\in f\left(V\right)$, since the level set $f^{-1}\left(j\right)$
is empty otherwise). The permutation of $V$ obtained by combining these
permutations $\sigma_{j}$ will then be denoted by $\bigoplus\limits_{j\in
f\left(V\right)}\sigma_{j}$. Here is its explicit definition:

######  Definition 2.30.

Let $V$ be any set. Let $f:V\rightarrow\mathbb{P}$ be any map.

For each $j\in f\left(V\right)$, let
$\sigma_{j}\in\mathfrak{S}_{f^{-1}\left(j\right)}$ be a permutation of the
level set $f^{-1}\left(j\right)$.

Then, $\bigoplus\limits_{j\in f\left(V\right)}\sigma_{j}$ shall denote the
permutation of $V$ that sends each $v\in V$ to
$\sigma_{f\left(v\right)}\left(v\right)$. This is the permutation that acts as
$\sigma_{j}$ on each level set $f^{-1}\left(j\right)$.

######  Proposition 2.31.

Let $V$ be any set. Let $f:V\rightarrow\mathbb{P}$ be any map. Let
$\sigma\in\mathfrak{S}_{V}$ be any permutation. Then:

  1. (a)

We have $f\circ\sigma=f$ if and only if $\sigma$ can be written in the form
$\sigma=\bigoplus\limits_{j\in f\left(V\right)}\sigma_{j}$, where
$\sigma_{j}\in\mathfrak{S}_{f^{-1}\left(j\right)}$ for each $j\in
f\left(V\right)$.

  2. (b)

In this case, the permutations $\sigma_{j}$ for all $j\in f\left(V\right)$ are
uniquely determined by $\sigma$ (namely, $\sigma_{j}$ is the restriction of
$\sigma$ to the subset $f^{-1}\left(j\right)$ for each $j\in
f\left(V\right)$).

Now, we recall the set $\mathbf{A}_{\sigma}$ defined in Definition 2.13 for
any finite set $V$ and any permutation $\sigma$ of $V$.

######  Proposition 2.32.

Let $V$ be a finite set. Let $f:V\rightarrow\mathbb{P}$ be any map. Let
$\sigma\in\mathfrak{S}_{V}$ be a permutation satisfying $f\circ\sigma=f$.
Write $\sigma$ in the form $\sigma=\bigoplus\limits_{j\in
f\left(V\right)}\sigma_{j}$, where
$\sigma_{j}\in\mathfrak{S}_{f^{-1}\left(j\right)}$ for each $j\in
f\left(V\right)$. (This can be done, because of Proposition 2.31 (a).) Then,

$\mathbf{A}_{\sigma}=\bigsqcup\limits_{j\in
f\left(V\right)}\mathbf{A}_{\sigma_{j}}.$

Next, we connect the above construction with the level subdigraphs of a
digraph:

######  Proposition 2.33.

Let $D=\left(V,A\right)$ be a digraph. Let $f:V\rightarrow\mathbb{P}$ be any
map. Let $\sigma\in\mathfrak{S}_{V}$ be a permutation satisfying
$f\circ\sigma=f$. Then,

$\mathbf{A}_{\sigma}\cap A\subseteq A_{f}.$

Our last result in this section is the following trivial yet complex-looking
lemma, which will be used in the proof after it:

######  Lemma 2.34.

Let $D=\left(V,A\right)$ be a digraph. Let $f:V\rightarrow\mathbb{P}$ be any
map. Let $\sigma_{j}\in\mathfrak{S}_{f^{-1}\left(j\right)}$ be a permutation
for each $j\in f\left(V\right)$. Let $F_{j}$ be a subset of $A_{j}$ for each
$j\in f\left(V\right)$. Then, we have the following logical equivalence:

$\ \left(\bigsqcup\limits_{j\in
f\left(V\right)}F_{j}\subseteq\bigsqcup\limits_{j\in
f\left(V\right)}\mathbf{A}_{\sigma_{j}}\right)\ \Longleftrightarrow\
\left(F_{j}\subseteq\mathbf{A}_{\sigma_{j}}\text{ for each }j\in
f\left(V\right)\right).$

###  2.6 An alternating sum involving permutations $\sigma$ with
$f\circ\sigma=f$

Now, we come to a crucial lemma, which generalizes Lemma 2.18 to the case of a
digraph $D=\left(V,A\right)$ “shattered” by a map $f:V\rightarrow\mathbb{P}$:

######  Lemma 2.35.

Let $D=\left(V,A\right)$ be a digraph. Let $f:V\rightarrow\mathbb{P}$ be any
map. For each $j\in\mathbb{P}$, we define a digraph $D_{j}$ as in Definition
2.23 (c). Then,

$\sum\limits_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{V};\\\
f\circ\sigma=f\end{subarray}}\ \
\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap A\\\
\text{is
linear}\end{subarray}}\left(-1\right)^{\left|F\right|}=\prod\limits_{j\in
f\left(V\right)}\left(\text{\\# of hamps of }\overline{D_{j}}\right).$

######  Proof 2.36.

We shall use the notations from Definition 2.20, Definition 2.23 and
Definition 2.30. We recall that every $j\in\mathbb{P}$ satisfies
$D_{j}=\left(f^{-1}\left(j\right),\ A_{j}\right)$ (by the definition of
$D_{j}$).

Let $\sigma\in\mathfrak{S}_{V}$ be a permutation satisfying $f\circ\sigma=f$.
Then, Proposition 2.33 yields $\mathbf{A}_{\sigma}\cap A\subseteq A_{f}$.
Hence, $\mathbf{A}_{\sigma}\cap A=\mathbf{A}_{\sigma}\cap A_{f}$ (because
$\underbrace{\mathbf{A}_{\sigma}}_{=\mathbf{A}_{\sigma}\cap\mathbf{A}_{\sigma}}\cap
A=\mathbf{A}_{\sigma}\cap\underbrace{\mathbf{A}_{\sigma}\cap A}_{\subseteq
A_{f}}\subseteq\mathbf{A}_{\sigma}\cap A_{f}$ and conversely
$\mathbf{A}_{\sigma}\cap\underbrace{A_{f}}_{\subseteq
A}\subseteq\mathbf{A}_{\sigma}\cap A$). Thus,

$\displaystyle\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap
A\\\ \text{is linear}\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap
A_{f}\\\ \text{is linear}\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}F\subseteq A_{f}\text{ is
linear};\\\
F\subseteq\mathbf{A}_{\sigma}\end{subarray}}\left(-1\right)^{\left|F\right|}$
(10)

(since a subset of $\mathbf{A}_{\sigma}\cap A_{f}$ is the same thing as a
subset $F$ of $A_{f}$ that satisfies $F\subseteq\mathbf{A}_{\sigma}$).

Forget that we fixed $\sigma$. We thus have proved (10) for every
$\sigma\in\mathfrak{S}_{V}$ satisfying $f\circ\sigma=f$.

Summing up the equality (10) over all permutations $\sigma\in\mathfrak{S}_{V}$
satisfying $f\circ\sigma=f$, we obtain

$\displaystyle\sum\limits_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{V};\\\
f\circ\sigma=f\end{subarray}}\ \
\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap A\\\
\text{is linear}\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{V};\\\
f\circ\sigma=f\end{subarray}}\ \ \sum\limits_{\begin{subarray}{c}F\subseteq
A_{f}\text{ is linear};\\\
F\subseteq\mathbf{A}_{\sigma}\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\sum\limits_{F\subseteq A_{f}\text{ is linear}}\ \
\underbrace{\sum\limits_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{V};\\\
F\subseteq\mathbf{A}_{\sigma};\\\
f\circ\sigma=f\end{subarray}}\left(-1\right)^{\left|F\right|}}_{=\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\#
of }\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\text{ and }f\circ\sigma=f\right)}$
$\displaystyle=\sum\limits_{F\subseteq A_{f}\text{ is
linear}}\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\# of
}\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\text{ and }f\circ\sigma=f\right).$ (11)

Now, a linear subset $F$ of $A_{f}$ is the same as a set $F$ of the form
$\bigsqcup\limits_{j\in f\left(V\right)}F_{j}$, where each $F_{j}$ is a linear
subset of $A_{j}$ (by Proposition 2.29 (a)); furthermore, if $F$ is such a
subset, then the latter subsets $F_{j}$ satisfying $F=\bigsqcup\limits_{j\in
f\left(V\right)}F_{j}$ are uniquely determined by $F$ (by Proposition 2.29
(b)). Hence, we can substitute $\bigsqcup\limits_{j\in f\left(V\right)}F_{j}$
for $F$ in the sum on the right hand side of (11). We thus obtain

$\displaystyle\sum\limits_{F\subseteq A_{f}\text{ is
linear}}\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\# of
}\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\text{ and }f\circ\sigma=f\right)$
$\displaystyle=\sum\limits_{\begin{subarray}{c}\left(F_{j}\right)_{j\in
f\left(V\right)}\text{ is a family}\\\ \text{of linear subsets }F_{j}\subseteq
A_{j}\end{subarray}}\left(-1\right)^{\left|\bigsqcup\limits_{j\in
f\left(V\right)}F_{j}\right|}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\cdot\left(\text{\\# of }\sigma\in\mathfrak{S}_{V}\text{ satisfying
}\bigsqcup\limits_{j\in
f\left(V\right)}F_{j}\subseteq\mathbf{A}_{\sigma}\text{ and
}f\circ\sigma=f\right).$ (12)

Furthermore, a permutation $\sigma\in\mathfrak{S}_{V}$ satisfies
$f\circ\sigma=f$ if and only if it can be written in the form
$\sigma=\bigoplus\limits_{j\in f\left(V\right)}\sigma_{j}$, where
$\sigma_{j}\in\mathfrak{S}_{f^{-1}\left(j\right)}$ for each $j\in
f\left(V\right)$ (by Proposition 2.31 (a)). Moreover, if $\sigma$ is written
in this way, then the permutations $\sigma_{j}$ are uniquely determined by
$\sigma$ (by Proposition 2.31 (b)), and we have
$\mathbf{A}_{\sigma}=\bigsqcup\limits_{j\in
f\left(V\right)}\mathbf{A}_{\sigma_{j}}$ (by Proposition 2.32). Hence, for
each family $\left(F_{j}\right)_{j\in f\left(V\right)}$ of linear subsets
$F_{j}\subseteq A_{j}$, we have

$\displaystyle\left(\text{\\# of }\sigma\in\mathfrak{S}_{V}\text{ satisfying
}\bigsqcup\limits_{j\in
f\left(V\right)}F_{j}\subseteq\mathbf{A}_{\sigma}\text{ and
}f\circ\sigma=f\right)$ $\displaystyle=\left(\text{\\# of families
}\left(\sigma_{j}\right)_{j\in f\left(V\right)}\in\prod\limits_{j\in
f\left(V\right)}\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}\bigsqcup\limits_{j\in f\left(V\right)}F_{j}\subseteq\bigsqcup\limits_{j\in
f\left(V\right)}\mathbf{A}_{\sigma_{j}}\right)$ $\displaystyle=\left(\text{\\#
of families }\left(\sigma_{j}\right)_{j\in
f\left(V\right)}\in\prod\limits_{j\in
f\left(V\right)}\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F_{j}\subseteq\mathbf{A}_{\sigma_{j}}\text{ for each }j\in
f\left(V\right)\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\left(\begin{array}[c]{c}\text{since the condition
\textquotedblleft}\bigsqcup\limits_{j\in
f\left(V\right)}F_{j}\subseteq\bigsqcup\limits_{j\in
f\left(V\right)}\mathbf{A}_{\sigma_{j}}\text{\textquotedblright}\\\ \text{is
equivalent to \textquotedblleft}F_{j}\subseteq\mathbf{A}_{\sigma_{j}}\text{
for each }j\in f\left(V\right)\text{\textquotedblright}\\\ \text{(by Lemma
\ref{lem.level.djunex})}\end{array}\right)$ (16)
$\displaystyle=\prod\limits_{j\in f\left(V\right)}\left(\text{\\# of
}\sigma_{j}\in\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F_{j}\subseteq\mathbf{A}_{\sigma_{j}}\right)$
$\displaystyle=\prod\limits_{j\in f\left(V\right)}\left(\text{\\# of
}\sigma\in\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F_{j}\subseteq\mathbf{A}_{\sigma}\right)$ (17) $\displaystyle\ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \left(\text{here, we have renamed the index
}\sigma_{j}\text{ as }\sigma\right).$

Thus, (12) becomes

$\displaystyle\sum\limits_{F\subseteq A_{f}\text{ is
linear}}\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\# of
}\sigma\in\mathfrak{S}_{V}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\text{ and }f\circ\sigma=f\right)$
$\displaystyle=\sum\limits_{\begin{subarray}{c}\left(F_{j}\right)_{j\in
f\left(V\right)}\text{ is a family}\\\ \text{of linear subsets }F_{j}\subseteq
A_{j}\end{subarray}}\ \
\underbrace{\left(-1\right)^{\left|\bigsqcup\limits_{j\in
f\left(V\right)}F_{j}\right|}}_{\begin{subarray}{c}=\left(-1\right)^{\sum\limits_{j\in
f\left(V\right)}\left|F_{j}\right|}\\\ =\prod\limits_{j\in
f\left(V\right)}\left(-1\right)^{\left|F_{j}\right|}\end{subarray}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \cdot\underbrace{\left(\text{\\# of
}\sigma\in\mathfrak{S}_{V}\text{ satisfying }\bigsqcup\limits_{j\in
f\left(V\right)}F_{j}\subseteq\mathbf{A}_{\sigma}\text{ and
}f\circ\sigma=f\right)}_{\begin{subarray}{c}=\prod\limits_{j\in
f\left(V\right)}\left(\text{\\# of
}\sigma\in\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F_{j}\subseteq\mathbf{A}_{\sigma}\right)\\\ \text{(by (\ref{pf.lem.hamps-by-
lin-f.short.6}))}\end{subarray}}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}\left(F_{j}\right)_{j\in
f\left(V\right)}\text{ is a family}\\\ \text{of linear subsets }F_{j}\subseteq
A_{j}\end{subarray}}\underbrace{\left(\prod\limits_{j\in
f\left(V\right)}\left(-1\right)^{\left|F_{j}\right|}\right)\cdot\prod\limits_{j\in
f\left(V\right)}\left(\text{\\# of
}\sigma\in\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F_{j}\subseteq\mathbf{A}_{\sigma}\right)}_{=\prod\limits_{j\in
f\left(V\right)}\left(\left(-1\right)^{\left|F_{j}\right|}\cdot\left(\text{\\#
of }\sigma\in\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F_{j}\subseteq\mathbf{A}_{\sigma}\right)\right)}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}\left(F_{j}\right)_{j\in
f\left(V\right)}\text{ is a family}\\\ \text{of linear subsets }F_{j}\subseteq
A_{j}\end{subarray}}\prod\limits_{j\in
f\left(V\right)}\left(\left(-1\right)^{\left|F_{j}\right|}\cdot\left(\text{\\#
of }\sigma\in\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F_{j}\subseteq\mathbf{A}_{\sigma}\right)\right)$
$\displaystyle=\prod\limits_{j\in f\left(V\right)}\ \
\sum\limits_{\begin{subarray}{c}F_{j}\subseteq A_{j}\text{ is
linear}\end{subarray}}\left(-1\right)^{\left|F_{j}\right|}\cdot\left(\text{\\#
of }\sigma\in\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F_{j}\subseteq\mathbf{A}_{\sigma}\right)$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \left(\text{by the product rule}\right)$
$\displaystyle=\prod\limits_{j\in f\left(V\right)}\ \
\underbrace{\sum\limits_{\begin{subarray}{c}F\subseteq A_{j}\text{ is
linear}\end{subarray}}\left(-1\right)^{\left|F\right|}\cdot\left(\text{\\# of
}\sigma\in\mathfrak{S}_{f^{-1}\left(j\right)}\text{ satisfying
}F\subseteq\mathbf{A}_{\sigma}\right)}_{\begin{subarray}{c}=\left(\text{\\# of
hamps of }\overline{D_{j}}\right)\\\ \text{(by Lemma \ref{lem.hamps-by-lin},
applied to }D_{j}=\left(f^{-1}\left(j\right),\ A_{j}\right)\text{ instead of
}D=\left(V,A\right)\text{)}\end{subarray}}$ $\displaystyle\ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \left(\text{here, we have renamed the summation index
}F_{j}\text{ as }F\right)$ $\displaystyle=\prod\limits_{j\in
f\left(V\right)}\left(\text{\\# of hamps of }\overline{D_{j}}\right).$

In view of this, we can rewrite (11) as

$\sum\limits_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{V};\\\
f\circ\sigma=f\end{subarray}}\ \
\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap A\\\
\text{is
linear}\end{subarray}}\left(-1\right)^{\left|F\right|}=\prod\limits_{j\in
f\left(V\right)}\left(\text{\\# of hamps of }\overline{D_{j}}\right).$

This proves Lemma 2.35.

###  2.7 $\left(f,D\right)$-friendly $V$-listings

The following restatement of Lemma 2.35 will be useful for us:

######  Lemma 2.37.

Let $D=\left(V,A\right)$ be a digraph. Let $f:V\rightarrow\mathbb{P}$ be any
map. A $V$-listing $v=\left(v_{1},v_{2},\ldots,v_{n}\right)$ will be called
$\left(f,D\right)$_-friendly_ if it has the properties that
$f\left(v_{1}\right)\leq f\left(v_{2}\right)\leq\cdots\leq
f\left(v_{n}\right)$ and that

$f\left(v_{p}\right)<f\left(v_{p+1}\right)\text{ for each
}p\in\left[n-1\right]\text{ satisfying }\left(v_{p},v_{p+1}\right)\in A.$ (18)

Then,

$\sum\limits_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{V};\\\
f\circ\sigma=f\end{subarray}}\ \
\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap A\\\
\text{is
linear}\end{subarray}}\left(-1\right)^{\left|F\right|}=\left(\text{\\# of
}\left(f,D\right)\text{-friendly }V\text{-listings}\right).$

######  Proof 2.38.

For each $j\in f\left(V\right)$, we define a digraph $D_{j}$ as in Definition
2.23 (c). This digraph $D_{j}$ is the restriction of the digraph $D$ to the
subset $f^{-1}\left(j\right)$. In particular, its vertex set is
$f^{-1}\left(j\right)$. In other words, its vertices are precisely those
vertices of $D$ that have level $j$ (with respect to $f$).

Clearly, a $V$-listing $v=\left(v_{1},v_{2},\ldots,v_{n}\right)$ satisfies
$f\left(v_{1}\right)\leq f\left(v_{2}\right)\leq\cdots\leq
f\left(v_{n}\right)$ if and only if it lists the vertices of $D$ in the order
of increasing level, i.e., if it first lists the vertices of the smallest
level, then the vertices of the second-smallest level, and so on.

In other words, a $V$-listing $v=\left(v_{1},v_{2},\ldots,v_{n}\right)$
satisfies $f\left(v_{1}\right)\leq f\left(v_{2}\right)\leq\cdots\leq
f\left(v_{n}\right)$ if and only if it can be constructed by choosing an
$f^{-1}\left(j\right)$-listing $v^{\left(j\right)}$ for each $j\in
f\left(V\right)$ and concatenating all these $f^{-1}\left(j\right)$-listings
$v^{\left(j\right)}$ in the order of increasing $j$. Moreover, if it can be
constructed in this way, then its construction is unique (i.e., each
$v^{\left(j\right)}$ is determined uniquely by $v$). Finally, for a
$V$-listing $v$ that is written as a concatenation of such
$f^{-1}\left(j\right)$-listings $v^{\left(j\right)}$, the condition (18) is
equivalent to the condition that each $v^{\left(j\right)}$ is a hamp of
$\overline{D_{j}}$ (indeed, this is easiest to see by rewriting (18) in the
contrapositive form “if $p\in\left[n-1\right]$ satisfies
$f\left(v_{p}\right)=f\left(v_{p+1}\right)$, then
$\left(v_{p},v_{p+1}\right)\notin A$”). Thus, a $V$-listing
$v=\left(v_{1},v_{2},\ldots,v_{n}\right)$ satisfies both
$f\left(v_{1}\right)\leq f\left(v_{2}\right)\leq\cdots\leq
f\left(v_{n}\right)$ and (18) at the same time if and only if it can be
constructed by choosing a hamp of $\overline{D_{j}}$ for each $j\in
f\left(V\right)$ and concatenating all these hamps in the order of increasing
$j$. In other words, a $V$-listing $v$ is $\left(f,D\right)$-friendly if and
only if it can be constructed in this way. Since this construction is unique,
we thus have

$\left(\text{\\# of }\left(f,D\right)\text{-friendly
}V\text{-listings}\right)=\prod\limits_{j\in f\left(V\right)}\left(\text{\\#
of hamps of }\overline{D_{j}}\right).$

Thus, Lemma 2.37 follows from Lemma 2.35.

###  2.8 A bit of Pólya counting

The following lemma is well-known, e.g., from the theory of Pólya enumeration:

######  Lemma 2.39.

Let $V$ be a finite set. Let $\sigma\in\mathfrak{S}_{V}$ be a permutation of
$V$. Then,

$\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{P}\text{;}\\\
f\circ\sigma=f\end{subarray}}\ \ \prod\limits_{v\in
V}x_{f\left(v\right)}=p_{\operatorname*{type}\sigma}.$

######  Proof 2.40.

Let $\gamma_{1},\gamma_{2},\ldots,\gamma_{k}$ be the cycles of $\sigma$,
listed with no repetition. For each $i\in\left[k\right]$, let $V_{i}$ be the
set of entries of the cycle $\gamma_{i}$. Thus, $V=V_{1}\sqcup
V_{2}\sqcup\cdots\sqcup V_{k}$. For each $i\in\left[k\right]$, the set $V_{i}$
is the set of entries of a cycle of $\sigma$ (namely, of $\gamma_{i}$), and
thus can be written as $\left\\{\sigma^{j}\left(v_{i}\right)\ \mid\
j\in\mathbb{N}\right\\}$ for some $v_{i}\in V_{i}$.

Hence, a map $f:V\rightarrow\mathbb{P}$ satisfies $f\circ\sigma=f$ if and only
if $f$ is constant on each of the $k$ sets $V_{1},V_{2},\ldots,V_{k}$. Hence,
in order to construct a map $f:V\rightarrow\mathbb{P}$ that satisfies
$f\circ\sigma=f$, we only need to choose the values $a_{1},a_{2},\ldots,a_{k}$
that it takes on these $k$ sets (i.e., for each $i\in\left[k\right]$, we need
to choose the value $a_{i}$ that $f$ takes on all elements of $V_{i}$).

Let us be more precise: For each $k$-tuple
$\left(a_{1},a_{2},\ldots,a_{k}\right)\in\mathbb{P}^{k}$, there is a unique
map $\Gamma\left(a_{1},a_{2},\ldots,a_{k}\right):V\rightarrow\mathbb{P}$ that
sends each element of $V_{1}$ to $a_{1}$, each element of $V_{2}$ to $a_{2}$,
and so on (since $V=V_{1}\sqcup V_{2}\sqcup\cdots\sqcup V_{k}$). The latter
map $\Gamma\left(a_{1},a_{2},\ldots,a_{k}\right)$ is a map
$f:V\rightarrow\mathbb{P}$ that satisfies $f\circ\sigma=f$ (by the preceding
paragraph, since it is constant on each of the $k$ sets
$V_{1},V_{2},\ldots,V_{k}$). Thus, we obtain a map

$\displaystyle\Gamma:\mathbb{P}^{k}$
$\displaystyle\rightarrow\left\\{f:V\rightarrow\mathbb{P}\ \mid\
f\circ\sigma=f\right\\},$ $\displaystyle\left(a_{1},a_{2},\ldots,a_{k}\right)$
$\displaystyle\mapsto\Gamma\left(a_{1},a_{2},\ldots,a_{k}\right).$

This map $\Gamma$ is easily seen to be injective (since
$V_{1},V_{2},\ldots,V_{k}$ are nonempty) and surjective (again by the previous
paragraph). Hence, it is bijective. Thus, substituting
$\Gamma\left(a_{1},a_{2},\ldots,a_{k}\right)$ for $f$ in the sum
$\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{P}\text{;}\\\
f\circ\sigma=f\end{subarray}}\ \ \prod\limits_{v\in V}x_{f\left(v\right)}$, we
obtain

$\displaystyle\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{P}\text{;}\\\
f\circ\sigma=f\end{subarray}}\ \ \prod\limits_{v\in V}x_{f\left(v\right)}$
$\displaystyle=\sum\limits_{\left(a_{1},a_{2},\ldots,a_{k}\right)\in\mathbb{P}^{k}}\
\ \underbrace{\prod\limits_{v\in
V}}_{\begin{subarray}{c}=\prod\limits_{i=1}^{k}\ \ \prod\limits_{v\in
V_{i}}\\\ \text{(since }V=V_{1}\sqcup V_{2}\sqcup\cdots\sqcup
V_{k}\text{)}\end{subarray}}x_{\left(\Gamma\left(a_{1},a_{2},\ldots,a_{k}\right)\right)\left(v\right)}$
$\displaystyle=\sum\limits_{\left(a_{1},a_{2},\ldots,a_{k}\right)\in\mathbb{P}^{k}}\
\ \prod\limits_{i=1}^{k}\ \ \prod\limits_{v\in
V_{i}}\underbrace{x_{\left(\Gamma\left(a_{1},a_{2},\ldots,a_{k}\right)\right)\left(v\right)}}_{\begin{subarray}{c}{}_{\begin{subarray}{c}=x_{a_{i}}\end{subarray}}\\\
\text{(since the map }\Gamma\left(a_{1},a_{2},\ldots,a_{k}\right)\\\
\text{sends each element of }V_{i}\text{ to }a_{i}\text{)}\end{subarray}}$
$\displaystyle=\sum\limits_{\left(a_{1},a_{2},\ldots,a_{k}\right)\in\mathbb{P}^{k}}\
\ \prod\limits_{i=1}^{k}\ \ \underbrace{\prod\limits_{v\in
V_{i}}x_{a_{i}}}_{=x_{a_{i}}^{\left|V_{i}\right|}}=\sum\limits_{\left(a_{1},a_{2},\ldots,a_{k}\right)\in\mathbb{P}^{k}}\
\ \prod\limits_{i=1}^{k}x_{a_{i}}^{\left|V_{i}\right|}$
$\displaystyle=\prod\limits_{i=1}^{k}\ \
\underbrace{\sum\limits_{a\in\mathbb{P}}x_{a}^{\left|V_{i}\right|}}_{\begin{subarray}{c}=x_{1}^{\left|V_{i}\right|}+x_{2}^{\left|V_{i}\right|}+x_{3}^{\left|V_{i}\right|}+\cdots\\\
=p_{\left|V_{i}\right|}\\\ \text{(by the definition of
}p_{\left|V_{i}\right|}\text{)}\end{subarray}}\ \ \ \ \ \ \ \ \ \
\left(\text{by the product rule}\right)$
$\displaystyle=\prod\limits_{i=1}^{k}p_{\left|V_{i}\right|}.$ (19)

However, the permutation $\sigma$ has cycles
$\gamma_{1},\gamma_{2},\ldots,\gamma_{k}$, and their respective sets of
entries are $V_{1},V_{2},\ldots,V_{k}$. Thus, the lengths of the cycles of
$\sigma$ are
$\left|V_{1}\right|,\left|V_{2}\right|,\ldots,\left|V_{k}\right|$. But the
entries of the partition $\operatorname*{type}\sigma$ are precisely the
lengths of the cycles of $\sigma$ (by the definition of
$\operatorname*{type}\sigma$), and thus must be
$\left|V_{1}\right|,\left|V_{2}\right|,\ldots,\left|V_{k}\right|$ in some
order (by the preceding sentence). Therefore, the partition
$\operatorname*{type}\sigma$ can be obtained from the $k$-tuple
$\left(\left|V_{1}\right|,\left|V_{2}\right|,\ldots,\left|V_{k}\right|\right)$
by sorting the entries in weakly decreasing order. Hence,

$p_{\operatorname*{type}\sigma}=\prod\limits_{i=1}^{k}p_{\left|V_{i}\right|}.$

Comparing this with (19), we obtain

$\sum\limits_{\begin{subarray}{c}f:V\rightarrow\mathbb{P}\text{;}\\\
f\circ\sigma=f\end{subarray}}\ \ \prod\limits_{v\in
V}x_{f\left(v\right)}=p_{\operatorname*{type}\sigma}.$

This proves Lemma 2.39.

###  2.9 A final alternating sum

We need one more alternating-sum identity:

######  Proposition 2.41.

Let $D=\left(V,A\right)$ be a digraph. Let $\sigma\in\mathfrak{S}_{V}$ be a
permutation of $V$. Then,

$\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap A\\\
\text{is
linear}\end{subarray}}\left(-1\right)^{\left|F\right|}=\begin{cases}\left(-1\right)^{\varphi\left(\sigma\right)},&\text{if
}\sigma\in\mathfrak{S}_{V}\left(D,\overline{D}\right);\\\
0,&\text{else,}\end{cases}$

where we set

$\varphi\left(\sigma\right):=\sum\limits_{\begin{subarray}{c}\gamma\in\operatorname*{Cycs}\sigma;\\\
\gamma\text{ is a
}D\text{-cycle}\end{subarray}}\left(\ell\left(\gamma\right)-1\right).$

######  Proof 2.42.

Let us first prove the proposition in the case when $\sigma$ has only one
cycle. That is, we shall first prove the following claim:

> Claim 1: Assume that $\sigma$ has a unique cycle $\gamma$. Then,
>
> $\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap A\\\
> \text{is
> linear}\end{subarray}}\left(-1\right)^{\left|F\right|}=\begin{cases}\left(-1\right)^{\ell\left(\gamma\right)-1},&\text{if
> }\gamma\text{ is a }D\text{-cycle;}\\\ 1,&\text{if }\gamma\text{ is a
> }\overline{D}\text{-cycle;}\\\ 0,&\text{else.}\end{cases}$

[Proof of Claim 1: We have assumed that $\sigma$ has a unique cycle $\gamma$.
Thus, $\mathbf{A}_{\sigma}=\operatorname*{CArcs}\gamma$. Hence, each proper
subset of $\mathbf{A}_{\sigma}$ is linear888since the removal of any cyclic
arc from a cycle turns the cycle into a path, and the removal of any further
arcs will break this path into smaller paths, but $\mathbf{A}_{\sigma}$ itself
is not999since the digraph $\left(V,\mathbf{A}_{\sigma}\right)$ has the cycle
$\gamma$. Furthermore, we have
$\left|\mathbf{A}_{\sigma}\right|=\left|\operatorname*{CArcs}\gamma\right|=\ell\left(\gamma\right)$.

The sum $\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap
A\\\ \text{is linear}\end{subarray}}\left(-1\right)^{\left|F\right|}$ depends
on whether $\gamma$ is a $D$-cycle, a $\overline{D}$-cycle or neither:

  * •

If $\gamma$ is a $D$-cycle, then all arcs in $\mathbf{A}_{\sigma}$ belong to
$A$, and therefore we have $\mathbf{A}_{\sigma}\cap A=\mathbf{A}_{\sigma}$.
Thus, in this case, we have

$\displaystyle\left\\{\text{linear subsets of }\mathbf{A}_{\sigma}\cap
A\right\\}$ $\displaystyle=\left\\{\text{linear subsets of
}\mathbf{A}_{\sigma}\right\\}=\left\\{\text{proper subsets of
}\mathbf{A}_{\sigma}\right\\}$

(since each proper subset of $\mathbf{A}_{\sigma}$ is linear, but
$\mathbf{A}_{\sigma}$ itself is not). Hence, in this case, we have

$\displaystyle\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap
A\\\ \text{is linear}\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\\\
\text{is a proper
subset}\end{subarray}}\left(-1\right)^{\left|F\right|}=\underbrace{\sum\limits_{F\subseteq\mathbf{A}_{\sigma}}\left(-1\right)^{\left|F\right|}}_{\begin{subarray}{c}=0\\\
\text{(by Lemma \ref{lem.cancel},}\\\ \text{since
}\mathbf{A}_{\sigma}\neq\varnothing\text{)}\end{subarray}}-\left(-1\right)^{\left|\mathbf{A}_{\sigma}\right|}$
$\displaystyle=-\left(-1\right)^{\left|\mathbf{A}_{\sigma}\right|}=\left(-1\right)^{\left|\mathbf{A}_{\sigma}\right|-1}$
$\displaystyle=\left(-1\right)^{\ell\left(\gamma\right)-1}\ \ \ \ \ \ \ \ \ \
\left(\text{since
}\left|\mathbf{A}_{\sigma}\right|=\ell\left(\gamma\right)\right).$

  * •

If $\gamma$ is a $\overline{D}$-cycle, then no arcs in $\mathbf{A}_{\sigma}$
belong to $A$, and therefore we have $\mathbf{A}_{\sigma}\cap A=\varnothing$.
Thus, in this case, we have

$\left\\{\text{linear subsets of }\mathbf{A}_{\sigma}\cap
A\right\\}=\left\\{\text{linear subsets of
}\varnothing\right\\}=\left\\{\varnothing\right\\}.$

Hence, in this case, the sum
$\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap A\\\
\text{is linear}\end{subarray}}\left(-1\right)^{\left|F\right|}$ has only one
addend, namely the addend corresponding to $F=\varnothing$. Thus, this sum
equals $1$ in this case.

  * •

If $\gamma$ is neither a $D$-cycle nor a $\overline{D}$-cycle, then we have
$\mathbf{A}_{\sigma}\cap A\neq\varnothing$ (since $\mathbf{A}_{\sigma}\cap
A=\varnothing$ would imply that $\mathbf{A}_{\sigma}\subseteq\left(V\times
V\right)\setminus A$, whence
$\operatorname*{CArcs}\gamma=\mathbf{A}_{\sigma}\subseteq\left(V\times
V\right)\setminus A$; but this would mean that $\gamma$ is a
$\overline{D}$-cycle) and $\mathbf{A}_{\sigma}\not\subseteq A$ (since
$\mathbf{A}_{\sigma}\subseteq A$ would mean that $\gamma$ is a $D$-cycle).
Hence, in this case, any $F\subseteq\mathbf{A}_{\sigma}\cap A$ is a proper
subset of $\mathbf{A}_{\sigma}$ (since $\mathbf{A}_{\sigma}\not\subseteq A$
shows that $\mathbf{A}_{\sigma}\cap A$ is a proper subset of
$\mathbf{A}_{\sigma}$) and therefore linear (since each proper subset of
$\mathbf{A}_{\sigma}$ is linear). Thus, in this case, we have

$\displaystyle\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap
A\\\ \text{is linear}\end{subarray}}\left(-1\right)^{\left|F\right|}$
$\displaystyle=\sum\limits_{F\subseteq\mathbf{A}_{\sigma}\cap
A}\left(-1\right)^{\left|F\right|}=\left[\mathbf{A}_{\sigma}\cap
A=\varnothing\right]\ \ \ \ \ \ \ \ \ \ \left(\text{by Lemma
\ref{lem.cancel}}\right)$ $\displaystyle=0\ \ \ \ \ \ \ \ \ \
\left(\text{since }\mathbf{A}_{\sigma}\cap A\neq\varnothing\right).$

Combining these three cases, we see that

$\sum\limits_{\begin{subarray}{c}F\subseteq\mathbf{A}_{\sigma}\cap A\\\
\text{is
linear}\end{subarray}}\left(-1\right)^{\left|F\right|}=\begin{cases}\left(-1\right)^{\ell\left(\gamma\right)-1},&\text{if
}\gamma\text{ is a }D\text{-cycle;}\\\ 1,&\text{if }\gamma\text{ is a
}\overline{D}\text{-cycle;}\\\ 0,&\text{else.}\end{cases}$

This proves Claim 1.]

Let us now prove Proposition 2.41 in the general case. Let
$\gamma_{1},\gamma_{2},\ldots,\gamma_{k}$ be the cycles of $\sigma$, listed
with no repetition. Thus, these cycles
$\gamma_{1},\gamma_{2},\ldots,\gamma_{k}$ are distinct, and we have
$\operatorname*{Cycs}\sigma=\left\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{k}\right\\}$.

For each $i\in\left[k\right]$, let $V_{i}$ be the set of entries of the cycle