The Gale–Ryser theorem is a result in graph theory and combinatorial matrix theory, two branches of combinatorics. It provides one of two known approaches to solving the bipartite realization problem, i.e. it gives a necessary and sufficient condition for two finite sequences of natural numbers to be the degree sequence of a labeled simple bipartite graph; a sequence obeying these conditions is called "bigraphic". It is an analog of the Erdős–Gallai theorem for simple graphs. The theorem was published independently in 1957 by H. J. Ryser and David Gale.
Contents
Statement
A pair of sequences of nonnegative integers
(
a
1
,
…
,
a
n
)
{\displaystyle (a_{1},\ldots ,a_{n})}
and
(
b
1
,
…
,
b
m
)
{\displaystyle (b_{1},\ldots ,b_{m})}
with
a
1
≥
⋯
≥
a
n
{\displaystyle a_{1}\geq \cdots \geq a_{n}}
is bigraphic if and only if
∑
i
=
1
n
a
i
=
∑
i
=
1
m
b
i
{\displaystyle \sum _{i=1}^{n}a_{i}=\sum _{i=1}^{m}b_{i}}
and the following inequality holds for all
k
∈
{
1
,
…
,
n
}
{\displaystyle k\in \{1,\ldots ,n\}}
:
∑
i
=
1
k
a
i
≤
∑
i
=
1
m
min
(
b
i
,
k
)
.
{\displaystyle \sum _{i=1}^{k}a_{i}\leq \sum _{i=1}^{m}\min(b_{i},k).}
Sometimes this theorem is stated with the additional constraint
b
1
≥
⋯
≥
b
m
{\displaystyle 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
,
…
,
a
n
)
{\displaystyle (a_{1},\ldots ,a_{n})}
and
(
b
1
,
…
,
b
n
)
{\displaystyle (b_{1},\ldots ,b_{n})}
.
Each sequence can also be considered as an integer partition of the same number
m
=
∑
i
=
1
n
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
,
…
,
b
n
)
{\displaystyle (b_{1},\ldots ,b_{n})}
and column sums
(
a
1
,
…
,
a
n
)
{\displaystyle (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
∗
{\displaystyle a^{*}}
. The operation of shifting all ones to the left increases a partition in majorization order, and so
Stronger version
Berger proved that it suffices to consider those
k
{\displaystyle k}
th inequalities such that
1
≤
k
<
n
{\displaystyle 1\leq k<n}
with
a
k
>
a
k
+
1
{\displaystyle a_{k}>a_{k+1}}
and the equality for
k
=
n
{\displaystyle k=n}
.
Generalization
A pair of finite sequences of nonnegative integers
a
{\displaystyle a}
and
b
{\displaystyle b}
with nonincreasing
a
{\displaystyle a}
is bigraphic if and only if
∑
i
=
1
n
a
i
=
∑
i
=
1
n
b
i
{\displaystyle \sum _{i=1}^{n}a_{i}=\sum _{i=1}^{n}b_{i}}
and there exists a sequence
c
{\displaystyle c}
such that the pair
c
,
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.