Gale–Ryser theorem

A pair of sequences of nonnegative integers (a_1,\ldots,a_n) and (b_1,\ldots,b_m) with a_1\geq\cdots\geq a_n is bigraphic if and only if \sum_{i=1}^{n}a_i=\sum_{i=1}^{m}b_i and the following inequality holds for all k \in \{1, \ldots, n\}: : \sum^k_{i=1} a_i\leq \sum^m_{i=1} \min(b_i,k). Sometimes this theorem is stated with the additional constraint b_1\geq\cdots\geq b_m. This condition is not necessary, because the labels of vertices of one partite set in a bipartite graph can be rearranged arbitrarily. In 1962 Ford and Fulkerson gave a different but equivalent formulation of the theorem. ==Other notations==

The theorem can also be stated in terms of zero-one matrices. The connection can be seen if one realizes that each bipartite graph has a biadjacency matrix where the column sums and row sums correspond to (a_1,\ldots,a_n) and (b_1,\ldots,b_n). Each sequence can also be considered as an integer partition of the same number m=\sum_{i=1}^{n}a_i. It turns out that partition (a^*_1,\ldots,a^*_n) where a^*_k:=|\{b_i \mid b_i \geq k\}| is the conjugate partition of (b_1,\ldots,b_n). The conjugate partition can be determined by a Ferrers diagram. Moreover, there is a connection to the relation majorization. Consider sequences (a_1,\ldots,a_n), (b_1,\ldots,b_n) and (a^*_1,\ldots,a^*_n) as n-dimensional vectors a, b and a^*. Since \sum_{i=1}^k a^*_i =\sum^n_{i=1} \min(b_i,k) , the theorem above states that a pair of nonnegative integer sequences a and b with nonincreasing a is bigraphic if and only if the conjugate partition b^* of b majorizes a. A third formulation is in terms of degree sequences of simple directed graphs with at most one loop per vertex. In this case the matrix is interpreted as the adjacency matrix of such a directed graph. When are pairs of nonnegative integers ((a_1,b_1),...,(a_n,b_n)) the indegree-outdegree pairs of a labeled directed graph with at most one loop per vertex? The theorem can easily be adapted to this formulation, because there does not exist a special order of b. ==Proofs==

The proof is composed of two parts: the necessity of the condition and its sufficiency. We outline the proof of both parts in the language of matrices. To see that the condition in the theorem is necessary, consider the adjacency matrix of a bigraphic realization with row sums (b_1,\ldots,b_n) and column sums (a_1,\ldots,a_n), and shift all ones in the matrix to the left. The row sums remain, while the column sums are now a^*. The operation of shifting all ones to the left increases a partition in majorization order, and so a^* majorizes a. The original proof of sufficiency of the condition was rather complicated. gave a simple algorithmic proof. The idea is to start with the Ferrers diagram of b and shift ones to the right until the column sums are a. The algorithm runs in at most n steps, in each of which a single one entry is moved to the right. ==Stronger version==

Berger proved that it suffices to consider those kth inequalities such that 1 \leq k with a_k > a_{k+1} and the equality for k = n. ==Generalization==

A pair of finite sequences of nonnegative integers a and b with nonincreasing a is bigraphic if and only if \sum_{i=1}^{n}a_i=\sum_{i=1}^{n}b_i and there exists a sequence c such that the pair c,b is bigraphic and c majorizes a. Moreover, in is also proved that pair a and b has more bigraphic realizations than pair c and b. This yields to the result that regular sequences have for fixed numbers of vertices and edges the largest number of bigraphic realizations, if n divides m. They are the contrary sequences of threshold sequences with only one unique bigraphic realization, which is known as threshold graph. Minconvex sequences generalize this concept if n does not divide m. ==Characterizations for similar problems==

Similar theorems describe the degree sequences of simple graphs and simple directed graphs. The first problem is characterized by the Erdős–Gallai theorem. The latter case is characterized by the Fulkerson–Chen–Anstee theorem. ==Notes==