TY - JOUR
T1 - A polynomial upper bound for poset saturation
AU - Bastide, Paul
AU - Groenland, Carla
AU - Ivan, Maria Romina
AU - Johnston, Tom
PY - 2024
Y1 - 2024
N2 - Given a finite poset P, we say that a family F of subsets of [n] is P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The induced saturation number of P, denoted by sat∗(n,P), is the size of the smallest P-saturated family with ground set [n]. In this paper we prove that the saturation number for any given poset grows at worst polynomially. More precisely, we show that sat∗(n,P)=O(nc), where c≤|P|2/4+1 is a constant depending on P only. We obtain this result by bounding the VC-dimension of our family.
AB - Given a finite poset P, we say that a family F of subsets of [n] is P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The induced saturation number of P, denoted by sat∗(n,P), is the size of the smallest P-saturated family with ground set [n]. In this paper we prove that the saturation number for any given poset grows at worst polynomially. More precisely, we show that sat∗(n,P)=O(nc), where c≤|P|2/4+1 is a constant depending on P only. We obtain this result by bounding the VC-dimension of our family.
UR - http://www.scopus.com/inward/record.url?scp=85192795740&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2024.103970
DO - 10.1016/j.ejc.2024.103970
M3 - Article
AN - SCOPUS:85192795740
SN - 0195-6698
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103970
ER -