Fulkerson–Chen–Anstee theorem

A sequence ${\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$ of nonnegative integer pairs with ${\displaystyle a_{1}\geq \cdots \geq a_{n}}$ is digraphic if and only if ${\displaystyle \sum _{i=1}^{n}a_{i}=\sum _{i=1}^{n}b_{i}}$ and the following inequality holds for k such that ${\displaystyle 1\leq k\leq n}$:

${\displaystyle \sum _{i=1}^{k}a_{i}\leq \sum _{i=1}^{k}\min(b_{i},k-1)+\sum _{i=k+1}^{n}\min(b_{i},k)}$

Berger proved[4] that it suffices to consider the ${\displaystyle k}$th inequality such that ${\displaystyle 1\leq k<n}$ with ${\displaystyle a_{k}>a_{k+1}}$ and for ${\displaystyle k=n}$.

The theorem can also be stated in terms of zero-one matrices. The connection can be seen if one realizes that each directed graph has an adjacency matrix where the column sums and row sums correspond to ${\displaystyle (a_{1},\ldots ,a_{n})}$ and ${\displaystyle (b_{1},\ldots ,b_{n})}$. Note that the diagonal of the matrix only contains zeros. There is a connection to the relation majorization. We define a sequence ${\displaystyle (a_{1}^{*},\ldots ,a_{n}^{*})}$ with ${\displaystyle a_{k}^{*}:=|\{b_{i}|i>k,b_{i}\geq k\}|+|\{b_{i}|i\leq k,b_{i}\geq k-1\}|}$. Sequence ${\displaystyle (a_{1}^{*},\ldots ,a_{n}^{*})}$ can also be determined by a corrected Ferrers diagram. Consider sequences ${\displaystyle (a_{1},\ldots ,a_{n})}$, ${\displaystyle (b_{1},\ldots ,b_{n})}$ and ${\displaystyle (a_{1}^{*},\ldots ,a_{n}^{*})}$ as ${\displaystyle n}$-dimensional vectors ${\displaystyle a}$, ${\displaystyle b}$ and ${\displaystyle a^{*}}$. Since ${\displaystyle \sum _{i=1}^{k}a_{i}^{*}=\sum _{i=1}^{k}\min(b_{i},k-1)+\sum _{i=k+1}^{n}\min(b_{i},k)}$ by applying the principle of double counting, the theorem above states that a pair of nonnegative integer sequences ${\displaystyle (a,b)}$ with nonincreasing ${\displaystyle a}$ is digraphic if and only if vector ${\displaystyle a^{*}}$ majorizes ${\displaystyle a}$.

A sequence ${\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$ of nonnegative integer pairs with ${\displaystyle a_{1}\geq \cdots \geq a_{n}}$ is digraphic if and only if ${\displaystyle \sum _{i=1}^{n}a_{i}=\sum _{i=1}^{n}b_{i}}$ and there exists a sequence ${\displaystyle c}$ such that the pair ${\displaystyle (c,b)}$ is digraphic and ${\displaystyle c}$ majorizes ${\displaystyle a}$.[5]

Similar theorems describe the degree sequences of simple graphs, simple directed graphs with loops, and simple bipartite graphs. The first problem is characterized by the Erdős–Gallai theorem. The latter two cases, which are equivalent see Berger,[4] are characterized by the Gale–Ryser theorem.

• Kleitman–Wang algorithms