Linear Saturation for \(\mathcal{N}\) via Butterflies

Read full text
Authors: Maria‐Romina Ivan, Nandi Wang
Cited by: 0

Abstract

Abstract. Given a finite poset [Formula: see text], how small can a family [Formula: see text] of subsets of [Formula: see text] be such that [Formula: see text] does not contain an induced copy of [Formula: see text], but [Formula: see text] contains such a copy for all [Formula: see text]? This is known as the induced saturation number of [Formula: see text], denoted by [Formula: see text]. The main conjecture in this area is that the induced saturation number for any poset is either bounded or linear. In this paper we establish linearity for the induced saturation number of the 4-point poset [Formula: see text]. Previously, it was known that [Formula: see text]. We show that [Formula: see text]. A crucial role in the proof is played by a structural feature of [Formula: see text]-saturated families, namely that if the family contains two antichains, one completely above the other, then it must also contain a “middle” point that is greater than one antichain and less than the other.

Fields of Study & Subjects

Limits and Structures in Graph Theory Advanced Topology and Set Theory Mathematical Dynamics and Fractals

Publication details

Journal / source
SIAM Journal on Discrete Mathematics
Volume
40
Issue
3
Pages
1553–1571
Publication date
17 September 2026
Language
EN