TY - JOUR

T1 - AROUND THE ERDÖS–GALLAI CRITERION

AU - Baransky, Vitaly

AU - Senchonok, Tatiana

PY - 2023

Y1 - 2023

N2 - By an (integer) partition we mean a non-increasing sequence λ = (λ1,λ2,…) of non-negative integers that contains a finite number of non-zero components. A partition λ is said to be graphic if there exists a graph G such that λ = dptG, where we denote by dptG 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. © 2023, Krasovskii Institute of Mathematics and Mechanics. All rights reserved.

AB - By an (integer) partition we mean a non-increasing sequence λ = (λ1,λ2,…) of non-negative integers that contains a finite number of non-zero components. A partition λ is said to be graphic if there exists a graph G such that λ = dptG, where we denote by dptG 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. © 2023, Krasovskii Institute of Mathematics and Mechanics. All rights reserved.

UR - http://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=85166942630

UR - https://elibrary.ru/item.asp?id=54265303

U2 - 10.15826/umj.2023.1.003

DO - 10.15826/umj.2023.1.003

M3 - Article

VL - 9

SP - 29

EP - 48

JO - Ural Mathematical Journal

JF - Ural Mathematical Journal

SN - 2414-3952

IS - 1

ER -