A polynomial upper bound for poset saturation
P.P. Bastide (Labri)
C.E. Groenland (TU Delft - Discrete Mathematics and Optimization)
Maria Romina Ivan (Centre for Mathematical Sciences, Magdalene College)
Tom Johnston (University of Bristol)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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.