A polynomial upper bound for poset saturation

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 ( n c ) , 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.