On maximal graphical partitions that are the nearest to a given graphical partition

V. A. Baransky ; T. A. Senchonok

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 338-363.

Résumé

A graphical partition is called maximal if it is maximal under domination among graphical partitions of a given weight. Let $\lambda$ and $\mu$ be partitions such that $\mu\leq\lambda$. The height of $\lambda$ over $\mu$ is the number of transformations in some shortest sequence of elementary transformations which transforms $\lambda$ to $\mu$, denoted by $\mathrm{height}(\lambda,\mu)$. For a given graphical partition $\mu$, a maximal graphical partition $\lambda$ such that $\mu\leq\lambda$ and $\mathrm{sum}(\mu)= \mathrm{sum}(\lambda)$ is called the $h$-nearest to $\mu$ if it has the minimal height over $\mu$ among all maximal graphical partitions $\lambda'$ such that $\mu\leq\lambda'$ and $\mathrm{sum}(\mu)= \mathrm{sum}(\lambda')$. The aim is to prove the following result: Let $\mu$ be a graphical partition and $\lambda$ be an $h$-nearest maximal graphical partition to $\mu$. Then either $r(\lambda)=r(\mu)-1$, $l(\mathrm{tl}(\mu))$ or $r(\lambda)=r(\mu)$, $\mathrm{height}(\lambda,\mu)= \mathrm{height}(\mathrm{tl}(\mu), \mathrm{hd}(\mu))- \frac{1}{2}[\mathrm{sum}(\mathrm{tl}(\mu))-\mathrm{sum}(\mathrm{hd}(\mu))]= \frac{1}{2}\sum^r_{i=1}|\mathrm{tl}(\mu)_i-\mathrm{hd}(\mu)_i|,$ where $r=r(\mu)$ is the rank, $\mathrm{hd}(\mu))$ is the head and $\mathrm{tl}(\mu))$ is the tail of the partition $\mu$, $l(\mathrm{tl}(\mu))$ is the length of $\mathrm{tl}(\mu)$. We provide an algorithm that generates some $h$-nearest to $\mu$ maximal graphical partition $\lambda$ such that $r(\lambda)=r(\mu)$. For the case $l(\mathrm{tl}(\mu))$, we also provide an algorithm that generates some $h$-nearest to $\mu$ maximal graphical partition $\lambda$ such that $r(\lambda)=r(\mu)-1$. In addition we present a new proof of the Kohnert's criterion for a partition to be graphical not using other criteria.

Détail

Keywords: threshold graphs, lattice of integer partitions, graphical partition, maximal graphical partition, Ferrer's diagram.

Bibliographie

[1] M.O. Asanov, V.A. Baransky, V.V. Rasin, Diskretnaya matematika: grafy, matroidy, algoritmy, Lan', SPb, 2010 (In Russian) | MR

[2] G.E. Andrews, The theory of partitions, Cambridge University Press, Cambridge, 1976 | MR | Zbl

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

[4] V.A. Baransky, T.A. Koroleva, T.A. Senchonok, “O reshetke razbieniy natural'nogo chisla”, Tr. Inst. Mat. Mekh., 21, no. 3, 2015, 30–36 | MR

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

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

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

[8] A. Kohnert, “Dominance order and graphical partitions”, Electron. J. Comb., 11:1 (2004), 4, 1–17 | MR | Zbl

[9] P. Erdös, T. Gallai, “Graphs with given degree of vertices”, Math. Lapok, 11 (1960), 264–274

[10] N.V.R. Mahadev, U.N. Peled, Threshold Graphs and Related Topics, Annals of Discrete Mathematics, 56, Elsevier Science, Amsterdam, 1995 | MR | Zbl

[11] V.A. Baransky, T.A. Senchonok, “O porogovyh grafah i realizaciyah graficheskih razbienii”, Tr. Inst. Mat. Mekh. UrO PAN, 23, no. 2, 2017, 1–10 (In Russian)

[12] D.R. Fulkerson, A.J. Hoffman, M.H. McAndrew, “Some properties of graphs with multiple edged”, Canadian J. Math., 17 (1965), 166–177 | MR | Zbl

[13] O. Mel'nikov, R.I. Tyshkevich, V.A. Emelichev, V.N. Sarvanov, Lectures on graph theory, Wissenschaftsverlag, Mannheim, 1994 | MR | Zbl

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

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

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