\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=True]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Tuesday, July 29, 2025 19:57:50}
%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
\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{warning}[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{convention}[1][Convention]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{warning}[1][Warning]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\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}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{22.5cm}
\setlength\textwidth{14.8cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\defn}[1]{{\color{darkred}\emph{#1}}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\mono}{\hookrightarrow}
\newcommand{\epi}{\twoheadrightarrow}
\newcommand{\iso}{\overset{\cong}{\to}}
\newcommand{\symd}{\mathbin{\bigtriangleup}}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{calc}
\usetikzlibrary{chains}
\usetikzlibrary{shapes}
\usetikzlibrary{decorations.pathmorphing}
\usetikzlibrary{lindenmayersystems}
\definecolor{darkgreen}{rgb}{0,.5,0}
\newtheoremstyle{plainsl}
{8pt plus 2pt minus 4pt}
{8pt plus 2pt minus 4pt}
{\slshape}
{0pt}
{\bfseries}
{.}
{5pt plus 1pt minus 1pt}
{}
\theoremstyle{plainsl}
\ihead{An equality for balanced digraphs, version 2025-07-29}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{An equality for balanced digraphs}
\author{Darij Grinberg\thanks{Drexel University, Philadelphia, PA.
\href{mailto:darijgrinberg@gmail.com}{\texttt{darijgrinberg@gmail.com}}},
Benjamin Liber\thanks{Drexel University, Philadelphia, PA.
\href{mailto:bl839@drexel.edu}{\texttt{bl839@drexel.edu}}}}
\date{July 29, 2025}
\maketitle

\begin{abstract}
Consider a directed multigraph $D$ that is balanced (i.e., at each vertex, the
indegree equals the outdegree). Let $A$ be its set of arcs. Fix an integer
$k$. Let $s$ be a vertex of $D$. We show that the number of $k$-element
subsets $B$ of $A$ that contain no cycles but contain a path from each vertex
to $s$ (we call them \textquotedblleft$s$-convergences\textquotedblright) is
independent on $s$. This generalizes known facts about spanning arborescences,
acyclic orientations and maximal acyclic subdigraphs (or, equivalently,
minimum feedback arc sets).

\end{abstract}

\section{The theorem}

In this note, we shall discuss \emph{balanced multidigraphs} -- i.e., directed
multigraphs (allowing loops and multiple arcs) in which each vertex satisfies
\textquotedblleft outdegree = indegree\textquotedblright. We recall the
relevant definitions in more detail:

A \emph{multidigraph} (henceforth just \emph{digraph}) means a triple
$(V,A,\psi)$, where $V$ and $A$ are two finite sets and $\psi:A\rightarrow
V\times V$ is a map. The elements of $V$ are called the \emph{vertices} of
this digraph, and the elements of $A$ are called the \emph{arcs} of this
digraph. The \emph{source} and \emph{target} of an arc $a\in A$ are,
respectively, the first and second entries of the pair $\psi(a)$. The
\emph{indegree} $\deg^{-}v$ of a vertex $v\in V$ means the number of arcs
$a\in A$ whose target is $v$. The \emph{outdegree} $\deg^{+}v$ of a vertex
$v\in V$ means the number of arcs $a\in A$ whose source is $v$. We say that a
digraph $(V,A,\psi)$ is \emph{balanced} if and only if each vertex $v\in V$
satisfies $\deg^{+}v=\deg^{-}v$. For further terminology on digraphs, we refer
to \cite{22s}.\footnote{The famous directed Euler--Hierholzer theorem (which
will not be used in this note) says that a weakly connected digraph has an
Eulerian circuit if and only if it is balanced. Thus, weakly connected
balanced digraphs are also known as \emph{Eulerian digraphs}.}

A \emph{to-root} of a digraph $D$ means a vertex $s$ of $D$ such that for each
vertex $v$ of $D$, the digraph $D$ has a path from $v$ to $s$ (equivalently, a
walk from $v$ to $s$).

From now on, we \textbf{fix a balanced digraph} $D=(V,A,\psi)$. If $B$ is any
subset of $A$, then $D\left\langle B\right\rangle $ will denote the induced
subdigraph $\left(  V,B,\psi\mid_{B}\right)  $. A subset $B$ of $A$ will be
called \emph{acyclic} if the subdigraph $D\left\langle B\right\rangle $ has no
cycles. (\textquotedblleft Cycle\textquotedblright\ always means
\textquotedblleft directed cycle\textquotedblright, as in \cite[Definition
4.5.1]{22s}.)

Given a vertex $s$ of $D$, we define an \emph{$s$-convergence} to be an
acyclic subset $B$ of $A$ such that $s$ is a to-root of the subdigraph $D
\left\langle B \right\rangle $.

We can think of an $s$-convergence as a set $B$ of arcs of $D$ such that by
following the $B$-arcs (i.e. the arcs in $B$) from any vertex $v\in V$, we
will always arrive at $s$ (no matter which $B$-arcs we take), and we will be
stuck at $s$. (This intuition is formalized in Proposition \ref{prop.s-conv.2}.)

For any $k\in\mathbb{N}$ and $s\in V$, we let $\gamma_{k}\left(  s\right)  $
denote the number of $s$-convergences of size $k$ (that is, with $k$
arcs).\footnote{The symbol $\mathbb{N}$ denotes the set $\left\{
0,1,2,\ldots\right\}  $.}

In this note, we shall prove the following result:

\begin{theorem}
\label{thm.balgamma}Let $k\in\mathbb{N}$. Then, the number $\gamma_{k}\left(
s\right)  $ does not depend on $s$. That is, $\gamma_{k}\left(  s\right)
=\gamma_{k}\left(  t\right)  $ for any $s,t\in V$.
\end{theorem}

\begin{example}
Let $D$ be the following balanced multidigraph:%
\[%
%TCIMACRO{\TeXButton{tikz multidigraph}{\begin{tikzpicture}[scale=4]
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0,0) {$1$};
%\node(2) at (0,1) {$2$};
%\node(3) at (1,1) {$3$};
%\node(4) at (1,0) {$4$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
%\path[->] (1) edge[bend left=20] node[left] {$a$} (2);
%\path[->] (2) edge[bend left=20] node[right] {$b$} (1);
%\path[->] (2) edge node[above] {$c$} (3);
%\path[->] (3) edge node[right] {$d$} (4);
%\path[->] (4) edge node[above] {$e$} (2);
%\path[->] (1) edge[bend left=20] node[above] {$f$} (4);
%\path[->] (4) edge[bend left=20] node[below] {$g$} (1);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=4]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0,0) {$1$};
\node(2) at (0,1) {$2$};
\node(3) at (1,1) {$3$};
\node(4) at (1,0) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[->] (1) edge[bend left=20] node[left] {$a$} (2);
\path[->] (2) edge[bend left=20] node[right] {$b$} (1);
\path[->] (2) edge node[above] {$c$} (3);
\path[->] (3) edge node[right] {$d$} (4);
\path[->] (4) edge node[above] {$e$} (2);
\path[->] (1) edge[bend left=20] node[above] {$f$} (4);
\path[->] (4) edge[bend left=20] node[below] {$g$} (1);
\end{scope}
\end{tikzpicture}%
%EndExpansion
\]
Then, the $1$-convergences are the subsets%
\[
\left\{  b,d,g\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  b,d,e\right\}
,\ \ \ \ \ \ \ \ \ \ \left\{  c,d,g\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{
b,d,e,g\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  b,c,d,g\right\}  .
\]
Hence, $\gamma_{3}\left(  1\right)  =3$, $\gamma_{4}\left(  1\right)  =2$, and
$\gamma_{k}\left(  1\right)  =0$ for all $k\notin\left\{  3,4\right\}  $. As a
visual aid, below is the spanning subdigraph $D\left\langle B\right\rangle $
for $B=\left\{  b,d,e,g\right\}  $:
\[%
%TCIMACRO{\TeXButton{tikz multidigraph}{\begin{tikzpicture}[scale=4]
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0,0) {$1$};
%\node(2) at (0,1) {$2$};
%\node(3) at (1,1) {$3$};
%\node(4) at (1,0) {$4$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
%\path[->] (2) edge[bend left=20] node[right] {$b$} (1);
%\path[->] (3) edge node[right] {$d$} (4);
%\path[->] (4) edge node[above] {$e$} (2);
%\path[->] (4) edge[bend left=20] node[below] {$g$} (1);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=4]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0,0) {$1$};
\node(2) at (0,1) {$2$};
\node(3) at (1,1) {$3$};
\node(4) at (1,0) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[->] (2) edge[bend left=20] node[right] {$b$} (1);
\path[->] (3) edge node[right] {$d$} (4);
\path[->] (4) edge node[above] {$e$} (2);
\path[->] (4) edge[bend left=20] node[below] {$g$} (1);
\end{scope}
\end{tikzpicture}%
%EndExpansion
\]


\noindent Theorem \ref{thm.balgamma} says that for all $v\in\{1,2,3,4\}$, we
have $\gamma_{3}(v)=3$, $\gamma_{4}(v)=2$, and $\gamma_{k}(v)=0$ for all
$k\notin\{3,4\}$. For example, the $2$-convergences are the subsets
\[
\left\{  a,d,e\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  a,d,g\right\}
,\ \ \ \ \ \ \ \ \ \ \left\{  d,e,f\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{
a,d,e,f\right\}  ,\ \ \ \ \ \ \ \ \ \ \left\{  a,d,e,g\right\}  .
\]
Hence, $\gamma_{3}(2)=3=\gamma_{3}(1)$, $\gamma_{4}(2)=2=\gamma_{4}(1)$, and
$\gamma_{k}(2)=0=\gamma_{k}(1)$ for all $k\notin\{3,4\}$. The same holds for
$v\in\left\{  3,4\right\}  $.
\end{example}

\section{Particular cases}

Theorem \ref{thm.balgamma} was inspired by a talk of Karla Leipold (NORCOM
2025), which made the first author aware of \cite[Lemma 4.1]{LeiVal24} and
\cite[\S 3.1]{PerPha15}. The talk discussed no enumerative questions, yet was
haunted by a perceptible aura of identities. The present note follows this
aura to its source.

Some particular cases of Theorem \ref{thm.balgamma} are known:

\begin{enumerate}
\item When $k=\left\vert V\right\vert -1$, the $s$-convergences $B$ of size
$k$ (or, more precisely, the respective subdigraphs $D\left\langle
B\right\rangle $ of $D$) are precisely the spanning arborescences of $D$
rooted to $s$ (see \cite[Definition 5.10.1 \textbf{(b)}]{22s} for the
definition of this). Indeed, the condition $\left\vert B\right\vert
=\left\vert V\right\vert -1$, combined with the to-rootness of $s$, forces
$D\left\langle B\right\rangle $ to be an arborescence rooted to $s$ (by
\cite[Theorem 5.10.5]{22s}), and conversely, if $D\left\langle B\right\rangle
$ is a spanning arborescence rooted to $s$, then \cite[Theorem 5.10.5]{22s}
shows that $B$ is acyclic and $\left\vert B\right\vert =\left\vert
V\right\vert -1$. Thus, in the case $k=\left\vert V\right\vert -1$, Theorem
\ref{thm.balgamma} is just \cite[Corollary 5.12.1]{22s}.

Likewise, if $k<\left\vert V\right\vert -1$, then Theorem \ref{thm.balgamma}
is just saying that $0=0$, since a spanning subdigraph $D\left\langle
B\right\rangle $ with fewer than $\left\vert V\right\vert -1$ arcs cannot have
a to-root.

\item If $D=G^{\operatorname*{bidir}}$ for some undirected multigraph
$G=\left(  V,E,\varphi\right)  $ (this means that $D$ is obtained from $G$ by
replacing\ each edge $e$ with two arcs $e^{\rightarrow}$ and $e^{\leftarrow}$,
going in opposite directions), and if $k=\left\vert E\right\vert =\left\vert
A\right\vert /2$, then the $s$-convergences $B$ of size $k$ are just the
acyclic orientations of $G$ with unique sink $s$ (because the acyclicity
condition forbids $B$ from containing both $e^{\rightarrow}$ and
$e^{\leftarrow}$ for any given edge $e\in E$, but the size condition
$\left\vert B\right\vert =k=\left\vert E\right\vert $ forces $B$ to contain at
least one of these two arcs; see Proposition \ref{prop.s-conv.2} for the
uniqueness of the sink). Thus, in this case, Theorem \ref{thm.balgamma} is
saying that the number of acyclic orientations of a given multigraph $G$ with
unique sink $s$ does not depend on $s$. This is part of a result by Greene and
Zaslavsky \cite[Theorem 7.3]{GreZas83}, proved using hyperplane arrangements,
and has recently been reproved combinatorially by Foissy \cite[Proposition
4.6]{Foissy22}.

\item Up to reversing the directions of the arcs, \cite[Proposition
3.7]{PerPha15} is Theorem \ref{thm.balgamma} for a specific value of $k$ --
namely, for the maximum possible that makes $\gamma_{k}\left(  s\right)  $ nonzero.

We note that when $D$ is weakly connected, then this maximum $k$ is also the
maximum size of an acyclic subset of $A$ (not just of an $s$-convergence).
This is a consequence of \cite[Theorem 3.4]{PerPha15}. It thus follows that
finding this maximum $k$ is equivalent to the \emph{maximum acyclic subdigraph
problem} for Eulerian (= weakly connected balanced) digraphs, which is known
to be NP-hard by \cite[Theorem 3.10]{PerPha15} (see also \cite[\S 3.7.1 and
Lemma 4.4.3]{BanGut18}). In the terminology of algorithmic combinatorics, this
problem is often stated in terms of the complement of the acyclic subset; this
complement is known as a \emph{feedback arc set}. In these terms, our
$\gamma_{k}\left(  s\right)  $ counts the feedback arc sets of size
$\left\vert A\right\vert -k$; this counting problem is \#P-complete
\cite[Theorem 5]{Perrot19}.
\end{enumerate}

\begin{noncompile}
TODO: see if something from
https://en.wikipedia.org/wiki/Feedback\_arc\_set\#Equivalences is relevant to us.

(I'm not sure how relevant this is to us). From
\href{https://link.springer.com/chapter/10.1007/978-3-642-45043-3_26}{this},
we can conclude the following. Let $D=(V,A)$ be a simple balanced digraph with
$|V|=n$ and $|A|=m$. If $\deg^{+}v=\deg^{-}v=1$ for all $v\in V$, then the
size of a maximum acyclic subdigraph is at least $m-\frac{n}{3}$, and this
bound is tight. (Thm 1). If $\deg^{+}v=\deg^{-}v\in\{1,2\}$ for all $v\in V$,
then the size of a maximum acyclic subdigraph is at least $\frac{2m}{3}$, and
this bound is tight (Thm. 2 and Corollary 4).

See also https://doi.org/10.1016/S0166-218X(00)00339-5 .
\end{noncompile}

\section{The proof}

We will prove Theorem~\ref{thm.balgamma} through a sequence of lemmas, which
are self-contained and might be of independent interest.

If $P$, $Q$ and $S$ are three sets, then the notation \textquotedblleft%
$S=P\sqcup Q$\textquotedblright\ shall mean that $S=P\cup Q$ and $P\cap
Q=\varnothing$. In other words, it shall mean that $S$ is the union of the two
disjoint sets $P$ and $Q$. Of course, if $S=P\sqcup Q$, then $P$ and $Q$ are
subsets of $S$ and we have $\left\vert S\right\vert =\left\vert P\right\vert
+\left\vert Q\right\vert $.

\begin{noncompile}
For two sets $P$ and $Q$, we shall use the notation $P\sqcup Q$ to denote the
\emph{disjoint union} of $P$ and $Q$, that is, the union $P\cup Q$ if the
intersection $P\cap Q$ is empty. Otherwise, $P\sqcup Q$ does not exist. Of
course, if $P\sqcup Q$ exists, then $\left\vert P\sqcup Q\right\vert
=\left\vert P\right\vert +\left\vert Q\right\vert $.
\end{noncompile}

For any subsets $P$ and $Q$ of $V$, we let $A(P,Q)$ denote the set of arcs in
$A$ whose source belongs to $P$ and whose target belongs to $Q$. The following
fact is a simple but crucial property of balanced digraphs:

\begin{proposition}
\label{prop.A-symmetry}Let $P$ and $Q$ be two subsets of $V$ such that
$V=P\sqcup Q$. Then,
\[
\left\vert A\left(  P,Q\right)  \right\vert =\left\vert A\left(  Q,P\right)
\right\vert .
\]

\end{proposition}

\begin{proof}
This is a known fact (see, e.g., \cite[Exercise 9.1]{22s}). The easiest way to
prove it is as follows: By the definition of an outdegree, we
have\footnote{The symbol \textquotedblleft\#\textquotedblright\ means
\textquotedblleft number\textquotedblright.}%
\begin{align}
& \sum_{p\in P}\deg^{+}p\nonumber\\
& =\sum_{p\in P}\left(  \text{\# of arcs }a\in A\text{ with source }p\right)
\nonumber\\
& =\left(  \text{\# of arcs }a\in A\text{ with source in }P\right)
\nonumber\\
& =\underbrace{\left(  \text{\# of arcs }a\in A\text{ with source in }P\text{
and target in }P\right)  }_{=\left\vert A\left(  P,P\right)  \right\vert
}\nonumber\\
& \ \ \ \ \ \ \ \ \ \ +\underbrace{\left(  \text{\# of arcs }a\in A\text{ with
source in }P\text{ and target in }Q\right)  }_{=\left\vert A\left(
P,Q\right)  \right\vert }\nonumber\\
& \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the target of any arc }a\in A\text{ belongs to either }P\text{ or
}Q\text{,}\\
\text{but not to both (because }V=P\sqcup Q\text{)}%
\end{array}
\right)  \nonumber\\
& =\left\vert A\left(  P,P\right)  \right\vert +\left\vert A\left(
P,Q\right)  \right\vert .\label{pf.prop.A-symmetry.sum.1}%
\end{align}
An analogous argument (but with the roles of sources and targets switched)
shows that%
\begin{equation}
\sum_{p\in P}\deg^{-}p=\left\vert A\left(  P,P\right)  \right\vert +\left\vert
A\left(  Q,P\right)  \right\vert .\label{pf.prop.A-symmetry.sum.2}%
\end{equation}


However, each $p\in P$ satisfies $\deg^{+}p=\deg^{-}p$ (since $D$ is
balanced). Thus, the left hand sides of the equalities
(\ref{pf.prop.A-symmetry.sum.1}) and (\ref{pf.prop.A-symmetry.sum.2}) are
equal. Therefore, their right hand sides are equal as well. In other words, we
have%
\[
\left\vert A\left(  P,P\right)  \right\vert +\left\vert A\left(  P,Q\right)
\right\vert =\left\vert A\left(  P,P\right)  \right\vert +\left\vert A\left(
Q,P\right)  \right\vert .
\]
Subtracting $\left\vert A\left(  P,P\right)  \right\vert $ from this equality,
we obtain $\left\vert A\left(  P,Q\right)  \right\vert =\left\vert A\left(
Q,P\right)  \right\vert $. Thus, Proposition \ref{prop.A-symmetry} is proved.
\end{proof}

\begin{noncompile}
OLD\ PROOF\ OF PROPOSITION \ref{prop.A-symmetry}: We have%
\[
A\left(  P,V\right)  =A\left(  P,P\right)  \sqcup A\left(  P,Q\right)
\]
(since the target of an arc belongs to either $P$ or $Q$ but not to both), so
that%
\[
\left\vert A\left(  P,V\right)  \right\vert =\left\vert A\left(  P,P\right)
\right\vert +\left\vert A\left(  P,Q\right)  \right\vert .
\]
However, we can count the arcs in $A\left(  P,V\right)  $ according to their
sources $p\in P$. This yields%
\begin{equation}
\left\vert A\left(  P,V\right)  \right\vert =\sum_{p\in P}\deg^{+}%
p,\label{pf.prop.A-symmetry.3}%
\end{equation}
since each arc in $A\left(  P,V\right)  $ is counted in the outdegree of
exactly one $p\in P$ (namely, of its source). Comparing these two equalities,
we obtain%
\begin{equation}
\sum_{p\in P}\deg^{+}p=\left\vert A\left(  P,P\right)  \right\vert +\left\vert
A\left(  P,Q\right)  \right\vert .\label{pf.prop.A-symmetry.4}%
\end{equation}


On the other hand, $A\left(  V,P\right)  =A\left(  P,P\right)  \sqcup A\left(
Q,P\right)  $ (since the source of an arc belongs to either $P$ or $Q$ but not
to both) and thus%
\[
\left\vert A\left(  V,P\right)  \right\vert =\left\vert A\left(  P,P\right)
\right\vert +\left\vert A\left(  Q,P\right)  \right\vert .
\]
Similarly to (\ref{pf.prop.A-symmetry.3}), we can show that%
\[
\left\vert A\left(  V,P\right)  \right\vert =\sum_{p\in P}\deg^{-}p.
\]
Comparing these two equalities, we obtain%
\begin{equation}
\sum_{p\in P}\deg^{-}p=\left\vert A\left(  P,P\right)  \right\vert +\left\vert
A\left(  Q,P\right)  \right\vert .\label{pf.prop.A-symmetry.5}%
\end{equation}


The left hand sides of the equalities (\ref{pf.prop.A-symmetry.4}) and
(\ref{pf.prop.A-symmetry.5}) are equal (since $D$ is balanced, so that each
$p\in P$ satisfies $\deg^{+}p=\deg^{-}p$). Hence, their right hand sides must
be equal as well. That is,%
\[
\left\vert A\left(  P,P\right)  \right\vert +\left\vert A\left(  P,Q\right)
\right\vert =\left\vert A\left(  P,P\right)  \right\vert +\left\vert A\left(
Q,P\right)  \right\vert .
\]
Subtracting $\left\vert A\left(  P,P\right)  \right\vert $ from this equality,
we obtain $\left\vert A\left(  P,Q\right)  \right\vert =\left\vert A\left(
Q,P\right)  \right\vert $. Thus, Proposition \ref{prop.A-symmetry} is proved.
\end{noncompile}

Now, given a subset $B$ of $A$ and two vertices $v,w\in V$, we say that
\textquotedblleft$v$ \emph{can }$B$\emph{-reach} $w$\textquotedblright\ if the
digraph $D\left\langle B\right\rangle $ has a path from $v$ to $w$ (or,
equivalently, a walk from $v$ to $w$).

Fix two vertices $s,t\in V$ and an integer $k\in\mathbb{N}$. We want to show
that $\gamma_{k}\left(  s\right)  =\gamma_{k}\left(  t\right)  $.

For any subset $B$ of $A$, we define the subsets%
\begin{align*}
S\left(  B\right)   &  :=\left\{  v\in V\ \mid\ v\text{ can }B\text{-reach
}s\right\}  \ \ \ \ \ \ \ \ \ \ \text{and}\\
T\left(  B\right)   &  :=\left\{  v\in V\ \mid\ v\text{ can }B\text{-reach
}t\right\}  \ \ \ \ \ \ \ \ \ \ \text{of }V.
\end{align*}
We call them the \emph{attraction basins} of $s$ and $t$ with respect to $B$.
Note that $s\in S\left(  B\right)  $ and $t\in T\left(  B\right)  $ always
hold, since each vertex can $B$-reach itself (by a path of length $0$).

The following property of attraction basins will be useful to our later arguments:

\begin{lemma}
\label{lem.new0}Let $P$ and $Q$ be two subsets of $V$ such that $V=P\sqcup Q$.
Let $E$ be a subset of $A$. Let $C$ be a subset of $A\left(  P,Q\right)  $.
Then, $S\left(  E\right)  =P$ if and only if $S\left(  E\cup C\right)  =P$.
\end{lemma}

\begin{proof}
First, we observe that if $B_{1}$ and $B_{2}$ are two subsets of $A$
satisfying $B_{1}\subseteq B_{2}$, then any path of $D\left\langle
B_{1}\right\rangle $ is a path of $D\left\langle B_{2}\right\rangle $, and
thus we have $S\left(  B_{1}\right)  \subseteq S\left(  B_{2}\right)  $.
Hence, $S\left(  E\right)  \subseteq S\left(  E\cup C\right)  $ (since
$E\subseteq E\cup C$).

Note furthermore that $P$ is disjoint from $Q$ (since $V=P\sqcup Q$).

We must prove the equivalence $\left(  S\left(  E\right)  =P\right)
\ \Longleftrightarrow\ \left(  S\left(  E\cup C\right)  =P\right)  $. We shall
verify the $\Longrightarrow$ and $\Longleftarrow$ directions separately:
\medskip

$\Longrightarrow:$ Assume that $S\left(  E\right)  =P$. We must show that
$S\left(  E\cup C\right)  =P$.

By assumption, we have $P=S\left(  E\right)  \subseteq S\left(  E\cup
C\right)  $. It remains to prove the converse inclusion.

Let $v\in S\left(  E\cup C\right)  $. Thus, $v$ can $E\cup C$-reach $s$. In
other words, the digraph $D\left\langle E\cup C\right\rangle $ has a path
$\mathbf{p}$ from $v$ to $s$. Consider this path $\mathbf{p}$.

We claim that all arcs of $\mathbf{p}$ belong to $E$. Indeed, let us assume
the contrary. Then, at least one of the arcs of $\mathbf{p}$ does not belong
to $E$. Let $c$ be the \textbf{last} arc of $\mathbf{p}$ that does not belong
to $E$, and let $q$ be the target of this arc $c$.

The arc $c$ belongs to $E\cup C$ (since it is part of the path $\mathbf{p}$,
which is a path of $D\left\langle E\cup C\right\rangle $). Since it does not
belong to $E$, it must thus belong to $C$. Thus, $c\in C\subseteq A\left(
P,Q\right)  $, so that the target of $c$ belongs to $Q$. In other words, $q\in
Q$ (since $q$ is the target of $c$).

However, $c$ is the \textbf{last} arc of $\mathbf{p}$ that does not belong to
$E$. Thus, all the arcs of $\mathbf{p}$ that come after $c$ must belong to
$E$. Therefore, the arcs of $\mathbf{p}$ that come after $c$ form a path of
the digraph $D\left\langle E\right\rangle $. This path starts at $q$ (the
target of $c$) and ends at $s$. Hence, we have shown that $D\left\langle
E\right\rangle $ has a path from $q$ to $s$. In other words, $q$ can $E$-reach
$s$, meaning that $q\in S\left(  E\right)  $. Thus, $q\in S\left(  E\right)
=P$, so that $q\notin Q$ (since $P$ is disjoint from $Q$). This contradicts
$q\in Q$.

This contradiction shows that our assumption was false. Hence, all arcs of
$\mathbf{p}$ belong to $E$. Therefore, $\mathbf{p}$ is a path of
$D\left\langle E\right\rangle $. Hence, $v$ can $E$-reach $s$ (by the path
$\mathbf{p}$). That is, $v\in S\left(  E\right)  =P$.

Since we have proved this for each $v\in S\left(  E\cup C\right)  $, we thus
conclude that $S\left(  E\cup C\right)  \subseteq P$. Combining this with
$P\subseteq S\left(  E\cup C\right)  $, we obtain $S\left(  E\cup C\right)
=P$. This proves the \textquotedblleft$\Longrightarrow$\textquotedblright%
\ direction of Lemma \ref{lem.new0}. \medskip

$\Longleftarrow:$ Assume that $S\left(  E\cup C\right)  =P$. We must show that
$S\left(  E\right)  =P$.

We have $S\left(  E\right)  \subseteq S\left(  E\cup C\right)  =P$ (by
assumption). It remains to prove the converse inclusion.

Let $p\in P$. Then, $p\in P=S\left(  E\cup C\right)  $ (by assumption). Hence,
$p$ can $E\cup C$-reach $s$. That is, the digraph $D\left\langle E\cup
C\right\rangle $ has a path $\mathbf{p}$ from $p$ to $s$. Any vertex $v$ of
this path $\mathbf{p}$ must itself belong to $S\left(  E\cup C\right)  $
(since it can $E\cup C$-reach $s$ by walking along $\mathbf{p}$ from $v$ to
$s$), so it cannot belong to $Q$ (since $S\left(  E\cup C\right)  =P$ is
disjoint from $Q$). Therefore, no arc of this path $\mathbf{p}$ can belong to
$A\left(  P,Q\right)  $ (since this would require its target to belong to
$Q$). Thus, all arcs of this path $\mathbf{p}$ belong to $\left(  E\cup
C\right)  \setminus\underbrace{A\left(  P,Q\right)  }_{\supseteq C}%
\subseteq\left(  E\cup C\right)  \setminus C\subseteq E$. Hence, $\mathbf{p}$
is a path of $D\left\langle E\right\rangle $. Consequently, the vertex $p$ can
$E$-reach $s$ (via the path $\mathbf{p}$). In other words, $p\in S\left(
E\right)  $. Since we have proved this for each $p\in P$, we conclude that
$P\subseteq S\left(  E\right)  $. Therefore, $S\left(  E\right)  =P$ (since
$S\left(  E\right)  \subseteq P$). This proves the \textquotedblleft%
$\Longleftarrow$\textquotedblright\ direction of Lemma \ref{lem.new0}.
\end{proof}

For any $i\in\mathbb{Z}$, we let $\mathcal{P}_{i}\left(  A\right)  $ denote
the set of all $i$-element subsets of $A$. Define the subset%
\begin{align*}
U_{k}:= &  \ \left\{  B\in\mathcal{P}_{k}\left(  A\right)  \text{ is
acyclic}\ \mid\ \text{each vertex can }B\text{-reach }s\text{ or }t\right\}
\\
= &  \ \left\{  B\in\mathcal{P}_{k}\left(  A\right)  \text{ is acyclic}%
\ \mid\ S\left(  B\right)  \cup T\left(  B\right)  =V\right\}
\end{align*}
of $\mathcal{P}_{k}\left(  A\right)  $. (\textquotedblleft
Vertex\textquotedblright\ means \textquotedblleft vertex of $D$%
\textquotedblright, that is, \textquotedblleft element of $V$%
\textquotedblright.)

We observe the following:

\begin{lemma}
\label{lem.new-1}We have%
\[
\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =V\right\}
\right\vert =\gamma_{k}\left(  s\right)  .
\]

\end{lemma}

\begin{proof}
Note that an acyclic subset $B$ of $A$ is an $s$-convergence

\qquad\qquad if and only if $s$ is a to-root of $D\left\langle B\right\rangle
$,

\qquad i.e.,\quad if and only if each vertex $v\in V$ has a path to $s$ in
$D\left\langle B\right\rangle $,

\qquad i.e.,\quad if and only if each vertex $v\in V$ can $B$-reach $s$,

\qquad i.e.,\quad if and only if $S\left(  B\right)  =V$

\noindent(since $S\left(  B\right)  $ is defined as the set of all vertices
$v\in V$ that can $B$-reach $s$). Thus, an $s$-convergence is the same thing
as an acyclic subset $B$ of $A$ that satisfies $S\left(  B\right)  =V$.

Hence, the number $\gamma_{k}\left(  s\right)  $ of all $s$-convergences of
size $k$ can also be described as the number of all acyclic subsets $B$ of $A$
of size $k$ that satisfy $S\left(  B\right)  =V$. In other words,%
\begin{equation}
\gamma_{k}\left(  s\right)  =\left\vert \left\{  B\in\mathcal{P}_{k}\left(
A\right)  \text{ is acyclic }\mid\ S\left(  B\right)  =V\right\}  \right\vert
. \label{pf.lem.new-1.2}%
\end{equation}
But any acyclic $B\in\mathcal{P}_{k}\left(  A\right)  $ satisfying $S\left(
B\right)  =V$ must also satisfy $B\in U_{k}$ (since $\underbrace{S\left(
B\right)  }_{=V}\cup\,T\left(  B\right)  =V\cup T\left(  B\right)  =V$).
Conversely, the definition of $U_{k}$ shows that any $B\in U_{k}$ is acyclic
and belongs to $\mathcal{P}_{k}\left(  A\right)  $. These two facts show that%
\[
\left\{  B\in\mathcal{P}_{k}\left(  A\right)  \text{ is acyclic }%
\mid\ S\left(  B\right)  =V\right\}  =\left\{  B\in U_{k}\ \mid\ S\left(
B\right)  =V\right\}  .
\]
Hence, we can rewrite (\ref{pf.lem.new-1.2}) as
\[
\gamma_{k}\left(  s\right)  =\left\vert \left\{  B\in U_{k}\ \mid\ S\left(
B\right)  =V\right\}  \right\vert .
\]
This proves Lemma \ref{lem.new-1}.
\end{proof}

Now we claim the following:

\begin{lemma}
\label{lem.new1} We have%
\[
\gamma_{k}\left(  s\right)  =\left\vert U_{k}\right\vert -\sum
_{\substack{P,Q\subseteq V\text{ are nonempty;}\\V=P\sqcup Q}}\left\vert
\left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}  \right\vert .
\]

\end{lemma}

\begin{proof}
Each $B\in U_{k}$ satisfies $S\left(  B\right)  =P$ for some nonempty subset
$P$ of $V$ (indeed, the set $S\left(  B\right)  $ is nonempty since it
contains $s$). Hence, by the sum rule,%
\begin{align*}
\left\vert U_{k}\right\vert  &  =\sum_{P\subseteq V\text{ nonempty}}\left\vert
\left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}  \right\vert \\
&  =\sum_{\substack{P,Q\subseteq V;\\P\text{ is nonempty;}\\V=P\sqcup
Q}}\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have introduced an extra index }Q\\
\text{into the sum (to make it more symmetric);}\\
\text{the condition \textquotedblleft}V=P\sqcup Q\text{\textquotedblright%
\ ensures that it}\\
\text{is uniquely determined by }P
\end{array}
\right)  \\
&  =\sum_{\substack{P,Q\subseteq V\text{ are nonempty;}\\V=P\sqcup
Q}}\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert +\underbrace{\left\vert \left\{  B\in U_{k}\ \mid\ S\left(
B\right)  =V\right\}  \right\vert }_{\substack{=\gamma_{k}\left(  s\right)
\\\text{(by Lemma \ref{lem.new-1})}}}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend}\\
\text{for }\left(  P,Q\right)  =\left(  V,\varnothing\right)  \text{ from the
sum}%
\end{array}
\right)  \\
&  =\sum_{\substack{P,Q\subseteq V\text{ are nonempty;}\\V=P\sqcup
Q}}\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert +\gamma_{k}\left(  s\right)  .
\end{align*}
Solving this for $\gamma_{k}\left(  s\right)  $, we obtain the claim of the lemma.
\end{proof}

Similarly, we find:

\begin{lemma}
\label{lem.new2}We have%
\[
\gamma_{k}\left(  t\right)  =\left\vert U_{k}\right\vert -\sum
_{\substack{P,Q\subseteq V\text{ are nonempty;}\\V=P\sqcup Q}}\left\vert
\left\{  B\in U_{k}\ \mid\ T\left(  B\right)  =Q\right\}  \right\vert .
\]

\end{lemma}

\begin{proof}
Analogous to the proof of Lemma \ref{lem.new1}. (Just switch the roles of $s$
and $t$ and also the roles of $P$ and $Q$.)
\end{proof}

Our goal is to prove $\gamma_{k}\left(  s\right)  =\gamma_{k}\left(  t\right)
$. In light of Lemma \ref{lem.new1} and Lemma \ref{lem.new2}, it will suffice
to show the following:

\begin{proposition}
\label{prop.new3}Let $P$ and $Q$ be two nonempty subsets of $V$ such that
$V=P\sqcup Q$. Then,%
\[
\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert =\left\vert \left\{  B\in U_{k}\ \mid\ T\left(  B\right)
=Q\right\}  \right\vert .
\]

\end{proposition}

We will prove this by finding analogous expressions for both sides. First, we
need some notation:

\begin{definition}
If $P$ and $Q$ are two subsets of $V$ satisfying $V=P\sqcup Q$, and if
$i\in\mathbb{Z}$ is arbitrary, then we set%
\[
X_{i}^{P,Q}:=\left\{  B\in\mathcal{P}_{i}(A)\text{ is acyclic}\mid
S(B)=P\text{ and }T(B)=Q\right\}  .
\]

\end{definition}

\begin{lemma}
\label{lem.new4}Let $P$ and $Q$ be two nonempty subsets of $V$ such that
$V=P\sqcup Q$. Then,%
\[
\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert =\sum_{m\in\mathbb{N}}\dbinom{\left\vert A\left(  P,Q\right)
\right\vert }{m}\cdot\left\vert X_{k-m}^{P,Q}\right\vert .
\]

\end{lemma}

We note that the infinite sum on the right hand side here is well-defined,
since it has only finitely many nonzero addends.\footnote{Indeed, all negative
integers $i$ satisfy $\mathcal{P}_{i}\left(  A\right)  =\varnothing$ and thus
$X_{i}^{P,Q}=\varnothing$, so that $\left\vert X_{i}^{P,Q}\right\vert =0$;
thus, we conclude that $\left\vert X_{k-m}^{P,Q}\right\vert =0$ whenever
$m>k$. Alternatively, we can observe that $\dbinom{\left\vert A\left(
P,Q\right)  \right\vert }{m}=0$ whenever $m>\left\vert A\left(  P,Q\right)
\right\vert $.}

\begin{proof}
[Proof of Lemma \ref{lem.new4}.]By the sum rule,
\begin{align}
&  \left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert \nonumber\\
&  =\sum_{C\subseteq A\left(  P,Q\right)  }\left\vert \left\{  B\in
U_{k}\ \mid\ S\left(  B\right)  =P\text{ and }B\cap A\left(  P,Q\right)
=C\right\}  \right\vert , \label{pf.lem.new4.sum}%
\end{align}
since the intersection $B\cap A\left(  P,Q\right)  $ is always a subset of
$A\left(  P,Q\right)  $.

Fix a subset $C\subseteq A(P,Q)$, and let
\[
Y_{k}:=\left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\text{ and }B\cap
A\left(  P,Q\right)  =C\right\}  .
\]
We want to show that $\left\vert Y_{k}\right\vert =\left\vert X_{k-|C|}%
^{P,Q}\right\vert $. Define
\begin{align*}
\text{the map }\Phi:Y_{k}  &  \rightarrow X_{k-|C|}^{P,Q}\\
\text{by }\Phi(B)  &  =B\setminus C
\end{align*}
and
\begin{align*}
\text{the map }\Psi:X_{k-|C|}^{P,Q}  &  \rightarrow Y_{k}\\
\text{by }\Psi(E)  &  =E\cup C.
\end{align*}
Let us first show that these maps are well-defined:

\begin{statement}
\textit{Claim 1.} The map $\Phi$ is well-defined. That is, $B\setminus C\in
X_{k-|C|}^{P,Q}$ for all $B\in Y_{k}$.
\end{statement}

\begin{proof}
[Proof of Claim 1.]Let $B\in Y_{k}$. Then $B\in U_{k}$ as well as $S\left(
B\right)  =P$ and $B\cap A\left(  P,Q\right)  =C$. From $B\in U_{k}$, we see
that $B$ is an acyclic $k$-element subset of $A$, and that each vertex can
$B$-reach $s$ or $B$-reach $t$. In particular, $\left\vert B\right\vert =k$.

We must show that $B\setminus C\in X_{k-|C|}^{P,Q}$. In other words, we must
show that $B\setminus C$ is an acyclic set in $\mathcal{P}_{k-\left\vert
C\right\vert }\left(  A\right)  $ and satisfies $S\left(  B\setminus C\right)
=P$ and $T\left(  B\setminus C\right)  =Q$.

It is clear that $B\setminus C$ is acyclic, since removing arcs from the
acyclic set $B$ cannot create any cycles.

Moreover, from $C=B\cap A\left(  P,Q\right)  \subseteq B$, we obtain
\[
\left\vert B\setminus C\right\vert =\left\vert B\right\vert -\left\vert
C\right\vert =k-\left\vert C\right\vert \ \ \ \ \ \ \ \ \ \ \left(
\text{since }\left\vert B\right\vert =k\right)  .
\]
Thus, $B\setminus C\in\mathcal{P}_{k-\left\vert C\right\vert }\left(
A\right)  $. Also, from $C\subseteq B$, we obtain $\left(  B\setminus
C\right)  \cup C=B$.

Note also that%
\[
B\setminus A\left(  P,Q\right)  =B\setminus\underbrace{\left(  B\cap
A(P,Q)\right)  }_{=C}=B\setminus C.
\]
Thus, the set $B\setminus C$ is disjoint from $A\left(  P,Q\right)  $ (since
$B\setminus A\left(  P,Q\right)  $ clearly is).

Next we show that $B\cap A\left(  Q,P\right)  =\varnothing$. Indeed, assume
the contrary. Then, there is an arc $b\in B\cap A\left(  Q,P\right)  $.
Consider this $b$. Thus, $b\in B$ and $b\in A\left(  Q,P\right)  $. The latter
shows that the arc $b$ has a source $q\in Q$ and a target $p\in P$. The vertex
$p$ can $B$-reach $s$ (since $p\in P=S\left(  B\right)  $);\ hence, the vertex
$q$ can $B$-reach $s$ as well (by first stepping to $p$ via the arc $b$). This
means that $q\in S\left(  B\right)  =P$, which contradicts $q\in Q$ since
$V=P\sqcup Q$. This contradiction shows that our assumption was false, so we
know that $B\cap A\left(  Q,P\right)  =\varnothing$.

In other words, no arc in $B$ belongs to $A\left(  Q,P\right)  $. Hence, no
arc in $B\setminus C$ belongs to $A\left(  Q,P\right)  $ either (since
$B\setminus C\subseteq B$). Furthermore, no arc in $B\setminus C$ belongs to
$A\left(  P,Q\right)  $ (since the set $B\setminus C$ is disjoint from
$A\left(  P,Q\right)  $).

Let us now prove that $S\left(  B\setminus C\right)  =P$. Indeed, Lemma
\ref{lem.new0} (applied to $E=B\setminus C$) yields that $S\left(  B\setminus
C\right)  =P$ if and only if $S\left(  \left(  B\setminus C\right)  \cup
C\right)  =P$. Since $S\left(  \left(  B\setminus C\right)  \cup C\right)  =P$
does hold (because $S\left(  \underbrace{\left(  B\setminus C\right)  \cup
C}_{=B}\right)  =S\left(  B\right)  =P$), we thus conclude that $S\left(
B\setminus C\right)  =P$.

It remains to show that $T\left(  B\setminus C\right)  =Q$.

First, we claim that $t\in Q$. Indeed, there exists some vertex $v\in Q$
(since $Q$ is nonempty). Consider this $v$. From $v\in Q$ and $V=P\sqcup Q$,
we obtain $v\notin P=S\left(  B\right)  $, and thus $v$ cannot $B$-reach $s$.
Hence, $v$ can $B$-reach $t$ (since each vertex can $B$-reach $s$ or $B$-reach
$t$). If $t$ could $B$-reach $s$, then this would entail that $v$ can also
$B$-reach $s$ (by concatenating the path from $v$ to $t$ and the path from $t$
to $s$), and this would contradict the fact that $v$ cannot $B$-reach $s$.
Hence, $t$ cannot $B$-reach $s$. In other words, $t\notin S\left(  B\right)
=P$, so that $t\in Q$ (since $V=P\sqcup Q$).

Let us now prove that $T\left(  B\setminus C\right)  \subseteq Q$. Indeed, let
$x\in T\left(  B\setminus C\right)  $ be any vertex. We must show that $x\in
Q$. Assume the contrary. Then, $x\in P$ (since $V=P\sqcup Q$). But $x\in
T\left(  B\setminus C\right)  $ shows that $x$ can $B\setminus C$-reach $t$.
So the digraph $D\left\langle B\setminus C\right\rangle $ has a path
$\mathbf{x}$ from $x$ to $t$. This path $\mathbf{x}$ starts at a vertex in $P$
(namely, at $x\in P$) and ends at a vertex in $Q$ (namely, at $t\in Q$). So
this path $\mathbf{x}$ must cross from $P$ to $Q$ at some point (since
$V=P\sqcup Q$). In other words, it must contain an arc that belongs to
$A\left(  P,Q\right)  $. But this is impossible, since all arcs of
$\mathbf{x}$ come from the set $B\setminus C$, which is disjoint from
$A\left(  P,Q\right)  $. This contradiction shows that $x\in Q$. Since we have
proved this for each $x\in T\left(  B\setminus C\right)  $, we thus conclude
that $T\left(  B\setminus C\right)  \subseteq Q$.

Now, we claim that $Q\subseteq T\left(  B\setminus C\right)  $. Indeed, let
$q\in Q$ be any vertex. Then, $q\notin P$ (since $V=P\sqcup Q$), so that
$q\notin P=S\left(  B\right)  $. In other words, $q$ cannot $B$-reach $s$.
Hence, $q$ can $B$-reach $t$ (since each vertex can $B$-reach $s$ or $B$-reach
$t$). That is, the digraph $D\left\langle B\right\rangle $ has a path
$\mathbf{q}$ from $q$ to $t$. Any vertex $w$ of this path $\mathbf{q}$ must
satisfy $w\notin P$ (since otherwise, $w$ would belong to $P=S\left(
B\right)  $ and thus could $B$-reach $s$, so that the digraph $D\left\langle
B\right\rangle $ would have a path $\mathbf{w}$ from $w$ to $s$; but then the
vertex $q$ could also $B$-reach $s$ by first following the path $\mathbf{q}$
from $q$ until $w$ and then following the path $\mathbf{w}$ from $w$ to $s$,
contradicting the fact that $q$ cannot $B$-reach $s$). Therefore, no arc of
the path $\mathbf{q}$ can belong to $A\left(  P,Q\right)  $ (since the source
of such an arc would be a vertex of $\mathbf{q}$ and belong to $P$). Thus, all
arcs of $\mathbf{q}$ belong to $B\setminus A\left(  P,Q\right)  =B\setminus
C$. Hence, $\mathbf{q}$ is a path of $D\left\langle B\setminus C\right\rangle
$. This shows that $q$ can $B\setminus C$-reach $t$ (via the path $\mathbf{q}%
$). In other words, $q\in T\left(  B\setminus C\right)  $. Since we have
proved this for each $q\in Q$, we thus conclude that $Q\subseteq T\left(
B\setminus C\right)  $.

Combining this with $T\left(  B\setminus C\right)  \subseteq Q$, we obtain
$T\left(  B\setminus C\right)  =Q$.

Altogether, we now have shown that $B\setminus C$ is an acyclic set in
$\mathcal{P}_{k-\left\vert C\right\vert }\left(  A\right)  $ and satisfies
$S\left(  B\setminus C\right)  =P$ and $T\left(  B\setminus C\right)  =Q$. In
other words, $B\setminus C\in X_{k-\left\vert C\right\vert }^{P,Q}$. Claim 1
is thus proved.
\end{proof}

\begin{statement}
\textit{Claim 2.} The map $\Psi$ is well-defined. That is, $E\cup C\in Y_{k}$
for all $E\in X_{k-|C|}^{P,Q}$.
\end{statement}

\begin{proof}
[Proof of Claim 2.]Let $E\in X_{k-|C|}^{P,Q}$. Then $E$ is an acyclic $\left(
k-\left\vert C\right\vert \right)  $-element subset of $A$ satisfying
$S\left(  E\right)  =P$ and $T\left(  E\right)  =Q$.

We must show that $E\cup C\in Y_{k}$. In other words, we must show that $E\cup
C\in U_{k}$, $S\left(  E\cup C\right)  =P$, and $\left(  E\cup C\right)  \cap
A\left(  P,Q\right)  =C$.

From $S\left(  E\right)  =P$, we immediately obtain $S\left(  E\cup C\right)
=P$ by Lemma \ref{lem.new0}.

Next, we show that $E\cap A\left(  P,Q\right)  =\varnothing$. Indeed, assume
the contrary. Then, there exists some arc $e\in E\cap A\left(  P,Q\right)  $.
Thus, $e\in E$ and $e\in A\left(  P,Q\right)  $. The latter shows that $e$ has
a source $p\in P$ and a target $q\in Q$. From $q\in Q=T\left(  E\right)  $, we
see that $q$ can $E$-reach $t$. Thus, $p$ can also $E$-reach $t$ (via the arc
$e\in E$ followed by the path from $q$ to $t$). Therefore, $p\in T\left(
E\right)  =Q$, which contradicts $p\in P$ because $V=P\sqcup Q$. This
contradiction shows that our assumption was false. Hence, $E\cap A\left(
P,Q\right)  =\varnothing$ is proved.

An analogous argument shows that $E\cap A\left(  Q,P\right)  =\varnothing$.

Note that the set $A\left(  P,Q\right)  $ is disjoint from $A\left(
Q,P\right)  $, since the source of an arc cannot belong to $P$ and $Q$ at the
same time (because of $V=P\sqcup Q$). Hence, the set $C$ (being a subset of
$A\left(  P,Q\right)  $) must be disjoint from $A\left(  Q,P\right)  $ as
well. In other words, $C\cap A\left(  Q,P\right)  =\varnothing$.

Also, note that $C$ is a subset of $A\left(  P,Q\right)  $, and thus we have
\[
E\cap\underbrace{C}_{\subseteq A\left(  P,Q\right)  }\subseteq E\cap A\left(
P,Q\right)  =\varnothing.
\]
Hence,
\begin{equation}
E\cap C=\varnothing, \label{pf.lem.new4.c2.pf.empty}%
\end{equation}
so that%
\[
\left\vert E\cup C\right\vert =\left\vert E\right\vert +\left\vert
C\right\vert =k\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left\vert
E\right\vert =k-\left\vert C\right\vert \right)  .
\]
Therefore, $E\cup C\in\mathcal{P}_{k}\left(  A\right)  $.

Furthermore,%
\[
\left(  E\cup C\right)  \cap A\left(  P,Q\right)  =\underbrace{\left(  E\cap
A\left(  P,Q\right)  \right)  }_{=\varnothing}\cup\underbrace{\left(  C\cap
A\left(  P,Q\right)  \right)  }_{\substack{=C\\\text{(since }C\subseteq
A\left(  P,Q\right)  \text{)}}}=\varnothing\cup C=C
\]
and%
\[
\left(  E\cup C\right)  \cap A\left(  Q,P\right)  =\underbrace{\left(  E\cap
A\left(  Q,P\right)  \right)  }_{=\varnothing}\cup\underbrace{\left(  C\cap
A\left(  Q,P\right)  \right)  }_{=\varnothing}=\varnothing\cup\varnothing
=\varnothing.
\]


Next, we show that $E\cup C$ is acyclic. Indeed, assume the contrary. Then,
the digraph $D\left\langle E\cup C\right\rangle $ has a cycle $\mathbf{c}$.
Since $E$ itself is acyclic, this cycle $\mathbf{c}$ must use at least one arc
from $C$. This arc must have source in $P$ and target in $Q$ (because it
belongs to $C\subseteq A\left(  P,Q\right)  $). Thus, the cycle $\mathbf{c}$
contains both a vertex in $P$ and a vertex in $Q$. Consequently, it must cross
from $Q$ to $P$ at some point (since $V=P\sqcup Q$). In other words, it
contains an arc $a\in A\left(  Q,P\right)  $. But such an arc $a$ cannot
belong to $E\cup C$ (since $\left(  E\cup C\right)  \cap A\left(  Q,P\right)
=\varnothing$). This is a contradiction, since it is an arc of $\mathbf{c}$,
which is a cycle of $D\left\langle E\cup C\right\rangle $. This contradiction
shows that our assumption was wrong, so $E\cup C$ is indeed acyclic.

Each vertex in $P$ can $E\cup C$-reach $s$ (since it lies in $P=S\left(  E\cup
C\right)  $). Each vertex in $Q$ can $E$-reach $t$ (since it lies in
$Q=T\left(  E\right)  $) and thus can $E\cup C$-reach $t$ as well (since
$E\subseteq E\cup C$). Since each vertex in $V$ belongs to either $P$ or $Q$
(because $V=P\sqcup Q$), we thus conclude that each vertex in $V$ can $E\cup
C$-reach $s$ (if it belongs to $P$) or can $E\cup C$-reach $t$ (if it belongs
to $Q$). This shows that $E\cup C\in U_{k}$ (since $E\cup C\in\mathcal{P}%
_{k}\left(  A\right)  $ is acyclic).

So, we have shown that $E\cup C\in U_{k}$, and $S\left(  E\cup C\right)  =P$,
and $\left(  E\cup C\right)  \cap A\left(  P,Q\right)  =C$. All together, this
yields $E\cup C\in Y_{k}$. Claim 2 is thus proved.
\end{proof}

\begin{statement}
\textit{Claim 3.} The maps $\Phi$ and $\Psi$ are mutually inverse.
\end{statement}

\begin{proof}
[Proof of Claim 3.]For each $B\in Y_{k}$, we have $B\cap A\left(  P,Q\right)
=C$ and therefore $C=B\cap A\left(  P,Q\right)  \subseteq B$. Thus, for each
$B\in Y_{k}$, we have%
\[
\Psi\left(  \Phi\left(  B\right)  \right)  =\Psi\left(  B\setminus C\right)
=\left(  B\setminus C\right)  \cup C=B\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}C\subseteq B\right)  .
\]
In other words, $\Psi\circ\Phi=\operatorname*{id}$.

On the other hand, for each $E\in X_{k-|C|}^{P,Q}$, we have $E\cap
C=\varnothing$ (see the equality (\ref{pf.lem.new4.c2.pf.empty}) in the proof
of Claim 2) and thus%
\[
\Phi\left(  \Psi\left(  E\right)  \right)  =\Phi\left(  E\cup C\right)
=\left(  E\cup C\right)  \setminus C=E\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}E\cap C=\varnothing\right)  .
\]
This shows that $\Phi\circ\Psi=\operatorname*{id}$.

From $\Phi\circ\Psi=\operatorname*{id}$ and $\Psi\circ\Phi=\operatorname*{id}%
$, we conclude that the maps $\Phi$ and $\Psi$ are mutually inverse. This
proves Claim 3.
\end{proof}

Claim 3 shows that the map $\Psi$ is a bijection from $X_{k-|C|}^{P,Q}$ to
$Y_{k}$. Thus,%
\[
\left\vert X_{k-|C|}^{P,Q}\right\vert =\left\vert Y_{k}\right\vert =\left\vert
\left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\text{ and }B\cap A\left(
P,Q\right)  =C\right\}  \right\vert
\]
(by the definition of $Y_{k}$).

We have proved this equality for each subset $C$ of $A\left(  P,Q\right)  $.
Summing it over all such subsets, we obtain%
\begin{align*}
\sum_{C\subseteq A\left(  P,Q\right)  }\left\vert X_{k-|C|}^{P,Q}\right\vert
&  =\sum_{C\subseteq A\left(  P,Q\right)  }\left\vert \left\{  B\in
U_{k}\ \mid\ S\left(  B\right)  =P\text{ and }B\cap A\left(  P,Q\right)
=C\right\}  \right\vert \\
&  =\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.lem.new4.sum}%
)}\right)  .
\end{align*}
Thus,%
\begin{align*}
\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert  &  =\sum_{C\subseteq A\left(  P,Q\right)  }\left\vert
X_{k-|C|}^{P,Q}\right\vert =\sum_{m\in\mathbb{N}}\ \ \sum
_{\substack{C\subseteq A\left(  P,Q\right)  ;\\\left\vert C\right\vert
=m}}\underbrace{\left\vert X_{k-|C|}^{P,Q}\right\vert }_{\substack{=\left\vert
X_{k-m}^{P,Q}\right\vert \\\text{(since }\left\vert C\right\vert =m\text{)}%
}}\\
&  =\sum_{m\in\mathbb{N}}\underbrace{\sum_{\substack{C\subseteq A\left(
P,Q\right)  ;\\\left\vert C\right\vert =m}}\left\vert X_{k-m}^{P,Q}\right\vert
}_{\substack{=\dbinom{\left\vert A\left(  P,Q\right)  \right\vert }{m}%
\cdot\left\vert X_{k-m}^{P,Q}\right\vert \\\text{(since this is a sum of
}\dbinom{\left\vert A\left(  P,Q\right)  \right\vert }{m}\\\text{many equal
addends)}}}\\
&  =\sum_{m\in\mathbb{N}}\dbinom{\left\vert A\left(  P,Q\right)  \right\vert
}{m}\cdot\left\vert X_{k-m}^{P,Q}\right\vert .
\end{align*}
This proves Lemma \ref{lem.new4}.
\end{proof}

\begin{lemma}
\label{lem.new5} Let $P$ and $Q$ be two nonempty subsets of $V$ such that
$V=P\sqcup Q$. Then,%
\[
\left\vert \left\{  B\in U_{k}\ \mid\ T\left(  B\right)  =Q\right\}
\right\vert =\sum_{m\in\mathbb{N}}\dbinom{\left\vert A\left(  Q,P\right)
\right\vert }{m}\cdot\left\vert X_{k-m}^{P,Q}\right\vert .
\]

\end{lemma}

\begin{proof}
Analogous to the proof of Lemma \ref{lem.new4}. (Just switch the roles of $s$
and $t$ and also the roles of $P$ and $Q$.)
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.new3}.]Lemma \ref{lem.new4} yields%
\begin{align*}
\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}
\right\vert  &  =\sum_{m\in\mathbb{N}}\dbinom{\left\vert A\left(  P,Q\right)
\right\vert }{m}\cdot\left\vert X_{k-m}^{P,Q}\right\vert \\
&  =\sum_{m\in\mathbb{N}}\dbinom{\left\vert A\left(  Q,P\right)  \right\vert
}{m}\cdot\left\vert X_{k-m}^{P,Q}\right\vert \\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since Proposition \ref{prop.A-symmetry}}\\
\text{yields }\left\vert A\left(  P,Q\right)  \right\vert =\left\vert A\left(
Q,P\right)  \right\vert
\end{array}
\right) \\
&  =\left\vert \left\{  B\in U_{k}\ \mid\ T\left(  B\right)  =Q\right\}
\right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma \ref{lem.new5}}\right)
.
\end{align*}
This proves Proposition \ref{prop.new3}.
\end{proof}

Now, Lemma \ref{lem.new1} yields%
\begin{align*}
\gamma_{k}\left(  s\right)   &  =\left\vert U_{k}\right\vert -\sum
_{\substack{P,Q\subseteq V\text{ are nonempty;}\\V=P\sqcup Q}%
}\underbrace{\left\vert \left\{  B\in U_{k}\ \mid\ S\left(  B\right)
=P\right\}  \right\vert }_{\substack{=\left\vert \left\{  B\in U_{k}%
\ \mid\ T\left(  B\right)  =Q\right\}  \right\vert \\\text{(by Proposition
\ref{prop.new3})}}}\\
&  =\left\vert U_{k}\right\vert -\sum_{\substack{P,Q\subseteq V\text{ are
nonempty;}\\V=P\sqcup Q}}\left\vert \left\{  B\in U_{k}\ \mid\ T\left(
B\right)  =Q\right\}  \right\vert =\gamma_{k}\left(  t\right)
\end{align*}
(by Lemma \ref{lem.new2}). This completes the proof of Theorem
\ref{thm.balgamma}.

\section{Further remarks}

\hspace{\parindent} \textbf{1.} One might wonder whether our proof of Theorem
\ref{thm.balgamma} is, or can be made, bijective. In the given form, it is
not, as it uses subtraction twice: once in proving Proposition
\ref{prop.A-symmetry} and once again in the \textquotedblleft subtractive
flip\textquotedblright\ that is involved in Lemma \ref{lem.new1} (and Lemma
\ref{lem.new2}). Both of these instances of subtraction can be made bijective
using the Garsia--Milne involution principle \cite[\S 4.6]{StaWhi86}.

In the case of Lemma \ref{lem.new1}, only the simplest case of the involution
principle is needed: Let $\Gamma_{k}\left(  s\right)  $ be the set of all
$s$-convergences of size $k$, and let $\Gamma_{k}\left(  t\right)  $ be the
set of all $t$-convergences of size $k$. Our above proof of Proposition
\ref{prop.new3} gives a bijection%
\[
\left\{  B\in U_{k}\ \mid\ S\left(  B\right)  =P\right\}  \rightarrow\left\{
B\in U_{k}\ \mid\ T\left(  B\right)  =Q\right\}
\]
for every pair of nonempty subsets $P,Q\subseteq V$ satisfying $V=P\sqcup Q$.
Combining these bijections for all such pairs $\left(  P,Q\right)  $, we
obtain a bijection $\phi:U_{k}\setminus\Gamma_{k}\left(  s\right)  \rightarrow
U_{k}\setminus\Gamma_{k}\left(  t\right)  $. Now we need to construct a
bijection $\psi:\Gamma_{k}\left(  s\right)  \rightarrow\Gamma_{k}\left(
t\right)  $ from it. The involution principle tells us that this $\psi$ acts
on a given element $B\in\Gamma_{k}\left(  s\right)  $ by repeatedly applying
$\phi^{-1}$ to it until it no longer belongs to $U_{k}\setminus\Gamma
_{k}\left(  t\right)  $ (which means that it belongs to $\Gamma_{k}\left(
t\right)  $). It is not hard to see that this does not require more than
$\left\vert V\right\vert $ many iterations, since $\left\vert T\left(
B\right)  \right\vert $ increases with each application of $\phi^{-1}$.

In the case of Proposition \ref{prop.A-symmetry}, however, we can also give a
direct bijective proof: By the directed Euler--Hierholzer theorem, each weak
component of the balanced digraph $D$ has a Eulerian circuit. Pick such a
circuit for each weak component of $D$. Note that on each of these circuits,
arcs from $A\left(  P,Q\right)  $ and arcs from $A\left(  Q,P\right)  $
alternate (if we remove the arcs from $A\left(  P,P\right)  $ and $A\left(
Q,Q\right)  $). Thus, we can define a bijection $A\left(  P,Q\right)
\rightarrow A\left(  Q,P\right)  $ that sends each arc $a\in A\left(
P,Q\right)  $ to the next arc $b\in A\left(  Q,P\right)  $ following it on the
chosen Eulerian circuit. At a second thought, this does not even require
Eulerian circuits; it suffices to pick any decomposition of $A$ into
(arc-disjoint) circuits.

\bigskip

\textbf{2.} We can also characterize $s$-convergences in terms of sinks.
Recall that a \emph{sink} of a digraph means a vertex with no outgoing arcs
(i.e., a vertex with outdegree $0$). Now our alternative characterization of
$s$-convergences is as follows:

\begin{proposition}
\label{prop.s-conv.2}Let $B$ be an acyclic subset of $A$. Let $s\in V$. Then,
$B$ is an $s$-convergence if and only if $s$ is the only sink of the
subdigraph $D\left\langle B\right\rangle $.
\end{proposition}

\begin{proof}
$\Longrightarrow$: Assume that $B$ is an $s$-convergence. Thus, $s$ is a
to-root of $D\left\langle B\right\rangle $.

We shall first show that $s$ is a sink of $D\left\langle B\right\rangle $.
Indeed, assume the contrary; thus, there exists an arc $a$ of $D\left\langle
B\right\rangle $ with source $s$. Let $v$ be the target of this arc $a$. Since
$s$ is a to-root of $D\left\langle B\right\rangle $, there exists a path from
$v$ to $s$ in $D\left\langle B\right\rangle $. This path, together with the
arc $a$, creates a cycle\footnote{If $v=s$, then this cycle consists of just a
single loop.} in $D\left\langle B\right\rangle $, which contradicts the
acyclicity of $B$. So, we see that $s$ is a sink of $D\left\langle
B\right\rangle $.

Furthermore, no vertex $v\neq s$ can also be a sink of $D\left\langle
B\right\rangle $, for $D\left\langle B\right\rangle $ must have a path from
$v$ to $s$ (because $s$ is a to-root of $D\left\langle B\right\rangle $) and
this path must begin with an arc with source $v$. So we conclude that $s$ is
the only sink of $D\left\langle B\right\rangle $. \medskip

$\Longleftarrow$: Assume that $s$ is the only sink of $D\left\langle
B\right\rangle $. Let $v\in V$ be any vertex.

The digraph $D\left\langle B\right\rangle $ has no cycles (since $B$ is
acyclic). Thus, any walk of $D\left\langle B\right\rangle $ is a path (since a
walk that is not a path would contain a cycle). Consequently, the walks of
$D\left\langle B\right\rangle $ are precisely the paths of $D\left\langle
B\right\rangle $. Hence, the digraph $D\left\langle B\right\rangle $ has only
finitely many walks that start at $v$ (since it clearly has only finitely many
\textbf{paths} that start at $v$). Moreover, there is at least one such walk
(the length-$0$ walk $\left(  v\right)  $).

Thus, there is a longest such walk. Let $\mathbf{p}$ be a such. Then,
$\mathbf{p}$ must end at a sink of $D\left\langle B\right\rangle $ (since
otherwise, we could extend $\mathbf{p}$ by an additional arc at the end,
obtaining an even longer walk that starts at $v$). Since the only sink of
$D\left\langle B\right\rangle $ is $s$, this means that $\mathbf{p}$ must end
at $s$. Thus, $\mathbf{p}$ is a walk from $v$ to $s$, hence a path from $v$ to
$s$ (since any walk of $D\left\langle B\right\rangle $ is a path). Hence,
$D\left\langle B\right\rangle $ has a path from $v$ to $s$ (namely,
$\mathbf{p}$). Since $v$ was arbitrary, this shows that $s$ is a to-root of
$D\left\langle B\right\rangle $. Therefore, $B$ is an $s$-convergence (since
$B$ is acyclic).
\end{proof}

\bigskip

\textbf{3.} In Lemma \ref{lem.new1}, Lemma \ref{lem.new2}, Lemma
\ref{lem.new4}, Lemma \ref{lem.new5} and Proposition \ref{prop.s-conv.2},
there is no need for the digraph $D$ to be balanced.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[22s]{22s}\href{https://arxiv.org/abs/2308.04512v3}{Darij Grinberg,
\textit{An introduction to graph theory}, arXiv:2308.04512v3.}

\bibitem[BanGut18]{BanGut18}%
\href{https://doi.org/10.1007/978-3-319-71840-8}{J\o rgen Bang-Jensen, Gregory
Gutin (eds.), \textit{Classes of Directed Graphs}, Springer 2018.}

\bibitem[Foissy22]{Foissy22}%
\href{https://arxiv.org/abs/2201.11974v5}{Lo\"{\i}c Foissy, \textit{Bialgebras
in cointeraction, the antipode and the eulerian idempotent},
arXiv:2201.11974v5.}

\bibitem[GreZas83]{GreZas83}%
\href{https://doi.org/10.1090/S0002-9947-1983-0712251-1}{Curtis Greene, Thomas
Zaslavsky, \textit{On the interpretation of Whitney numbers through
arrangement of hyperplanes, zonotopes, non-Radon partitions, and orientations
of graphs}. Trans. Amer. Math. Soc. \textbf{280}(1) (1983), pp. 97--126.}

\bibitem[LeiVal24]{LeiVal24}\href{https://arxiv.org/abs/2402.09914v3}{Karla
Leipold, Frank Vallentin, \textit{Computing the EHZ capacity is NP-hard},
arXiv:2402.09914v3.}

\bibitem[PerPha15]{PerPha15}K\'{e}vin Perrot, Trung Van Pham, \textit{Feedback
Arc Set Problem and NP-Hardness of Minimum Recurrent Configuration Problem of
Chip-Firing Game on Directed Graphs}, Annals of Combinatorics \textbf{19}
(2015), pages 373--396.

\bibitem[Perrot19]{Perrot19}%
\href{https://arxiv.org/abs/1909.03339v2}{K\'{e}vin Perrot, \textit{On the
complexity of counting feedback arc sets}, Chicago Journal of Theoretical
Computer Science 2022, Article 01, pages 1--8, arXiv:1909.03339v2.}

\bibitem[StaWhi86]{StaWhi86}%
\href{https://doi.org/10.1007/978-1-4612-4968-9}{Dennis Stanton, Dennis White,
\textit{Constructive Combinatorics}, Springer 1986.}
\end{thebibliography}


\end{document}