Linear Saturation for mathcal N via Butterflies
Pith reviewed 2026-05-17 23:05 UTC · model grok-4.3
The pith
The induced saturation number for the poset N is at least linear in n.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We show that sat*(n, N) ≥ (n+6)/4. The argument proceeds by establishing a structural lemma: any N-saturated family that contains two antichains, one completely above the other, must contain a middle point that is greater than one antichain and less than the other.
What carries the argument
The structural lemma on N-saturated families that forces a middle point between any two vertically separated antichains.
If this is right
- The induced saturation number sat*(n, N) is linear in n.
- The general conjecture that every poset has induced saturation number either bounded or linear receives new support from the N case.
- Maximal N-free families cannot stay small; their size must increase steadily with the ground set.
Where Pith is reading between the lines
- Similar structural lemmas about separated antichains might yield linear bounds for other small posets whose saturation numbers are currently only known to be sublinear.
- For small fixed n one could computationally enumerate maximal N-free families and check whether their sizes meet or exceed the (n+6)/4 threshold.
- If the middle-point lemma extends to other posets, it could give a uniform method for proving linearity across a wider class.
Load-bearing premise
The proof depends on the structural lemma that any N-saturated family containing two antichains one completely above the other must contain a middle point greater than one and less than the other.
What would settle it
An explicit construction of an N-saturated family on n elements with fewer than (n+6)/4 sets would falsify the claimed lower bound.
read the original abstract
Given a finite poset $\mathcal P$, how small can a family $\mathcal F$ of subsets of $[n]$ be such that $\mathcal F$ does not contain an induced copy of $\mathcal P$, but $\mathcal F\cup\{X\}$ contains such a copy for all $X\in\mathcal P([n])\setminus\mathcal F$? This is known as the induced saturation number of $\mathcal P$, denoted by $\text{sat}^*(n,\mathcal P)$. The main conjecture in the 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 $\mathcal N$. Previously, it was known that $2\sqrt n\leq\text{sat}^*(n,\mathcal N)\leq 2n$. We show that $\text{sat}^*(n,\mathcal N)\geq\frac{n+6}{4}$. A crucial role in the proof is played by a structural feature of $\mathcal N$-saturated families, namely that if the family contains two antichains, one completely above the other, then it must also contain a `middle' point -- greater than one antichain and less than the other.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that the induced saturation number sat*(n, N) for the 4-element poset N satisfies sat*(n, N) ≥ (n+6)/4. This establishes linearity for this poset, improving the prior lower bound of 2√n while the upper bound remains 2n. The argument relies on a structural lemma asserting that any N-saturated family containing two antichains A and B with every element of A strictly above every element of B must contain a 'middle' set X that is comparable to elements of both antichains in the manner required to force an N-configuration upon addition of any missing set.
Significance. If correct, the result confirms the central conjecture that induced saturation numbers are either bounded or linear for any fixed poset, here for N. The structural lemma on stacked antichains and middle points supplies a combinatorial counting mechanism that yields the explicit 1/4 coefficient and may extend to other small posets. The paper also supplies an explicit construction achieving the bound up to the additive constant.
major comments (1)
- [Structural lemma on stacked antichains] Structural lemma (the 'butterfly' or middle-point claim invoked to derive the linear bound): the case analysis appears to assume that the two antichains are maximal or that all cross-comparabilities are total; it is unclear whether the argument covers non-maximal antichains or configurations in which adding a candidate middle set would create an N but saturation is preserved by some other route. This lemma is load-bearing for the coefficient 1/4 in the main counting argument that produces sat*(n, N) ≥ (n+6)/4.
minor comments (2)
- [Introduction] Notation for the poset N and the induced copy should be fixed consistently in the introduction and in the statement of the main theorem.
- [Construction section] The explicit construction achieving the lower bound is only sketched; a self-contained description of the family realizing (n+6)/4 would strengthen the paper.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for identifying a point of potential ambiguity in the structural lemma. We address the concern directly below and are prepared to add a clarifying remark in the revised manuscript.
read point-by-point responses
-
Referee: Structural lemma (the 'butterfly' or middle-point claim invoked to derive the linear bound): the case analysis appears to assume that the two antichains are maximal or that all cross-comparabilities are total; it is unclear whether the argument covers non-maximal antichains or configurations in which adding a candidate middle set would create an N but saturation is preserved by some other route. This lemma is load-bearing for the coefficient 1/4 in the main counting argument that produces sat*(n, N) ≥ (n+6)/4.
Authors: The structural lemma is stated for arbitrary antichains A and B in the saturated family F with every element of A strictly above every element of B; maximality of A or B is never assumed. The proof examines an arbitrary set X not in F and shows that if X is incomparable to all members of A and B in the manner that would avoid creating an induced N, then there must exist a middle set Y in F that is above at least one element of the lower antichain and below at least one element of the upper antichain. The case analysis is exhaustive over the possible intersection patterns of X with the ground set elements realizing the comparabilities between A and B; it does not rely on total cross-comparability. Regarding alternative saturation-preserving routes: because F is induced-N-saturated, the addition of any missing set (including any candidate middle set) must produce an induced N. Thus, if no middle set exists, every possible X would have to create an N by some other configuration, but the argument demonstrates that the only way to block all such X is to force the existence of the middle point. We will insert a short paragraph after the lemma statement explicitly noting that the antichains are not required to be maximal and briefly summarizing why the induced-saturation hypothesis rules out other blocking configurations. revision: partial
Circularity Check
No circularity; bound derived from independently proven structural lemma
full rationale
The paper proves sat*(n, N) ≥ (n+6)/4 via direct combinatorial analysis: it first establishes a structural lemma that any N-saturated family with two stacked antichains must contain a middle set satisfying the N-relations, then applies this to force sufficient intersection with layers or a counting argument yielding the linear coefficient. This lemma is derived from case analysis on inclusion relations within the family and is not equivalent to the target bound by definition, nor obtained via fitted parameters, self-citation chains, or ansatz smuggling. The derivation chain is self-contained against external benchmarks and does not reduce the claimed result to its own inputs.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard facts about partial orders, antichains, and induced subposets in the Boolean lattice.
Forward citations
Cited by 2 Pith papers
-
Induced poset saturation in the hypergrid
For every poset P, the induced saturation function sat*([t]^n, P) is either eventually constant or Omega(sqrt(n)) as n grows, with chains constant and unique-twin-cover posets growing.
-
The Exact Saturation Number for the Diamond
The saturation number for the diamond poset is exactly n+1.
Reference graph
Works this paper leans on
-
[1]
Paul Bastide, Carla Groenland, Maria-Romina Ivan, and Tom Johnston,A Polynomial Upper Bound for Poset Saturation, European Journal of Combinatorics (2024)
work page 2024
-
[2]
Paul Bastide, Carla Groenland, Hugo Jacob, and Tom Johnston,Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron, Combinatorial Theory4(2024)
work page 2024
-
[3]
Michael Ferrara, Bill Kay, Lucas Kramer, Ryan R Martin, Benjamin Reiniger, Heather C Smith, and Eric Sullivan,The Saturation Number of Induced Subposets of the Boolean lattice, Discrete Mathematics340(2017), no. 10, 2479–2487
work page 2017
-
[4]
AndreaFreschi, SimónPiga, MaryamSharifzadeh, andAndrewTreglown,The induced saturation problem for posets, Combinatorial Theory3(2023), no. 3
work page 2023
-
[5]
Maria-Romina Ivan,Saturation for the Butterfly Poset, Mathematika66(2020), no. 3, 806–817
work page 2020
-
[6]
Maria-Romina Ivan and Sean Jaffe,Gluing Posets and the Dichotomy of Poset Saturation Num- bers, arXiv:2503.12223 (2025)
work page internal anchor Pith review arXiv 2025
- [7]
-
[8]
Balázs Keszegh, Nathan Lemons, Ryan R Martin, Dömötör Pálvölgyi, and Balázs Patkós,In- duced and non-induced poset saturation problems, Journal of Combinatorial Theory, Series A184 (2021), 105497. Maria-Romina Ivan,Department of Pure Mathematics and Mathematical Statistics, Centre for Math- ematical Sciences, Wilberforce Road, Cambridge, CB3 0WB, UK,and D...
work page 2021
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.