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.
| Original language | English |
|---|---|
| Article number | 103970 |
| Number of pages | 6 |
| Journal | European Journal of Combinatorics |
| Early online date | 14 May 2024 |
| DOIs | |
| Publication status | E-pub ahead of print - 14 May 2024 |
Bibliographical note
Publisher Copyright:© 2024
Fingerprint
Dive into the research topics of 'A polynomial upper bound for poset saturation'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver