Projects per year
Abstract
For a fixed poset P, 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, 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) ≥ log_{2}n. We improve this general result showing that either sat* (n, P) = O(1) or sat* (n, P) ≥ 2√n2. Our proof 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 

Title of host publication  EUROCOMB’23 
Publisher  Masaryk University Press 
Pages  16 
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)  27883116 
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