Around the ErdÖs–Gallai criterion

Vitaly A. Baransky   ; Tatiana A. Senchonok

Ural mathematical journal, Tome 9 (2023) no. 1, pp. 29-48

Résumé

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.

Détail

Keywords: threshold graph, bipartite-threshold graph, Ferrers diagram.
Mots-clés : integer partition, bipartite graph

Bibliographie

[1] Andrews G. E., The Theory of Partitions, Cambridge University Press, Cambridge, 1984, 255 pp. | DOI | MR | Zbl

[2] Baransky V. A., Koroleva T. A., “The lattice of partitions of a positive integer”, Doklady Math., 77:1 (2008), 72–75 | DOI | MR | Zbl

[3] Baransky V. A., Koroleva T. A., Senchonok T. A., “On the partition lattice of an integer”, Trudy Inst. Mat. i Mekh. UrO RAN, 21:3 (2015), 30—36 (in Russian) | MR

[4] Baransky V. A., Nadymova T. I., Senchonok T. A., “A new algorithm generating graphical sequences”, Sib. Electron. Mat. Izv., 13 (2016), 269–279 (in Russian) | DOI | MR | Zbl

[5] Baransky V. A., Koroleva T. A., Senchonok T. A., “On the partition lattice of all integers”, Sib. Electron. Mat. Izv., 13 (2016), 744–753 (in Russian) | DOI | MR | Zbl

[6] Baransky V. A., Senchonok T. A., “On maximal graphical partitions”, Sib. Electron. Mat. Izv., 14 (2017), 112–124 (in Russian) | DOI | MR | Zbl

[7] Baransky V. A., Senchonok T. A., “On threshold graphs and realizations of graphical partitions”, Trudy Inst. Mat. i Mekh. UrO RAN, 23:2 (2017), 22–31 (in Russian) | MR

[8] Baransky V. A., Senchonok T. A., “On the shortest sequences of elementary transformations in the partition lattice”, Sib. Electron. Mat. Izv., 15 (2018), 844–852 (in Russian) | DOI | MR | Zbl

[9] Baransky V. A., Senchonok T. A., “On maximal graphical partitions that are the nearest to a given graphical partition”, Sib. Electron. Mat. Izv., 17 (2020), 338–363 (in Russian) | DOI | MR | Zbl

[10] Baransky V. A., Senchonok T. A., “Bipartite threshold graphs”, Trudy Inst. Mat. i Mekh. UrO RAN, 26:2 (2020), 56–67 (in Russian) | DOI | MR

[11] Baransky V. A., Senchonok T. A., “An algorithm for taking a bipartite graph to the bipartite threshold form”, Trudy Inst. Mat. i Mekh. UrO RAN, 28:4 (2022), 54–63 (in Russian) | DOI | MR

[12] Baransky V. A., Senchonok T. A., “Bipartite-threshold graphs and lifting rotations of edges in bipartite graphs”, Trudy Inst. Mat. i Mekh. UrO RAN, 29:1 (2023), 24–35 (in Russian) | DOI | MR

[13] Brylawski T., “The lattice of integer partitions”, Discrete Math., 6:3 (1973), 201–219 | DOI | MR | Zbl

[14] Erdös P., Gallai T., “Graphs with given degree of vertices”, Mat. Lapok, 11 (1960), 264—274 (in Hungarian)

[15] Kohnert A., “Dominance order and graphical partitions”, Elec. J. Comb., 11:1 (2004), N4, 1–17 | DOI | MR | Zbl

[16] Mahadev N. V. R., Peled U. N., Threshold Graphs and Related Topics, v. 56, Annals of Discr. Math., North-Holland Publishing Co., Amsterdam, 1995, 542 pp. | MR

[17] Sierksma G., Hoogeven H., “Seven criteria for integer sequences being graphic”, J. Graph Theory, 15:2 (1991), 223–231 | DOI | MR | Zbl