Projects per year
Abstract
For a fixed posetP, a family F of subsets of[n]is induced Psaturated if F does not contain an induced copy of P, but for every subset S of [n] such that S̸∈F, P is an induced subposet of F∪{S}. The size of the smallest such family F is denoted by 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 sat^{∗}(n, P) = O(1) or sat^{∗}(n, P) ⩾ log_{2}n. In this paper we improve this general result showing that either sat^{∗}(n, P) = O(1)or sat^{∗}(n, P) ⩾ min{2√n, n/2 + 1}. Ourproof makes use of a Turántype 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 socalled diamond poset ♢ we have sat^{∗}(n,♢) = Θ(√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 sat^{∗}(n, P) = O(1)or sat^{∗}(n, P) ⩾ n+ 1. We prove that this latter conjecture is true for a certain class of posets P.
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 socalled diamond poset ♢ we have sat^{∗}(n,♢) = Θ(√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 sat^{∗}(n, P) = O(1)or sat^{∗}(n, P) ⩾ n+ 1. We prove that this latter conjecture is true for a certain class of posets P.
Original language  English 

Article number  9 
Number of pages  15 
Journal  Combinatorial Theory 
Volume  3 
Issue number  3 
DOIs  
Publication status  Published  22 Dec 2023 
Bibliographical note
Funding:Research supported by EPSRC grant EP/V002279/1.
Keywords
 Partially ordered sets
 saturation
 Turántype problems
Fingerprint
Dive into the research topics of 'The induced saturation problem for posets'. Together they form a unique fingerprint.Projects
 1 Finished

Matchings and tilings in graphs
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils