Fulkerson-Chen-Anstee Theorem
Get Fulkerson%E2%80%93Chen%E2%80%93Anstee Theorem essential facts below. View Videos or join the Fulkerson%E2%80%93Chen%E2%80%93Anstee Theorem discussion. Add Fulkerson%E2%80%93Chen%E2%80%93Anstee Theorem to your PopFlock.com topic list for future reference or share this resource on social media.
Fulkerson%E2%80%93Chen%E2%80%93Anstee Theorem

The Fulkerson-Chen-Anstee theorem is a result in graph theory, a branch of combinatorics. It provides one of two known approaches solving the digraph realization problem, i.e. it gives a necessary and sufficient condition for pairs of nonnegative integers ${\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$ to be the indegree-outdegree pairs of a simple directed graph; a sequence obeying these conditions is called "digraphic". D. R. Fulkerson [1] (1960) obtained a characterization analogous to the classical Erd?s-Gallai theorem for graphs, but in contrast to this solution with exponentially many inequalities. In 1966 Chen [2] improved this result in demanding the additional constraint that the integer pairs must be sorted in non-increasing lexicographical order leading to n inequalities. Anstee [3] (1982) observed in a different context that it is suffient to have ${\displaystyle a_{1}\geq \cdots \geq a_{n}}$. Berger [4] reinvented this result and gives a direct proof.

## Theorem statement

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)}$

## Stronger versions

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

## Other notations

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}$.

## Generalization

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]

## Characterizations for similar problems

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.

## References

1. ^ D.R. Fulkerson: Zero-one matrices with zero trace. In: Pacific J. Math. No. 12, 1960, pp. 831-836
2. ^ Wai-Kai Chen: On the realization of a (p,s)-digraph with prescribed degrees . In: Journal of the Franklin Institute No. 6, 1966, pp. 406-422
3. ^ Richard Anstee: Properties of a class of (0,1)-matrices covering a given matrix. In: Can. J. Math., 1982, pp. 438-453
4. ^ a b c Annabell Berger: A Note on the Characterization of Digraphic Sequences In: Discrete Mathematics, 2014, pp. 38-41
5. ^ Annabell Berger: The connection between the number of realizations for degree sequences and majorization In: arXiv1212.5443, 2012