A general bound for the induced poset saturation problem

EUROCOMB’23

Andrea Freschi Simon Piga Maryam Sharifzadeh Andrew Treglown

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

PDF
Abstract
For a fixed poset $P$, a family $\mathcal F$ of subsets of $[n]$ is induced $P$-saturated if $\mathcal F$ does not contain an induced copy of $P$, but for every subset $S$ of $[n]$ such that $ S\not \in \mathcal F$, then $P$ is an induced subposet of $\mathcal F \cup \{S\}$. The size of the smallest such family $\mathcal F$ is denoted by $\text{sat}^* (n,P)$. Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset $P$, either $\text{sat}^* (n,P)=O(1)$ or $\text{sat}^* (n,P)\geq \log _2 n$. We improve this general result showing that either $\text{sat}^* (n,P)=O(1)$ or $\text{sat}^* (n,P) \geq 2 \sqrt{n-2}$. Our proof makes use of a Turán-type result for digraphs. Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states that for the so-called diamond poset $\Diamond$ we have $\text{sat}^* (n,\Diamond)=\Theta (\sqrt{n})$; so if true this conjecture implies our result is tight up to a multiplicative constant. On the other hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states that given any poset $P$, either $\text{sat}^* (n,P)=O(1)$ or $\text{sat}^* (n,P)\geq n+1$. We prove that this latter conjecture is true for a certain class of posets $P$.

Pages:
457–462
References

Paul Bastide, Carla Groenland, Hugo Jacob, and Tom Johnston. Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron. arXiv:2207.07391, 2022.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-017

William G. Brown and Frank Harary. Extremal digraphs. Colloquia Mathematica Societatis János Bolyai, 4:135-198, 1969.

Bryan L. Currie, Jill R. Faudree, Ralph J. Faudree, and John R. Schmitt. A survey of minimum saturated graphs. The Electronic Journal of Combinatorics, DS19, 2011.

Irina Ðanković and Maria-Romina Ivan. Saturation for small antichains. The Electronic Journal of Combinatorics, 30(1): P1.3, 2023.
https://doi.org/10.37236/11262

Paul Erdős, András Hajnal, and John W. Moon. A problem in graph theory. The American Mathematical Monthly, 71(10): 1107-1110, 1964.
https://doi.org/10.2307/2311408

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

Andrea Freschi, Simón Piga, Maryam Sharifzadeh, and Andrew Treglown. The induced saturation problem for posets. arXiv:2207.03974, 2022.

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

Jerrold R. Griggs and Wei-Tian Li. Progress on poset-free families of subsets. Recent Trends in Combinatorics, The IMA Volumes in Mathematics and its Applications, vol. 159, 317-338. Springer, New York, 2016.
https://doi.org/10.1007/978-3-319-24298-9_14

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

Maria-Romina Ivan. Minimal diamond-saturated families. Contemporary Mathematics, 3(2):81-88, 2022.
https://doi.org/10.37256/cm.3220221333

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

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

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

Paul Turán. On an extremal problem in graph theory. Matematikai és Fizikai Lapok, 48: 436-452, 1941.

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 Andrea Freschi, Simon Piga, Maryam Sharifzadeh, Andrew Treglown

PDF