The induced saturation problem for posets

Andrea Freschi, Simón Piga, Maryam Sharifzadeh, Andrew Treglown

Research output: Working paper/PreprintPreprint

24 Downloads (Pure)

Abstract

For a fixed poset P, a family F of subsets of [n] is induced P-saturated if F does not contain an induced copy of P, but for every subset S of [n] such that S∉F, then 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)≥log2n. In this paper we improve this general result showing that either sat∗(n,P)=O(1) or sat∗(n,P)≥2n−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 ◊ 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 languageEnglish
Number of pages12
Publication statusPublished - 8 Jul 2022

Bibliographical note

12 pages

Keywords

  • math.CO
  • 06A07, 05D05

Fingerprint

Dive into the research topics of 'The induced saturation problem for posets'. Together they form a unique fingerprint.

Cite this