Repository logo
 

A polynomial upper bound for poset saturation

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Bastide, Paul 
Groenland, Carla 
Ivan, Maria-Romina 
Johnston, Tom 

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.

Description

Keywords

4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

European Journal of Combinatorics

Conference Name

Journal ISSN

0195-6698

Volume Title

Publisher

Elsevier BV