\documentclass[numbers=enddot,14pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=true]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{color}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, August 17, 2023 13:08:13}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newcommand{\arinj}{\ar@{_{(}->}}
\newcommand{\arinjrev}{\ar@{^{(}->}}
\newcommand{\arsurj}{\ar@{->>}}
\newcommand{\arelem}{\ar@{|->}}
\newcommand{\arback}{\ar@{<-}}
\newcommand{\id}{\operatorname{id}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\DeclareMathOperator{\osc}{OSC}
\DeclareMathOperator{\rtb}{R2B}
\DeclareMathOperator{\uosc}{UOSC}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\green}[1]{\textcolor{green!50!black}{#1}}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{\node[shape=circle,fill,inner sep=2pt] (char) {\textcolor{white}{#1}};}}
\newcommand{\icast}{\circled{$\ast$}}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{25cm}
\setlength\textwidth{15.5cm}
\newenvironment{noncompile}{}{}
\excludecomment{noncompile}
\ihead{The Redei--Berge symmetric function (talk)}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{The Redei--Berge symmetric function of a directed graph [talk slides]}
\date{The IPAC (Important Papers in Algebraic Combinatorics) Seminar, 2023-08-15}
\author{Darij Grinberg
\and joint work with Richard P. Stanley}
\maketitle

\begin{abstract}
{\small In 1934, Laszlo Redei observed a peculiar property of tournaments
(directed graphs that have an arc between every pair of distinct vertices):
Each tournament has an odd number of Hamiltonian paths. In 1996, Chow
introduced the ``path-cycle symmetric function'' of a directed graph, a
symmetric function in two sets of arguments, which was later used in rook
theory. We study Chow's symmetric function in the case when the y-variables
are 0. In this case, we give new nontrivial expansions of the function in
terms of the power-sum basis; in particular, we find that it is p-positive as
long as the directed graph has no 2-cycles. We use our expansions to reprove
Redei's theorem and refine it to a mod-4 congruence. }

{\small This is joint work with Richard P. Stanley. }

\end{abstract}

\newpage

\section*{***}

Preprint:

\begin{itemize}
\item Darij Grinberg and Richard P. Stanley, \textit{The Redei--Berge
symmetric function of a directed graph},
\href{https://arxiv.org/abs/2307.05569}{arXiv:2307.05569}.
\end{itemize}

Slides of this talk:

\begin{itemize}
\item \url{https://www.cip.ifi.lmu.de/~grinberg/algebra/ipac2023a.pdf}
\end{itemize}

\begin{noncompile}
Items marked with $\circled{$\ast$}$ are more important.
\end{noncompile}

\newpage

\section{Digraphs and tournaments}

\begin{itemize}
\item \textbf{Definition.} A \textbf{digraph} (short for \textquotedblleft
directed graph\textquotedblright) means a pair $\left(  V,A\right)  $ of a
finite set $V$ and a subset $A\subseteq V\times V$.

The elements $\left(  u,v\right)  \in A$ are called \textbf{arcs} of this
digraph, and are drawn accordingly.

We allow loops ($\left(  u,u\right)  \in A$) and antiparallel arcs ($\left(
u,v\right)  \in A$ and $\left(  v,u\right)  \in A$) but not parallel arcs ($A$
is not a multiset).

\item \textbf{Definition.} Let $D=\left(  V,A\right)  $ be a digraph. Then,
$\overline{D}$ denotes the \textbf{complement} of $D$; this is the digraph
$\left(  V,\ \left(  V\times V\right)  \setminus A\right)  $. Its arcs are the
\textbf{non-arcs} of $D$.

\item \textbf{Example.}%
\begin{align*}
\text{If }D  &  =\left(  \left\{  1,2,3\right\}  ,\ \left\{  \left(
1,2\right)  ,\ \left(  2,2\right)  ,\ \left(  3,3\right)  \right\}  \right)
,\\
\text{then }\overline{D}  &  =\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)  .
\end{align*}%
\[%
\begin{tabular}
[c]{|c|c|}\hline
$%
%TCIMACRO{\TeXButton{tikz D}{\begin{tikzpicture}
%\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0:1.5) {$1$};
%\node(2) at (120:1.5) {$2$};
%\node(3) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (1) edge (2) (2) edge[loop left] (2) (3) edge[loop left] (3);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0:1.5) {$1$};
\node(2) at (120:1.5) {$2$};
\node(3) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (1) edge (2) (2) edge[loop left] (2) (3) edge[loop left] (3);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz Dprime}{\begin{tikzpicture}
%\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0:1.5) {$1$};
%\node(2) at (120:1.5) {$2$};
%\node(3) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=red,line width=1.7pt}]
%\path[->] (1) edge[loop right] (1) edge[bend left=20] (3);
%\path[->] (2) edge (1) edge[bend left=20] (3);
%\path[->] (3) edge[bend left=20] (1) edge[bend left=20] (2);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0:1.5) {$1$};
\node(2) at (120:1.5) {$2$};
\node(3) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=red,line width=1.7pt}]
\path[->] (1) edge[loop right] (1) edge[bend left=20] (3);
\path[->] (2) edge (1) edge[bend left=20] (3);
\path[->] (3) edge[bend left=20] (1) edge[bend left=20] (2);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$\\
$D$ & $\overline{D}$\\\hline
\end{tabular}
\]


\item \textbf{Definition.} A digraph $D=\left(  V,A\right)  $ is
\textbf{loopless} if it has no loops (i.e., no arcs $\left(  u,u\right)  $).

\item \textbf{Definition.} A loopless digraph $D=\left(  V,A\right)  $ is a
\textbf{tournament} if it has the following property: For any distinct $u,v\in
V$, exactly one of the two pairs $\left(  u,v\right)  $ and $\left(
v,u\right)  $ is an arc of $D$.

In other words, a tournament is an orientation of the complete undirected
graph $K_{V}$.

\item \textbf{Examples.}
\[%
\begin{tabular}
[c]{|c|c|c|c|}\hline
$%
%TCIMACRO{\TeXButton{tikz 3-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0:1.5) {$1$};
%\node(B) at (120:1.5) {$2$};
%\node(C) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (A) edge (B) (B) edge (C) (A) edge (C);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0:1.5) {$1$};
\node(B) at (120:1.5) {$2$};
\node(C) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (A) edge (B) (B) edge (C) (A) edge (C);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz 3-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0:1.5) {$1$};
%\node(B) at (120:1.5) {$2$};
%\node(C) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (A) edge (B) (B) edge (C) (C) edge (A);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0:1.5) {$1$};
\node(B) at (120:1.5) {$2$};
\node(C) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (A) edge (B) (B) edge (C) (C) edge (A);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz 3-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0:1.5) {$1$};
%\node(B) at (120:1.5) {$2$};
%\node(C) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (A) edge (B) (B) edge (C);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0:1.5) {$1$};
\node(B) at (120:1.5) {$2$};
\node(C) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (A) edge (B) (B) edge (C);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz 3-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0:1.5) {$1$};
%\node(B) at (120:1.5) {$2$};
%\node(C) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (B) edge (C);
%\path[->] (A) edge[bend left=20] (B);
%\path[->] (B) edge[bend left=20] (A);
%\path[->] (C) edge[bend left=10] (A);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0:1.5) {$1$};
\node(B) at (120:1.5) {$2$};
\node(C) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (B) edge (C);
\path[->] (A) edge[bend left=20] (B);
\path[->] (B) edge[bend left=20] (A);
\path[->] (C) edge[bend left=10] (A);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$\\
tournament & tournament & not tournament & not tournament\\\hline
\end{tabular}
\]

\end{itemize}

\newpage

\section{Hamiltonian paths and R\'{e}dei's and Berge's theorems}

\begin{itemize}
\item \textbf{Definition.} Let $V$ be a finite set. A $V$\textbf{-listing}
will mean a list of elements of $V$ that contains each element of $V$ exactly once.

\item \textbf{Definition.} Let $D=\left(  V,A\right)  $ be a digraph. A
\textbf{Hamiltonian path} (short: \textbf{hamp}) of $D$ means a $V$-listing
$\left(  v_{1},v_{2},\ldots,v_{n}\right)  $ such that
\[
\left(  v_{i},v_{i+1}\right)  \in A\ \ \ \ \ \ \ \ \ \ \text{for each }%
i\in\left\{  1,2,\ldots,n-1\right\}  .
\]


In other words (for $V\neq\varnothing$), it means a path of $D$ that contains
each vertex.

\item \textbf{Easy proposition (R\'{e}dei 1933):} Any tournament has a hamp.

\item This is an easy exercise in graph theory. But R\'{e}dei proved a lot more:

\item \textbf{Theorem (R\'{e}dei 1933):} Let $D$ be a tournament. Then,%
\[
\left(  \text{\# of hamps of }D\right)  \text{ is odd.}%
\]


\item \textbf{Example.} Here are some tournaments:%
\[%
\begin{tabular}
[c]{|c|c|c|c|}\hline
$%
%TCIMACRO{\TeXButton{tikz 3-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0:1.5) {$1$};
%\node(B) at (120:1.5) {$2$};
%\node(C) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (A) edge (B) (B) edge (C) (A) edge (C);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0:1.5) {$1$};
\node(B) at (120:1.5) {$2$};
\node(C) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (A) edge (B) (B) edge (C) (A) edge (C);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz 3-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0:1.5) {$1$};
%\node(B) at (120:1.5) {$2$};
%\node(C) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (A) edge (B) (B) edge (C) (C) edge (A);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0:1.5) {$1$};
\node(B) at (120:1.5) {$2$};
\node(C) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (A) edge (B) (B) edge (C) (C) edge (A);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz 4-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0:1.5) {$1$};
%\node(B) at (90:1.5) {$2$};
%\node(C) at (180:1.5) {$3$};
%\node(D) at (270:1.5) {$4$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path
%[->] (A) edge (B) (B) edge (C) (C) edge (D) (D) edge (A) (A) edge (C) (B) edge (D);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0:1.5) {$1$};
\node(B) at (90:1.5) {$2$};
\node(C) at (180:1.5) {$3$};
\node(D) at (270:1.5) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path
[->] (A) edge (B) (B) edge (C) (C) edge (D) (D) edge (A) (A) edge (C) (B) edge (D);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz 5-vertex tournament}{\begin{tikzpicture}[scale=0.8]
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0*360/5 : 2) {$1$};
%\node(2) at (1*360/5 : 2) {$2$};
%\node(3) at (2*360/5 : 2) {$3$};
%\node(4) at (3*360/5 : 2) {$4$};
%\node(5) at (4*360/5 : 2) {$5$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (1) edge (2) edge (4) edge (5);
%\path[->] (2) edge (5);
%\path[->] (3) edge (1) edge (2);
%\path[->] (4) edge (2) edge (3) edge (5);
%\path[->] (5) edge (3);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.8]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0*360/5 : 2) {$1$};
\node(2) at (1*360/5 : 2) {$2$};
\node(3) at (2*360/5 : 2) {$3$};
\node(4) at (3*360/5 : 2) {$4$};
\node(5) at (4*360/5 : 2) {$5$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (1) edge (2) edge (4) edge (5);
\path[->] (2) edge (5);
\path[->] (3) edge (1) edge (2);
\path[->] (4) edge (2) edge (3) edge (5);
\path[->] (5) edge (3);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$\\
has $1$ hamp: & has $3$ hamps: & has $5$ hamps: & has $9$ hamps:\\
$\left(  1,2,3\right)  $ & e.g., $\left(  2,3,1\right)  $ & e.g., $\left(
1,2,3,4\right)  $ & e.g., $\left(  1,4,2,5,3\right)  $\\\hline
\end{tabular}
\]


\item R\'{e}dei's proof is complicated and intransparent (see
\href{https://www.gutenberg.org/ebooks/42833}{Moon, \textit{Topics on
Tournaments}} for an English version).

To give a more conceptual proof, Berge discovered the following:

\item \textbf{Theorem (Berge 1976):} Let $D$ be a digraph. Then,%
\[
\left(  \text{\# of hamps of }\overline{D}\right)  \equiv\left(  \text{\# of
hamps of }D\right)  \operatorname{mod}2.
\]


\item \textbf{Example.}
\[%
\begin{tabular}
[c]{|c|c|}\hline
$%
%TCIMACRO{\TeXButton{tikz 3-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0,0) {$1$};
%\node(B) at (2,-1) {$2$};
%\node(C) at (4,0) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (B) edge (C);
%\path[->] (A) edge[bend left=20] (B);
%\path[->] (B) edge[bend left=20] (A);
%\path[->] (C) edge[bend right=40] (A);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0,0) {$1$};
\node(B) at (2,-1) {$2$};
\node(C) at (4,0) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (B) edge (C);
\path[->] (A) edge[bend left=20] (B);
\path[->] (B) edge[bend left=20] (A);
\path[->] (C) edge[bend right=40] (A);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz 3-digraph}{\begin{tikzpicture}
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(A) at (0,0) {$1$};
%\node(B) at (2,-1) {$2$};
%\node(C) at (4,0) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=red,line width=1.7pt}]
%\path[->] (A) edge[loop left] (A);
%\path[->] (B) edge[loop left] (B);
%\path[->] (C) edge[loop right] (C);
%\path[->] (C) edge (B);
%\path[->] (A) edge[bend left=30] (C);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0,0) {$1$};
\node(B) at (2,-1) {$2$};
\node(C) at (4,0) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=red,line width=1.7pt}]
\path[->] (A) edge[loop left] (A);
\path[->] (B) edge[loop left] (B);
\path[->] (C) edge[loop right] (C);
\path[->] (C) edge (B);
\path[->] (A) edge[bend left=30] (C);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$\\
$D$ & $\overline{D}$\\\hline
has $3$ hamps & has $1$ hamp\\\hline
\end{tabular}
\]
(loops don't actually matter, but I draw them to be fully correct).

\item Berge proves his theorem (in his \textit{Graphs} textbook) using an
elegant inclusion-exclusion argument.

Then he uses his theorem to prove R\'{e}dei's theorem via induction on the
number of \textquotedblleft inversions\textquotedblright\ (arcs directed the
\textquotedblleft wrong way\textquotedblright).

This proof is much cleaner than R\'{e}dei's, but still far from simple.

For a detailed exposition, see
\url{https://www.cip.ifi.lmu.de/~grinberg/t/17s/5707lec7.pdf} .

\item \textbf{Remark.} Can we improve on R\'{e}dei's theorem even further?

\href{https://mathoverflow.net/questions/232751/the-number-of-hamiltonian-paths-in-a-tournament}{MathOverflow
question \#232751} asks for the possible values of $\left(  \text{\# of hamps
of }D\right)  $ for a tournament $D$.

Among the numbers between $1$ and $80555$, the answer is \textquotedblleft all
odd numbers except for $7$ and $21$\textquotedblright\ (proved by bof and
Gordon Royle).

\textbf{Question:} Are these the only exceptions?
\end{itemize}

\newpage

\section{The R\'{e}dei--Berge symmetric function}

\begin{itemize}
\item Independently, \href{http://timothychow.net/pathcycle.pdf}{Chow
(\textit{The Path-Cycle Symmetric Function of a Digraph}, 1996)} introduced a
symmetric function assigned to each digraph $D$.

(This was inspired by Chung/Graham's cover polynomial in rook theory.)

\item We only discuss a coarsening of his construction (Chow has two families
of variables, and we set the second family to $0$).

\textbf{Question:} Which of the results below can be generalized to the full version?

\item \textbf{Definition.} Let $n\in\mathbb{N}$, and let $I$ be a subset of
$\left\{  1,2,\ldots,n-1\right\}  $. Then, we define the power series%
\[
L_{I,n}:=\sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq i_{n};\\i_{p}%
<i_{p+1}\text{ for each }p\in I}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}%
\in\mathbb{Z}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]
\]
(where the summation indices $i_{1},i_{2},\ldots,i_{n}$ range over $\left\{
1,2,3,\ldots\right\}  $).

\textbf{Remark:} This is a \textbf{(Gessel's) fundamental quasisymmetric
function}.

\item \textbf{Definition.} Let $n\in\mathbb{N}$. Let $D=\left(  V,A\right)  $
be a digraph with $n$ vertices. We define the \textbf{Redei--Berge symmetric
function}%
\[
U_{D}:=\sum_{w\text{ is a }V\text{-listing}}L_{\operatorname*{Des}\left(
w,D\right)  ,\ n}\in\mathbb{Z}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]
\right]  ,
\]
where%
\begin{align*}
\operatorname*{Des}\left(  w,D\right)   &  :=\left\{  i\in\left\{
1,2,\ldots,n-1\right\}  \ \mid\ \left(  w_{i},w_{i+1}\right)  \in A\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \text{for each }V\text{-listing }w=\left(  w_{1}%
,w_{2},\ldots,w_{n}\right)  .
\end{align*}


\item \textbf{Example:} Let%
\[
D=%
%TCIMACRO{\TeXButton{tikz D}{\begin{tikzpicture}
%\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0:1.5) {$1$};
%\node(2) at (120:1.5) {$2$};
%\node(3) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (1) edge (2) (2) edge[loop left] (2) (3) edge[loop left] (3);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0:1.5) {$1$};
\node(2) at (120:1.5) {$2$};
\node(3) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (1) edge (2) (2) edge[loop left] (2) (3) edge[loop left] (3);
\end{scope}
\end{tikzpicture}%
%EndExpansion
\ \ .
\]
Then,%
\begin{align*}
U_{D}  &  =\sum_{w\text{ is a }V\text{-listing}}L_{\operatorname*{Des}\left(
w,D\right)  ,\ 3}\\
&  =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}\\
&  \ \ \ \ \ \ \ \ \ \ +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}\\
&  =L_{\left\{  1\right\}  ,\ 3}+L_{\varnothing,\ 3}+L_{\varnothing
,\ 3}+L_{\varnothing,\ 3}+L_{\left\{  2\right\}  ,\ 3}+L_{\varnothing,\ 3}\\
&  =4\cdot\underbrace{L_{\varnothing,\ 3}}_{=\sum_{i_{1}\leq i_{2}\leq i_{3}%
}x_{i_{1}}x_{i_{2}}x_{i_{3}}}+\underbrace{L_{\left\{  1\right\}  ,\ 3}}%
_{=\sum_{i_{1}<i_{2}\leq i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}}%
+\underbrace{L_{\left\{  2\right\}  ,\ 3}}_{=\sum_{i_{1}\leq i_{2}<i_{3}%
}x_{i_{1}}x_{i_{2}}x_{i_{3}}}\\
&  =4\cdot\sum_{i_{1}\leq i_{2}\leq i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}%
+\sum_{i_{1}<i_{2}\leq i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}+\sum_{i_{1}\leq
i_{2}<i_{3}}x_{i_{1}}x_{i_{2}}x_{i_{3}}.
\end{align*}


\item We can restate the definition of $U_{D}$ directly as follows:

\item \textbf{Proposition.} Let $D=\left(  V,A\right)  $ be a digraph with $n$
vertices. Then,%
\[
U_{D}=\sum_{f:V\rightarrow\left\{  1,2,3,\ldots\right\}  }a_{D,f}\prod_{v\in
V}x_{f\left(  v\right)  },
\]
where $a_{D,f}$ is the \# of all $V$-listings $w=\left(  w_{1},w_{2}%
,\ldots,w_{n}\right)  $ such that

\begin{itemize}
\item we have $f\left(  w_{1}\right)  \leq f\left(  w_{2}\right)  \leq
\cdots\leq f\left(  w_{n}\right)  $;

\item we have $f\left(  w_{i}\right)  <f\left(  w_{i+1}\right)  $ if $\left(
w_{i},w_{i+1}\right)  \in A$.
\end{itemize}

\item This is similar (though not directly related) to $P$-partition
enumerators and chromatic symmetric functions.

\item \textbf{Remark.} We can restate the definition of $a_{D,f}$ in nicer
terms. Namely, fix a digraph $D=\left(  V,A\right)  $ and a map
$f:V\rightarrow\left\{  1,2,3,\ldots\right\}  $. For any $j\in f\left(
V\right)  $, let $\overline{D_{j}}$ denote the induced subdigraph of the
complement $\overline{D}$ on the vertex set $f^{-1}\left(  j\right)  =\left\{
v\in V\ \mid\ f\left(  v\right)  =j\right\}  $. Then,%
\[
a_{D,f}=\prod_{j\in f\left(  V\right)  }\left(  \text{\# of hamps of
}\overline{D_{j}}\right)  .
\]
(Think of $f$ as assigning a \textquotedblleft level\textquotedblright\ to
each vertex of $D$; then $f^{-1}\left(  j\right)  $ are the level sets.)

\item Note that $U_{D}$ is $\Xi_{\overline{D}}\left(  x,0\right)  $ in the
notations of Chow's 1996 paper.

\item What is $U_{D}$ good for? Counting hamps, for one:

\item \textbf{Proposition.} Let $D$ be a digraph. Then,%
\[
U_{D}\left(  1,0,0,0,\ldots\right)  =\left(  \text{\# of hamps of }%
\overline{D}\right)  .
\]


\item Thus, any results about $U_{D}$ might give us information about the \#
of hamps!

\item Formulas for $U_{D}$ in some specific cases ($D$ acyclic, $D$ poset, $D$
path) can be found in
\href{https://math.mit.edu/~rstan/ec/ch7supp.pdf}{Additional Problem 120 to
Chapter 7 of Stanley's EC2}.
\end{itemize}

\newpage

\section{$p$-expansions: the main theorems}

\begin{itemize}
\item I called $U_{D}$ the \textquotedblleft R\'{e}dei--Berge symmetric
function\textquotedblright, but is it actually symmetric? Yes, and in fact
something better holds:

\item \textbf{Definition.} For each $k\geq1$, let%
\[
p_{k}:=x_{1}^{k}+x_{2}^{k}+x_{3}^{k}+\cdots
\]
be the $k$\textbf{-th power-sum symmetric function}.

\item \textbf{Theorem.} For any digraph $D$, we have%
\[
U_{D}\in\mathbb{Z}\left[  p_{1},p_{2},p_{3},\ldots\right]  .
\]
That is, $U_{D}$ can be written as a polynomial in $p_{1},p_{2},p_{3},\ldots$
over $\mathbb{Z}$.

\item Which polynomial, though?

\item \textbf{Definition.} Fix a digraph $D=\left(  V,A\right)  $.

Let $\mathfrak{S}_{V}$ be the symmetric group on the set $V$.

For any $\sigma\in\mathfrak{S}_{V}$, we let $\operatorname*{Cycs}\sigma$ be
the set of all cycles of $\sigma$, and we let
\[
p_{\operatorname*{type}\sigma}:=\prod_{\gamma\in\operatorname*{Cycs}\sigma
}p_{\ell\left(  \gamma\right)  },
\]
where $\ell\left(  \gamma\right)  $ denotes the length of $\gamma$. In other
words, if $\sigma$ has cycles of lengths $a,b,\ldots,k$ (including
$1$-cycles), then $p_{\operatorname*{type}\sigma}=p_{a}p_{b}\cdots p_{k}$.

We say that a cycle $\gamma$ of $\sigma$ is \textbf{a }$D$\textbf{-cycle} if
all the pairs $\left(  i,\sigma\left(  i\right)  \right)  $ for $i\in\gamma$
are arcs of $D$.

\item \textbf{Main Theorem I.} Let $D=\left(  V,A\right)  $ be a digraph. Set%
\[
\varphi\left(  \sigma\right)  :=\sum_{\substack{\gamma\in\operatorname*{Cycs}%
\sigma;\\\gamma\text{ is a }D\text{-cycle}}}\left(  \ell\left(  \gamma\right)
-1\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }\sigma\in\mathfrak{S}_{V}.
\]
Then,%
\[
U_{D}=\sum_{\substack{\sigma\in\mathfrak{S}_{V};\\\text{each cycle of }%
\sigma\text{ is}\\\text{a }D\text{-cycle or a }\overline{D}\text{-cycle}%
}}\left(  -1\right)  ^{\varphi\left(  \sigma\right)  }p_{\operatorname*{type}%
\sigma}.
\]


\item This yields the $U_{D}\in\mathbb{Z}\left[  p_{1},p_{2},p_{3}%
,\ldots\right]  $ theorem, of course.

\item \textbf{Example.} Recall our favorite example:%
\[%
\begin{tabular}
[c]{|c|c|}\hline
$%
%TCIMACRO{\TeXButton{tikz D}{\begin{tikzpicture}
%\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0:1.5) {$1$};
%\node(2) at (120:1.5) {$2$};
%\node(3) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path[->] (1) edge (2) (2) edge[loop left] (2) (3) edge[loop left] (3);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0:1.5) {$1$};
\node(2) at (120:1.5) {$2$};
\node(3) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path[->] (1) edge (2) (2) edge[loop left] (2) (3) edge[loop left] (3);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz Dprime}{\begin{tikzpicture}
%\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0:1.5) {$1$};
%\node(2) at (120:1.5) {$2$};
%\node(3) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=red,line width=1.7pt}]
%\path[->] (1) edge[loop right] (1) edge[bend left=20] (3);
%\path[->] (2) edge (1) edge[bend left=20] (3);
%\path[->] (3) edge[bend left=20] (1) edge[bend left=20] (2);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0:1.5) {$1$};
\node(2) at (120:1.5) {$2$};
\node(3) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=red,line width=1.7pt}]
\path[->] (1) edge[loop right] (1) edge[bend left=20] (3);
\path[->] (2) edge (1) edge[bend left=20] (3);
\path[->] (3) edge[bend left=20] (1) edge[bend left=20] (2);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$\\
$D$ & $\overline{D}$\\\hline
\end{tabular}
\ \ \ .
\]


The cycles of $D$ are $\left(  2\right)  _{\sim}$ and $\left(  3\right)
_{\sim}$, whereas the cycles of $\overline{D}$ are $\left(  1\right)  _{\sim}%
$, $\left(  2,3\right)  _{\sim}$, $\left(  3,1\right)  _{\sim}$ and $\left(
1,3,2\right)  _{\sim}$ (the \textquotedblleft$\sim$\textquotedblright\ means
\textquotedblleft rotation-equivalence class\textquotedblright).

Thus, the $\sum_{\substack{\sigma\in\mathfrak{S}_{V};\\\text{each cycle of
}\sigma\text{ is}\\\text{a }D\text{-cycle or a }\overline{D}\text{-cycle}}}$
sum in Main Theorem I has four addends, corresponding to ($\sigma$ written in
one-line notation)%
\[%
\begin{tabular}
[c]{|c||c|c|c|c|}\hline
$\sigma=$ & $\left[  1,2,3\right]  $ & $\left[  3,1,2\right]  $ & $\left[
1,3,2\right]  $ & $\left[  3,2,1\right]  $\\\hline
$\left(-1\right)^{\varphi\left(  \sigma\right)  }=$ & $1$ & $1$ & $1$ & $1$\\\hline
$p_{\operatorname*{type}\sigma}=$ & $p_{1}^{3}$ & $p_{3}$ & $p_{2}p_{1}$ &
$p_{2}p_{1}$\\\hline
\end{tabular}
\
\]
Hence, Main Theorem I yields%
\[
U_{D}=p_{1}^{3}+p_{3}+p_{2}p_{1}+p_{2}p_{1}=p_{1}^{3}+2p_{1}p_{2}+p_{3}.
\]


\item \textbf{Example.} Let%
\[%
\begin{tabular}
[c]{|c|c|}\hline
$%
%TCIMACRO{\TeXButton{tikz D}{\begin{tikzpicture}
%\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0:1.5) {$1$};
%\node(2) at (120:1.5) {$2$};
%\node(3) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
%\path
%[->] (1) edge[bend left=20] (3) (2) edge (1) (3) edge[bend left=20] (1) (3) edge (2);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0:1.5) {$1$};
\node(2) at (120:1.5) {$2$};
\node(3) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=blue,line width=1.7pt}]
\path
[->] (1) edge[bend left=20] (3) (2) edge (1) (3) edge[bend left=20] (1) (3) edge (2);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz Dprime}{\begin{tikzpicture}
%\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0:1.5) {$1$};
%\node(2) at (120:1.5) {$2$};
%\node(3) at (240:1.5) {$3$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=red,line width=1.7pt}]
%\path[->] (1) edge[loop right] (1) edge (2);
%\path[->] (2) edge[loop left] (2) edge (3);
%\path[->] (3) edge[loop left] (3);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}
\draw[draw=black] (-2.1, -2.2) rectangle (2.6, 2.2);
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0:1.5) {$1$};
\node(2) at (120:1.5) {$2$};
\node(3) at (240:1.5) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=red,line width=1.7pt}]
\path[->] (1) edge[loop right] (1) edge (2);
\path[->] (2) edge[loop left] (2) edge (3);
\path[->] (3) edge[loop left] (3);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$\\
$D$ & $\overline{D}$\\\hline
\end{tabular}
\ \ \ .
\]
Thus, the $\sum_{\substack{\sigma\in\mathfrak{S}_{V};\\\text{each cycle of
}\sigma\text{ is}\\\text{a }D\text{-cycle or a }\overline{D}\text{-cycle}}}$
sum in Main Theorem I has three addends, with%
\[%
\begin{tabular}
[c]{|c||c|c|c|}\hline
$\sigma=$ & $\left[  1,2,3\right]  $ & $\left[  3,1,2\right]  $ & $\left[
3,2,1\right]  $\\\hline
$\left(-1\right)^{\varphi\left(  \sigma\right)  }=$ & $1$ & $1$ & $-1$\\\hline
$p_{\operatorname*{type}\sigma}=$ & $p_{1}^{3}$ & $p_{3}$ & $p_{2}p_{1}%
$\\\hline
\end{tabular}
\]
Hence, Main Theorem I yields%
\[
U_{D}=p_{1}^{3}+p_{3}-p_{2}p_{1}.
\]


\item Main Theorem I yields Berge's theorem, since the sum for $D$ and the sum
for $\overline{D}$ range over the same $\sigma$'s, and the addends only differ
in sign.

\item \textbf{Corollary.} Let $D=\left(  V,A\right)  $ be a digraph. Assume
that every $D$-cycle has odd length. Then,
\[
U_{D}=\sum_{\substack{\sigma\in\mathfrak{S}_{V};\\\text{each cycle of }%
\sigma\text{ is}\\\text{a }D\text{-cycle or a }\overline{D}\text{-cycle}%
}}p_{\operatorname*{type}\sigma}\in\mathbb{N}\left[  p_{1},p_{2},p_{3}%
,\ldots\right]  .
\]


\item \textbf{Main Theorem II.} 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$. (A cycle is called
\textbf{nontrivial} if it has length $>1$.) Then,%
\begin{align*}
U_{D}  &  =\sum_{\substack{\sigma\in\mathfrak{S}_{V};\\\text{each cycle of
}\sigma\text{ is a }D\text{-cycle;}\\\text{all cycles of }\sigma\text{ have
odd length}}}2^{\psi\left(  \sigma\right)  }p_{\operatorname*{type}\sigma}\\
&  \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]  .
\end{align*}


\item Main Theorem II easily yields R\'{e}dei's theorem, as the only addend
with $2^{\psi\left(  \sigma\right)  }$ odd is the $\sigma=\operatorname*{id}$ addend.

\item The above corollary yields that $U_{D}$ is $p$-positive when $D$ has no
even-length cycles. But this holds even more generally:

\item \textbf{Main Theorem III.} Let $D=\left(  V,A\right)  $ be a digraph
that has no cycles of length $2$. Then,%
\[
U_{D}=\sum_{\substack{\sigma\in\mathfrak{S}_{V};\\\text{each cycle of }%
\sigma\text{ is}\\\text{a }D\text{-cycle or a }\overline{D}\text{-cycle;}%
\\\text{no even-length cycle of }\sigma\text{ is}\\\text{a }D\text{-cycle or a
reversed }D\text{-cycle}}}p_{\operatorname*{type}\sigma}.
\]


\item \textbf{Remark.} Even this does not cover all $p$-positive $U_{D}$'s;
there are more.
\end{itemize}

\newpage

\section{Proof ideas}

\begin{itemize}
\item The proof of Main Theorem I is long and intricate. It might be
simplifiable. Here are the main ideas.

\item \textbf{P\'{o}lya-style lemma.} Let $V$ be a finite set. Let $\sigma
\in\mathfrak{S}_{V}$ be a permutation of $V$. Then,%
\[
\sum_{\substack{f:V\rightarrow\left\{  1,2,3,\ldots\right\}  \text{;}%
\\f\circ\sigma=f}}\ \ \prod_{v\in V}x_{f\left(  v\right)  }%
=p_{\operatorname*{type}\sigma}.
\]


\textbf{Proof.} Easy exercise.

\item Using this lemma (and the above formula for $a_{D,f}$), we can easily
reduce Main Theorem I to the following lemma:

\item \textbf{Main combinatorial lemma.} Let $D=\left(  V,A\right)  $ be a
digraph with $n$ vertices. Let $f:V\rightarrow\left\{  1,2,3,\ldots\right\}  $
be any map. Then,%
\[
\prod_{j\in f\left(  V\right)  }\left(  \text{\# of hamps of }\overline{D_{j}%
}\right)  =\sum_{\substack{\sigma\in\mathfrak{S}_{V};\\\text{each cycle of
}\sigma\text{ is}\\\text{a }D\text{-cycle or a }\overline{D}\text{-cycle;}%
\\f\circ\sigma=f}}\left(  -1\right)  ^{\varphi\left(  \sigma\right)  },
\]
where $\overline{D_{j}}$ is the induced subdigraph of $\overline{D}$ on the
vertex set $f^{-1}\left(  j\right)  $.

\item Work on each level:

\textbf{Main combinatorial lemma (simplified).} Let $D=\left(  V,A\right)  $
be a digraph with $n$ vertices. Then,%
\[
\left(  \text{\# of hamps of }\overline{D}\right)  =\sum_{\substack{\sigma
\in\mathfrak{S}_{V};\\\text{each cycle of }\sigma\text{ is}\\\text{a
}D\text{-cycle or a }\overline{D}\text{-cycle}}}\left(  -1\right)
^{\varphi\left(  \sigma\right)  }.
\]


\item This can be proved using a nontrivial exclusion-inclusion.

\item Main Theorems II and III follow from Main Theorem I by combining
$\sigma$'s into equivalence classes by reversing certain cycles.
\end{itemize}

\newpage

\section{A surprise}

\begin{itemize}
\item \textbf{Theorem.} Let $D$ be a tournament. Then,
\begin{align*}
&  \left(  \text{\# of hamps of }D\right) \\
&  \equiv1+2\left(  \text{\# of nontrivial odd-length }D\text{-cycles}\right)
\operatorname{mod}4.
\end{align*}
Here, \textquotedblleft nontrivial\textquotedblright\ means \textquotedblleft
having length $>1$\textquotedblright.

\item We can prove this using Main Theorem II. We have not seen this anywhere
in the literature.
\end{itemize}

\newpage

\section{I thank}

\begin{itemize}
\item \textbf{Richard P. Stanley} for the obvious reasons.

\item \textbf{Mike Zabrocki} for helpful comments.

\item \textbf{Anna Pun} for the invitation and the implied compliment.

\item \textbf{you} for your patience.
\end{itemize}

\begin{noncompile}
TODO: Add the following:

\begin{enumerate}
\item More about Chow's $x,y$ generalization. What can be extended?

\item Proof ideas for Main Theorems II-III in more details.

\item Antipode formula (even though known).

\item s-positivity for path digraphs.

\item w-generalization (Zabrocki).

\item The rest of the statements made in EC2add.
\end{enumerate}
\end{noncompile}


\end{document}