The induced saturation problem for posets

DOI10.5070/C63362792MaRDI QIDQ6204679zbMATH OpenOpenAlexFDO

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

Publication date 2 April 2024

Published in Combinatorial Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.03974

zbMATH Keywords

partially ordered setssaturationTurán-type problems

Mathematics Subject Classification ID

Extremal set theory (05D05) Combinatorics of partially ordered sets (06A07)

Abstract: For a fixed poset $P$, a family $mathcalF$ of subsets of $[n]$ is induced $P$-saturated if $mathcalF$ does not contain an induced copy of $P$, but for every subset $S$ of $[n]$ such that $SotinmathcalF$, then $P$ is an induced subposet of $mathcalFcupS$. The size of the smallest such family $mathcalF$ is denoted by $ext{sat}^{\ast }(n,P)$. Keszegh, Lemons, Martin, P'alv"olgyi and Patk'os [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset $P$, either $ext{sat}^{\ast }(n,P)=O(1)$ or $ext{sat}^{\ast }(n,P)geqlo{g}_{2}n$. In this paper we improve this general result showing that either $ext{sat}^{\ast }(n,P)=O(1)$ or $ext{sat}^{\ast }(n,P)geq2sqrtn-2$. Our proof makes use of a Tur'an-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 $ext{sat}^{\ast }(n,Diamond)=Theta(sqrtn)$; 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'alv"olgyi and Patk'os states that given any poset $P$, either $ext{sat}^{\ast }(n,P)=O(1)$ or $ext{sat}^{\ast }(n,P)geqn+1$. We prove that this latter conjecture is true for a certain class of posets $P$.

Cites work

• A Problem in Graph Theory
• A survey of minimum saturated graphs
• scientific article; zbMATH DE number 3333210 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Improved bounds for induced poset saturation
• Induced and non-induced poset saturation problems
• On saturated k-Sperner systems
• Progress on poset-free families of subsets
• Saturating Sperner families
• Saturation for small antichains
• Saturation for the butterfly poset
• The saturation number of induced subposets of the Boolean lattice

Cited in

(7)

• Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron
• Induced saturation of the poset 2C₂
• Poset saturation of unions of chains
• Projective and external saturation problem for posets
• Saturation of k-chains in the Boolean lattice
• Induced saturation for complete bipartite posets
• Gluing posets and the dichotomy of poset saturation numbers

This page was built for publication: The induced saturation problem for posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204679)