The induced saturation problem for posets
Preprint
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$, $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\'alv\"olgyi and Patk\'os [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$. In this paper we improve this general result showing that either $\text{sat}^* (n,P)=O(1)$ or $\text{sat}^* (n,P) \geq \min\{ 2 \sqrt{n}, n/2+1\}$. Our proof makes use of a Tur\'an-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\'alv\"olgyi and Patk\'os 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$.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Exact antichain saturation numbers via a generalisation of a result of Lehman-RonCombinatorial Theory, 2024
- Saturation for Small AntichainsThe Electronic Journal of Combinatorics, 2023
- Minimal Diamond-Saturated FamiliesContemporary Mathematics, 2022
- Induced and non-induced poset saturation problemsJournal of Combinatorial Theory, Series A, 2021
- SATURATION FOR THE BUTTERFLY POSETMathematika, 2020
- Improved Bounds for Induced Poset SaturationThe Electronic Journal of Combinatorics, 2020
- The saturation number of induced subposets of the Boolean latticeDiscrete Mathematics, 2017
- On Saturated $k$-Sperner SystemsThe Electronic Journal of Combinatorics, 2014
- Saturating Sperner FamiliesGraphs and Combinatorics, 2012
- A Survey of Minimum Saturated GraphsThe Electronic Journal of Combinatorics, 2011