REVIEW 2 major objections 3 minor 10 references
Improved bounds for induced poset saturation
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper proves that induced-saturated families in the Boolean lattice must be large: at least $\lceil\sqrt{n}\rceil$ for the diamond poset and, for large $k$, about $k n/\log_2 k$ for a $(k+1)$-element antichain.
desk verdict Solid diamond lower bound, but the antichain proof has a real, load-bearing gap in the wide-gap elimination argument that the paper does not address. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The main objects are the Boolean lattice $\mathcal{B}_n=(2^{[n]},\subseteq)$, the diamond $\mathcal{D}_2$ (the four-element poset with two incomparable middle elements), and the antichain $\mathcal{A}_{k+1}$. The diamond proof is carried by a directed cover graph on the family, with an arc $A\to B$ when $B=A\cup\{i\}$; the key lemma forces every coordinate $i$ to appear in at least one arc, so the graph has at least $n$ arcs although it has at most $|\mathcal{F}|(|\mathcal{F}|-1)$ arcs. The antichain proof is carried by a chain decomposition of the family, by the open intervals, called gaps, between consecutive elements of a chain, and by a greedy coloring that assigns each element to one of $k$ color classes; the size of any gap in color class $j$ is bounded by the largest $d$ with $\binom{d}{\lfloor d/2\rfloor}\leq j-1$, and this bound is what converts chain lengths into the linear lower bound.
What would settle it
A single induced-$\mathcal{D}_2$-saturated family $\mathcal{F}\subseteq 2^{[n]}$ with $|\mathcal{F}|<\lceil\sqrt{n}\rceil$ for some $n$ would refute the diamond theorem; a single induced-$\mathcal{A}_{k+1}$-saturated family with fewer than $(1-1/\log_2 k)\, k n/\log_2 k$ members, for $k\geq 3$ and $n\geq (\log_2 k)^3$, would refute the antichain theorem. Inspecting the greedy coloring of such a family would also directly test the claimed invariant that uncolored elements cannot appear in a gap of a later color class.
Extended reading notes
Core claim
The paper's central results are Theorem 6 and Theorem 7. Theorem 6 states that every induced-$\mathcal{D}_2$-saturated family in $\mathcal{B}_n$ has size at least $\lceil\sqrt{n}\rceil$; the proof builds a directed graph on the family whose arcs record pairs differing in exactly one coordinate, shows via a coordinate-by-coordinate lemma that each of the $n$ coordinates forces a distinct arc, and counts $|\mathcal{F}|(|\mathcal{F}|-1)\geq n$. Theorem 7 states that for $k\geq 3$ and $n$ sufficiently large, every induced-$\mathcal{A}_{k+1}$-saturated family has size at least $(1 - 1/\log_2 k)\, k n/\log_2 k$; the proof partitions the family into $k$ chains, uses the classical bound on antichains inside a Boolean lattice to control the length of gaps between consecutive chain elements, and sums the resulting lower bounds on chain lengths.
Load-bearing premise
The antichain proof assumes that after the greedy coloring, every subset lying strictly between two consecutive members of color class $j$ has already received one of the earlier colors; this invariant is stated as a consequence of the coloring's structure without a full derivation.
Editorial extensions
If this is right
- Every induced-$\mathcal{D}_2$-saturated family in $\mathcal{B}_n$ has at least $\lceil\sqrt{n}\rceil$ members, so no family of size $o(\sqrt{n})$ can saturate the diamond.
- For fixed $k\geq 3$ and large $n$, $\operatorname{sat}^*(n,\mathcal{A}_{k+1})\geq (1 - 1/\log_2 k)\, k n/\log_2 k$; for $k$ large enough this is stronger than the previous $3n-1$ lower bound.
- The antichain argument forces both $\emptyset$ and $[n]$ to belong to any induced-$\mathcal{A}_{k+1}$-saturated family, and every gap in a chain containing no chain elements must itself be entirely filled with family members.
- The two parts of the antichain theorem are complementary: for fixed $k\leq 243$ the gap-sum bound is stronger, while for $k\geq 264$ the wide-gap bound wins, so the proof covers two different regimes.
Reading between the lines
- Nothing in the diamond proof uses the full force of saturation beyond the coordinate lemma; the same arc-counting idea may apply to other small posets, such as the butterfly, and would yield polynomial lower bounds if every coordinate can again be assigned a distinct cover pair.
- If the unproved greedy-coloring invariant for the antichain can be established, the same template likely extends to induced saturation in products of chains, where the relevant antichain bound is known but takes a different form.
- The paper itself closes by conjecturing the true values are $n+1$ for the diamond and $kn-o(k)$ for the antichain; if that is right, both lower bounds here are still far from optimal, and stronger arguments must exploit structure beyond single-coordinate counting and gap sizes.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the minimum size sat*(n,P) of an induced-P-saturated family in the n-dimensional Boolean lattice. Theorem 6 establishes sat*(n,D2) ≥ ceil(sqrt n), improving the logarithmic lower bound of Ferrara et al.; the proof uses Lemma 9 to force, for each member F* and each coordinate i, a distinct arc in a digraph on the family, giving n arcs and hence |F| ≥ sqrt n. Theorem 7 establishes sat*(n,A_{k+1}) ≥ (1 − 1/log_2 k) k n/log_2 k for k ≥ 3 and n sufficiently large, via a Dilworth chain decomposition and two counting arguments: Theorem 11(1) repeatedly moves an element from a 'wide' gap between chains and then counts gap elements, while Theorem 11(2) builds greedy color classes and applies Sperner's theorem to gaps in each color class. The diamond proof is clean and self-contained; the antichain proof, however, has two steps that are not justified as written.
Significance. If the antichain proofs can be completed, the paper gives a substantial advance in induced poset saturation. The sqrt(n) lower bound for the diamond is the first polynomial lower bound for that poset and follows from a short, elegant arc-counting argument. The antichain lower bound is asymptotically k n/log_2 k, far above the previous 3n−1 bound and within a logarithmic factor of the known upper bound. The paper is written in an elementary style and makes explicit use only of classical results such as Dilworth's theorem and Sperner's theorem. The main weakness is not novelty but proof completeness in Section 3.
major comments (2)
- [Section 3, Part (1), the wide-gap reassignment argument] The argument that moving T from C_j to C_i does not increase the maximum size among wide gaps is incomplete: it analyzes only gaps in C_i and C_j, and only gaps that contain X, T, and Y. A gap (A,B) in a third chain C_l can contain X and T but not Y. For example, with A ⊂ W ⊂ X ⊂ T ⊂ B ⊂ Y, where W,X ∈ C_i and S,T ∈ C_j with U not in (A,B), the gap (A,B) has two elements from C_i and two from C_j before the move, hence is not wide; after T moves to C_i, it has three elements from C_i and becomes wide, and its size |B−A| can exceed |Y−X|. The sentence 'any gap in some C_i′ containing X,T,Y must also contain S,T,U' does not cover such a gap. Since the termination of the reassignment process depends on the maximum wide-gap size not increasing, Theorem 11(1) and consequently Theorem 7 are not fully proved as written.
- [Section 3, Part (2), the greedy color-class invariant] The assertion that for a gap (X,Y) in the chain forming color class j, every element of the open interval (X,Y) has already received one of the colors 1,...,j−1 is not justified. Item (ii) applies to gaps in the chains of a k-chain partition of F, but the greedy color class j is not shown to be a chain in such a partition; maximality of the greedy construction only excludes uncolored members of F from the gap, not elements of B_n outside F. The later Sperner bound, (d choose floor(d/2)) ≤ j−1, requires every element of the interval to be colored, so the proof of Theorem 11(2) is missing a step. This does not affect Theorem 7 if Part (1) is repaired, but it is a genuine gap in a stated result.
minor comments (3)
- [Section 2, proof of Theorem 6] The definition says an arc (A,B) is included when |B−A|=1, but the proof writes arcs (F_i,G_i) where F_i−G_i={i}; the ordered-pair convention should be clarified, for instance by writing arcs from the smaller set to the larger set consistently.
- [Section 3, final paragraph] The phrase 'n ≥ log_2^3 k' should be typeset as n ≥ (log_2 k)^3 to avoid ambiguity.
- [Section 2, Lemma 9] In Lemma 9, the proof of part (2) is dismissed with 'the proof for (2) follows similarly'; since the dual argument is not literally identical, a few sentences of detail would improve readability.
Circularity Check
New bounds are derived from saturation, Dilworth, and Sperner; self-citations are contextual, not load-bearing.
full rationale
The derivation chain for both main theorems is self-contained and does not reduce to its inputs. Theorem 6 is proved by counting arcs of an auxiliary digraph on F: Lemma 9 supplies n distinct arcs (one per coordinate i, either inside or outside a fixed F*), and the trivial upper bound |F|(|F|-1) on arcs yields |F| >= sqrt(n). The lemma is proved directly from the definition of induced-D2-saturation, not from the claimed bound. Theorem 7 is proved from Dilworth's chain decomposition of F - {empty, [n]} into k chains, the saturation-forced fact that every Boolean element in a chain gap lies in F (item (ii)), and Sperner's theorem applied to gap intervals; the bound d <= d*(j) and the summation are arithmetic consequences, with no fitted parameter or assumed target value. The citations to Ferrara et al. [4] (which includes two of the authors) and to Walker's thesis [9] supply the definition, baseline bounds, and a comparative table of the two parts of Theorem 11; these are context rather than load-bearing, since the new lower-bound proofs do not invoke the [4] bounds as premises. A possible unproven invariant in the greedy-coloring part ('the structure of our color classes guarantees...') is a proof gap, not a circular reduction: it does not assume the desired bound. Accordingly, the circularity score is 2, reflecting only minor non-load-bearing self-citation.
Assumptions & free parameters
assumptions (3)
- standard math Dilworth's theorem: a finite poset with largest antichain of size k can be partitioned into k chains.
- standard math Sperner's theorem: the largest antichain in the d-dimensional Boolean lattice has size binomial(d, floor(d/2)).
- standard math Any chain in the Boolean lattice between two sets of size difference d has at least ceil(n/d)+1 elements when its maximum gap size is d.
Cite this review
Pith. "Pith review of Improved bounds for induced poset saturation." pith.science (2026). https://pith.science/paper/JFBA6MPO
@misc{pith2026190801108,
author = {Pith},
title = {Pith review of: Improved bounds for induced poset saturation},
year = {2026},
howpublished = {\url{https://pith.science/paper/JFBA6MPO}},
note = {Machine review of arXiv:1908.01108}
}
abstract
Given a finite poset $\mathcal{P}$, a family $\mathcal{F}$ of elements in the Boolean lattice is induced-$\mathcal{P}$-saturated if $\mathcal{F}$ contains no copy of $\mathcal{P}$ as an induced subposet but every proper superset of $\mathcal{F}$ contains a copy of $\mathcal{P}$ as an induced subposet. The minimum size of an induced-$\mathcal{P}$-saturated family in the $n$-dimensional Boolean lattice, denoted $\operatorname{sat}^*(n,\mathcal{P})$, was first studied by Ferrara et al. (2017). Our work focuses on strengthening lower bounds. For the 4-point poset known as the diamond, we prove $\operatorname{sat}^*(n,\mathcal{D}_2)\geq\sqrt{n}$, improving upon a logarithmic lower bound. For the antichain with $k+1$ elements, we prove $\operatorname{sat}^*(n,\mathcal{A}_{k+1})\geq (1-o_k(1))\frac{kn}{\log_2 k}$, improving upon a lower bound of $3n-1$ for $k\geq 3$.
Figures
Reference graph
Works this paper leans on
-
[1]
R. P. Dilworth. A decomposition theorem for partially ordered set s. Annals of Mathematics, 51(1): 161–166, 1950
work page 1950
-
[2]
P. Erd¨ os, A. Hajnal, and J. W. Moon. A problem in graph theory. The Amer- ican Mathematical Monthly , 71(10): 1107–1110, 1964
work page 1964
-
[3]
J. R. Faudree, R. J. Faudree, and J. R. Schmitt. A survey of min imum sat- urated graphs. The Electronic Journal of Combinatorics , Dynamic Survey, DS19, accessed 14 March 2019
work page 2019
-
[4]
M. Ferrara, B. Kay, L. Kramer, R. R. Martin, B. Reiniger, H. C. S mith, and E. Sullivan. The saturation number of induced subposets of the Boo lean lattice. Discrete Mathematics, 340(10): 2479–2487, 2017
work page 2017
-
[5]
D. Gerbner, B. Keszegh, N. Lemons, C. Palmer, D. P´ alv¨ olgyi, a nd B. Patk´ os. Saturating Sperner Families. Graphs and Combinatorics , 29(5): 1355–1364, 2013
work page 2013
-
[6]
J. R. Griggs and W.-T. Li. Progress on poset-free families of subs ets. In Recent Trends in Combinatorics , pages 317–338. Springer, 2016
work page 2016
-
[7]
N. Morrison, J. A. Noel, and A. Scott. On saturated k-Sperner systems. The Electronic Journal of Combinatorics , 21(3): P3–22, 2014. 10 RYAN R. MARTIN, HEATHER C. SMITH, AND SHANISE W ALKER
work page 2014
-
[8]
E. Sperner. Ein satz ¨ uber untermengen einer endlichen menge. Mathematische Zeitschrift, 27(1): 544–548, 1928
work page 1928
Show all 10 references
-
[9]
S. Walker. Problems in extremal graphs and poset theory (2018 ). Graduate Theses and Dissertations. 16482
2018
-
[10]
A. A. Zykov. On some properties of linear complexes. Matematicheskii Sbornik, 66(2): 163–188, 1949. (Martin) Department of Mathematics, Iowa State University , Ames, Iowa, 50011 E-mail address : rymartin@iastate.edu (Smith) Department of Mathematics and Computer Science, Da vi...
1949
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.