Combinatorial Theory

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á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\). 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á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\).

Mathematics Subject Classifications: 06A07, 05D05

Keywords: Partially ordered sets, saturation, Turán-type problems