V.A. Baransky, V.V. Zuev. On lattices associated with maximal graphical partitions ... P. 32-42

The aim of this paper is to describe, for a given graphical partition $\lambda$ of weight $2m$ and rank $r$, the set of all maximal graphical partitions $\mu$ of weight $2m$ that dominate $\lambda$. To do this, it is enough to find the set of heads of such partitions. Theorem 1 states that, for any natural number $t$, the set of heads of all maximal graphical partitions $\mu$ of weight $2m$ and rank $t$ dominating $\lambda$ forms an interval of the integer partition lattice if such partitions $\mu$ of rank $t$ exist. Algorithms are also provided for finding the smallest and largest elements of this interval.

Keywords: lattice, integer partition, Ferrers diagram, graph, maximal graphical partition

Received November 30, 2023

Revised December 19, 2023

Accepted December 25, 2023

Vitaly Anatolievich Baransky, Dr. Phys.-Math. Sci., Prof., Ural Federal University Yekaterinburg, 620000 Russia, e-mail: vitaly.baransky@urfu.ru

Valentin Viktorovich Zuev, doctoral student, Ural Federal University Yekaterinburg, 620000 Russia, e-mail: valentin.zuev@urfu.ru

REFERENCES

1.   Andrews G.E. The theory of partitions. Cambridge: Cambridge University Press, 1976. 255 p.

2.   Brylawski T. The lattice of integer partitions. Discrete Math., 1973, vol. 6, no. 3, pp. 201–219. doi: 10.1016/0012-365X(73)90094-0

3.   Baransky V.A., Senchonok T.A. On maximal graphical partitions that are the nearest to a given graphical partition. Sib. Elect. Math. Reports, 2020, vol. 17, pp. 338–363 (in Russian). doi: 10.33048/semi.2020.17.022

4.   Erdős P., Gallai T. Graphs with given degree of vertices. Math. Lapok, 1960, vol. 11, pp. 264–274.

5.   Sierksma G., Hoogeven H. Seven criteria for integer sequences being graphic. J. Graph Theory, 1991, vol. 15, no. 2. P. 223–231. doi: 10.1002/jgt.3190150209

6.   Kohnert A. Dominance order and graphical partitions. Elec. J. Comb., 2004, vol. 11, no. 1, art. no. N4, pp. 1–17. doi: 10.37236/1845

7.   Baransky V.A., Senchonok T.A. On maximal graphical partitions. Sib. Electron. Mat. Izv., 2017, vol. 14, pp. 112–124 (in Russian). doi: 10.17377/semi.2017.14.012

8.   Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Ser. Annals of Discr. Math., vol.  56, Amsterdam: North-Holland Publishing Co., 1995, 542  p.

Cite this article as: V.A. Baransky, V.V. Zuev. On lattices associated with maximal graphical partitions. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2024, vol. 30, no. 1, pp. 32–42.