Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron

EUROCOMB’23

Paul Bastide Carla Groenland Hugo Jacob Tom Johnston

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-017

PDF
Abstract
For given positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$, but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use sat$^*(n, k)$ to denote the smallest size of such a family. For all $k$ and sufficiently large $n$, we determine the exact value of sat$^*(n, k)$. Our result implies that sat$^*(n, k)=n(k-1)-\Theta(k\log k)$, which confirms several conjectures on antichain saturation. Previously, exact values for sat$^*(n,k)$ were only known for $k$ up to $6$. We also prove a strengthening of a result of Lehman-Ron which may be of independent interest. We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). The complete version of the paper can be found here \cite{antichainsaturation}.

Pages:
120–126
References

Martin Aigner. Lexicographic matching in Boolean algebras. Journal of Combinatorial Theory, Series B, 14:187-194, 1973.
https://doi.org/10.1016/0095-8956(73)90001-4

Irina Ðanković and Maria-Romina Ivan. Saturation for small antichains. ArXiv preprint arXiv:2205.07392, 2022.
https://doi.org/10.37236/11262

Béla Bajnok and Shahriar Shahriari. Long symmetric chains in the boolean lattice. Journal of Combinatorial Theory, Series A, 75(1):44-54, 1996.
https://doi.org/10.1006/jcta.1996.0062

Paul Bastide, Carla Groenland, Hugo Jacob, and Tom Johnston. Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron. https://arxiv.org/abs/2207.07391.

Robert P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, pages 161-166, 1950.
https://doi.org/10.2307/1969503

Dwight Duffus, David Howard, and Imre Leader. The width of downsets. European Journal of Combinatorics, 79:46-59, 2019.
https://doi.org/10.1016/j.ejc.2018.11.005

Michael Ferrara, Bill Kay, Lucas Kramer, Ryan R Martin, Benjamin Reiniger, Heather C Smith, and Eric Sullivan. The saturation number of induced subposets of the Boolean lattice. Discrete Mathematics, 340(10):2479-2487, 2017.
https://doi.org/10.1016/j.disc.2017.06.010

Dániel Gerbner, Balázs Keszegh, Nathan Lemons, Cory Palmer, Dömötör Pálvölgyi, and Balázs Patkós. Saturating Sperner families. Graphs and Combinatorics, 29(5):1355-1364, 2013.
https://doi.org/10.1007/s00373-012-1195-6

Curtis Greene and Daniel J. Kleitman. Strong versions of Sperner's theorem. Journal of Combinatorial Theory, Series A, 20(1):80-88, 1976.
https://doi.org/10.1016/0097-3165(76)90079-0

Jerrold R. Griggs. Collections of subsets with the Sperner property. Transactions of the American Mathematical Society, 269(2):575-591, 1982.
https://doi.org/10.1090/S0002-9947-1982-0637711-2

Maria-Romina Ivan. Saturation for the butterfly poset. Mathematika, 66:806-817, 2020.
https://doi.org/10.1112/mtk.12044

Maria-Romina Ivan. Minimal diamond-saturated families. Contemporary Mathematics, 3(2), 2022.

Balázs Keszegh, Nathan Lemons, Ryan R. Martin, Dömötör Pálvölgyi, and Balázs Patkós. Induced and non-induced poset saturation problems. Journal of Combinatorial Theory, Series A, 184:105497, 2021.
https://doi.org/10.1016/j.jcta.2021.105497

D. J. Kleitman. On an extremal property of antichains in partial orders. the lym property and some of its implications and applications. In M. Hall and J. H. van Lint, editors, Combinatorics, pages 277-290. Springer Netherlands, 1975.
https://doi.org/10.1007/978-94-010-1826-5_14

Eric Lehman and Dana Ron. On disjoint chains of subsets. Journal of Combinatorial Theory, Series A, 94(2):399-404, 2001.
https://doi.org/10.1006/jcta.2000.3148

Mark J. Logan. Sperner theory in a difference of boolean lattices. Discrete Mathematics, 257:501-512, 2002.
https://doi.org/10.1016/S0012-365X(02)00509-5

Ryan R Martin, Heather C Smith, and Shanise Walker. Improved bounds for induced poset saturation. The Electronic Journal of Combinatorics, 27(2):P2.31, 2020.
https://doi.org/10.37236/8949

Karl Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10(1):96-115, 1927.
https://doi.org/10.4064/fm-10-1-96-115

Natasha Morrison, Jonathan A. Noel, and Alex Scott. On saturated k-Sperner systems. The Electronic Journal of Combinatorics, 21(3):P3.22, 2014.
https://doi.org/10.37236/4136

Michael Saks. A short proof of the existence of k-saturated partitions of partially ordered sets. Advances in Mathematics, 33:207-2011, 1979.
https://doi.org/10.1016/0001-8708(79)90010-0

Emanuel Sperner. Ein Satz über Untermengen einer endlichen Menge. Mathematische Zeitschrift, 27(1):544-548, 1928.
https://doi.org/10.1007/BF01171114

Benny Sudakov, István Tomon, and Adam Zsolt Wagner. Uniform chain decompositions and applications. Random Structures & Algorithms, 60(2):261-286, 2022.
https://doi.org/10.1002/rsa.21034

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Paul Bastide, Carla Groenland, Hugo Jacob, Tom Johnston

PDF