Projects per year
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. We improve this general result showing that either sat* (n, P) = O(1) or sat* (n, P) ≥ 2√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 ◊ 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 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 language | English |
---|---|
Title of host publication | EUROCOMB’23 |
Publisher | Masaryk University Press |
Pages | 1-6 |
Number of pages | 6 |
DOIs | |
Publication status | Published - 28 Aug 2023 |
Event | European Conference on Combinatorics, Graph Theory and Applications - Charles University, Faculty of Mathematics and Physics, Prague, Czech Republic Duration: 28 Aug 2023 → 1 Sept 2023 https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/ |
Publication series
Name | European Conference on Combinatorics, Graph Theory and Applications |
---|---|
Publisher | Masaryk University Press |
Number | 12 |
ISSN (Electronic) | 2788-3116 |
Conference
Conference | European Conference on Combinatorics, Graph Theory and Applications |
---|---|
Abbreviated title | EUROCOMB'23 |
Country/Territory | Czech Republic |
City | Prague |
Period | 28/08/23 → 1/09/23 |
Internet address |
Fingerprint
Dive into the research topics of 'A general bound for the induced poset saturation problem'. 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