В.А. Баранский, В.В. Зуев. О решетках, ассоциированных с максимальными графическими разбиениями ... С. 32-42

УДК 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]