УДК 519.176
MSC: 05A17, 05C07, 05C35
DOI: 10.21538/0134-4889-2024-30-1-32-42
Цель данной работы состоит в описании для заданного графического разбиения $\lambda$ веса $2m$ и ранга $r$ множества всех максимальных графических разбиений $\mu$ веса $2m$, доминирующих $\lambda$. Для этого достаточно найти множество голов таких разбиений. В теореме 1 установлено, что для любого натурального числа $t$ множество голов всех максимальных графических разбиений $\mu$ веса $2m$ и ранга $t$, доминирующих $\lambda$, образует интервал решетки всех целочисленных разбиений, если такие разбиения $\mu$ ранга $t$ существуют. Указаны алгоритмы вычисления наибольших и наименьших разбиений в этих интервалах.
Ключевые слова: решетка, целочисленное разбиение, диаграмма Ферре, граф, максимальное графическое разбиение
СПИСОК ЛИТЕРАТУРЫ
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. P. 201–219. doi: 10.1016/0012-365X(73)90094-0 .
3. Баранский В.А., Сеньчонок Т.А. О максимальных графических разбиениях, ближайших к заданному графическому разбиению // Сиб. электрон. мат. изв. 2020. Т. 17. С. 338–363. doi: 10.33048/semi.2020.17.022 .
4. Erdős P., Gallai T. Graphs with given degree of vertices // Math. Lapok. 1960. Vol. 11. P. 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. P. 1–17. doi: 10.37236/1845 .
7. Баранский В.А., Сеньчонок Т.А. О максимальных графических разбиениях // Сиб. электрон. мат. изв. 2017. Т. 14. С. 112–124. doi: 10.17377/semi.2017.14.012 .
8. Mahadev N.V.R., Peled U.N. Threshold graphs and related topics. Amsterdam: North-Holland Publishing Co., 1995. 542 p. (Ser. Annals of Discr. Math.; vol. 56.)
Поступила 30.11.2023
После доработки 19.12.2023
Принята к публикации 25.12.2023
Баранский Виталий Анатольевич
д-р физ.-мат. наук, профессор
профессор
Уральский федеральный университет
г. Екатеринбург
e-mail: vitaly.baransky@urfu.ru
Зуев Валентин Викторович
аспирант
Уральский федеральный университет
г. Екатеринбург
e-mail: valentin.zuev@urfu.ru
Ссылка на статью: В.А. Баранский, В.В. Зуев. О решетках, ассоциированных с максимальными графическими разбиениями // Тр. Ин-та математики и механики УрО РАН. 2024.Т.30, № 1. С. 32-42
English
V.A. Baransky, V.V. Zuev. On lattices associated with maximal graphical partitions
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
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.
[References -> on the "English" button bottom right]
