Around the ErdÖs–Gallai criterion

By an (integer) partition we mean a non-increasing sequence $\lambda=(\lambda_1, \lambda_2, \dots)$ of non-negative integers that contains a finite number of non-zero components. A partition $\lambda$ is said to be graphic if there exists a graph $G$ such that $\lambda = \mathrm{dpt}\,G$, where we denote by $\mathrm{dpt}\,G$ the degree partition of $G$ composed of the degrees of its vertices, taken in non-increasing order and added with zeros. In this paper, we propose to consider another criterion for a partition to be graphic, the ht-criterion, which, in essence, is a convenient and natural reformulation of the well-known Erdös–Gallai criterion for a sequence to be graphical. The ht-criterion fits well into the general study of lattices of integer partitions and is convenient for applications. The paper shows the equivalence of the Gale–Ryser criterion on the realizability of a pair of partitions by bipartite graphs, the ht-criterion and the Erdös–Gallai criterion. New proofs of the Gale–Ryser criterion and the Erdös–Gallai criterion are given. It is also proved that for any graphical partition there exists a realization that is obtained from some splitable graph in a natural way. A number of information of an overview nature is also given on the results previously obtained by the authors which are close in subject matter to those considered in this paper.