Induced poset saturation in the hypergrid
Pith reviewed 2026-05-10 15:03 UTC · model grok-4.3
The pith
For every poset P the induced saturation number sat*([t]^n, P) is either eventually constant or grows as Omega(sqrt(n)).
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that for all t greater than or equal to 2 and every poset P that embeds as an induced subposet of [t]^n, the induced poset saturation function sat*([t]^n, P) satisfies a dichotomy: either there exists a constant C_P such that sat*([t]^n, P) equals C_P for all sufficiently large n, or sat*([t]^n, P) equals Omega of the square root of n. Chains belong to the constant class; posets with the unique twin cover property belong to the Omega(sqrt(n)) class.
What carries the argument
The induced saturation function sat*([t]^n, P), the smallest cardinality of a subset of the hypergrid [t]^n that contains no induced copy of P and is saturated (every omitted element can be inserted to create at least one induced copy of P).
If this is right
- The saturation number of any chain stabilizes to a constant depending only on the chain length and t.
- Any poset with the unique twin cover property forces every induced-P-free saturated family to have size at least c sqrt(n) for some positive c depending on the poset.
- The same two-regime classification that holds for the hypercube extends to all hypergrids with fixed t at least 2.
- No poset produces saturation numbers that grow slower than sqrt(n) yet unbounded, or faster than linear in n but sublinear in other ways, under the stated dichotomy.
Where Pith is reading between the lines
- The unique twin cover property appears to be the structural feature that forces the sqrt(n) lower bound.
- For any fixed P the exact constant C_P may be determined by computing minimal saturated families in low dimensions and checking that they remain minimal when n increases.
- The dichotomy suggests that intermediate growth rates such as log n or n to a fractional power other than 1/2 are impossible for induced poset saturation in hypergrids.
- Similar constant-versus-sqrt(n) behavior may hold for saturation problems in other graded posets or in product orders with different component sizes.
Load-bearing premise
The technical obstacles created by richer embeddings and relations when t exceeds 2 can be overcome without producing saturation numbers that grow at rates other than constant or sqrt(n).
What would settle it
An explicit poset P together with families in [t]^n of size tending to infinity but o(sqrt(n)) that are both induced-P-free and induced-P-saturated for infinitely many n.
read the original abstract
Set $[n]=\{1, 2, \ldots , n\}$. The hypergrid $[t]^n$ is the collection of functions $f: \ [n]\rightarrow [t]$. We equip it with the natural partial order by letting $f\leq g$ whenever $f(x)\leq g(x)$ holds for all $x\in [n]$. Given a poset $P$ which can be embedded as an induced subposet of $[t]^n$, the induced poset saturation function $\mathrm{sat}^{\star}([t]^n, P)$ denotes the minimum size of a subset of $[t]^n$ that is both induced $P$-free and induced $P$-saturated. We show that for all $t\geq 2$, $\mathrm{sat}^{\star}([t]^n, P)$ satisfies a dichotomy: for every poset $P$, either there exists a constant $C_P$ such that $\mathrm{sat}^{\star}([t]^n, P)=C_P$ for all $n$ sufficiently large, or $\mathrm{sat}^{\star}([t]^n, P)=\Omega(\sqrt{n})$. We also show chains fall in the former part of the dichotomy, while posets with the unique twin cover property fall in the latter part. These contributions generalize a number of results obtained by various authors in the hypercube ($t=2$) setting; the transition to the hypergrid setting provides novel challenges, however, and requires some new ideas.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that the induced saturation function sat^*([t]^n, P) on the hypergrid poset [t]^n (t ≥ 2) obeys a dichotomy: for any poset P embeddable as an induced subposet, either sat^*([t]^n, P) equals some constant C_P for all sufficiently large n, or sat^*([t]^n, P) = Ω(√n). Chains are placed in the constant class and posets possessing the unique twin cover property are placed in the Ω(√n) class. The result extends known t=2 hypercube dichotomies by introducing new technical ideas to handle the richer embeddings and relations present when t > 2.
Significance. If the proofs are correct, the work supplies a clean structural dichotomy in a strictly more general setting than the hypercube, together with explicit, verifiable placements of two natural families of posets on each side of the dichotomy. The explicit handling of the transition from t=2 to arbitrary t, including the novel challenges of product-order embeddings, constitutes a genuine advance in extremal poset theory and induced saturation.
minor comments (2)
- The definition of the unique twin cover property is used centrally in the classification but is only referenced rather than restated; a brief self-contained definition in §1 or §2 would improve readability for readers unfamiliar with the t=2 literature.
- The statement of the main dichotomy theorem (presumably Theorem 1.1 or 1.2) would benefit from an explicit sentence clarifying that the Ω(√n) lower bound is witnessed by an explicit construction rather than an existence argument.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript, including the recognition that the work supplies a clean structural dichotomy in a more general setting than the hypercube together with explicit placements of natural families of posets. We are pleased that the novel technical ideas required for the transition from t=2 to arbitrary t are viewed as a genuine advance.
Circularity Check
No significant circularity detected in the claimed dichotomy
full rationale
The paper establishes a dichotomy theorem for sat*([t]^n, P) via direct combinatorial arguments that generalize prior hypercube results (cited to various external authors) while introducing new technical ideas to address t>2 embeddings. No equations or definitions reduce the constant-vs-Omega(sqrt(n)) classification to a fitted parameter, a self-referential quantity, or a load-bearing self-citation chain. Chains are shown to yield bounded saturation size and unique-twin-cover posets to yield Omega(sqrt(n)) growth through explicit constructions and forbidden-subposet arguments that remain independent of the target statement. The derivation is self-contained against external benchmarks in extremal poset theory.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math The componentwise partial order on [t]^n is a poset, and induced subposets are defined by preserving both the order relations and the non-relations among the selected elements.
Reference graph
Works this paper leans on
-
[1]
On primitive sequences.Journal of the London Mathematical Society, 1(1):137– 148, 1967
Ian Anderson. On primitive sequences.Journal of the London Mathematical Society, 1(1):137– 148, 1967
work page 1967
-
[2]
Saturationforsmallantichains.The Electronic Journal of Combinatorics, 30, 01 2023
IrinaÐankovićandMaria-RominaIvan. Saturationforsmallantichains.The Electronic Journal of Combinatorics, 30, 01 2023
work page 2023
-
[3]
A polynomial upper bound for poset saturation.European Journal of Combinatorics, 129:103970, 2025
Paul Bastide, Carla Groenland, Maria-Romina Ivan, and Tom Johnston. A polynomial upper bound for poset saturation.European Journal of Combinatorics, 129:103970, 2025
work page 2025
-
[4]
Paul Bastide, Carla Groenland, Hugo Jacob, and Tom Johnston. Exact antichain saturation numbers via a generalisation of a result of lehman-ron.Preprint, arXiv ref:2207.07391, 2023
- [5]
-
[6]
Counting antichains and linear extensions in generalizations of the boolean lattice.Preprint, 2009
Teena Carroll, Joshua Cooper, and Prasad Tetali. Counting antichains and linear extensions in generalizations of the boolean lattice.Preprint, 2009
work page 2009
-
[7]
Dedekind’s problem in the hypergrid
Victor Falgas-Ravry, Eero Räty, and István Tomon. Dedekind’s problem in the hypergrid. Advances in Mathematics, 488:110796, 2026
work page 2026
-
[8]
Martin, Benjamin Reiniger, Heather C
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 Mathematics, 340(10):2479–2487, 2017. 14
work page 2017
-
[9]
Optimal embeddings of posets in hypercubes
Tomáš Flídr, Maria-Romina Ivan, and Sean Jaffe. Optimal embeddings of posets in hypercubes. Preprint, arXiv ref:2509.26630, 2025
-
[10]
The induced satu- ration problem for posets.Combinatorial Theory, 3(3), December 2023
Andrea Freschi, Simón Piga, Maryam Sharifzadeh, and Andrew Treglown. The induced satu- ration problem for posets.Combinatorial Theory, 3(3), December 2023
work page 2023
-
[11]
Saturating Sperner families.Graphs and Combinatorics, 29(5):1355–1364, 2013
DánielGerbner, BalázsKeszegh, NathanLemons, CoryPalmer, DömötörPálvölgyi, and Balázs Patkós. Saturating Sperner families.Graphs and Combinatorics, 29(5):1355–1364, 2013
work page 2013
-
[12]
Forbidden subposet problems in the grid.Discrete Mathematics, 345(3):112720, 2022
Dániel Gerbner, Dániel T Nagy, Balázs Patkós, and Máté Vizer. Forbidden subposet problems in the grid.Discrete Mathematics, 345(3):112720, 2022
work page 2022
-
[13]
A generalization of Sauer’s lemma.Journal of Combina- torial Theory, Series A, 71(2):219–240, 1995
David Haussler and Philip M Long. A generalization of Sauer’s lemma.Journal of Combina- torial Theory, Series A, 71(2):219–240, 1995
work page 1995
-
[14]
Saturation for the butterfly posets.Mathematika, 66(3):806–817, 2020
Maria-Romina Ivan. Saturation for the butterfly posets.Mathematika, 66(3):806–817, 2020
work page 2020
-
[15]
Minimal diamond-saturated families.Contemporary Mathematics, page 81–88, Mar 2022
Maria-Romina Ivan. Minimal diamond-saturated families.Contemporary Mathematics, page 81–88, Mar 2022
work page 2022
-
[16]
Gluing posets and the dichotomy of poset saturation numbers.Preprint, arXiv ref:2503.12223., 2025
Maria-Romina Ivan and Sean Jaffe. Gluing posets and the dichotomy of poset saturation numbers.Preprint, arXiv ref:2503.12223., 2025
work page internal anchor Pith review arXiv 2025
-
[17]
Saturation for sums of posets and antichains.Preprint, arXiv ref:2509.10294, 2025
Maria-Romina Ivan and Sean Jaffe. Saturation for sums of posets and antichains.Preprint, arXiv ref:2509.10294, 2025
-
[18]
The Exact Saturation Number for the Diamond
Maria-Romina Ivan and Sean Jaffe. The exact saturation number for the diamond.Preprint, arXiv ref:2604.06521, 2026
work page internal anchor Pith review Pith/arXiv arXiv 2026
-
[19]
Maria-Romina Ivan and Sean Jaffe. The saturation number for the diamond is linear.Bulletin of the London Mathematical Society, 58(3):e70305, 2026
work page 2026
-
[20]
Linear Saturation for $\mathcal N$ via Butterflies
Maria-Romina Ivan and Nandi Wang. Linear saturation forNvia butterflies.Preprint, arXiv ref:2511.08965, 2025
work page internal anchor Pith review Pith/arXiv arXiv 2025
-
[21]
Poset saturation of unions of chains.Preprint, arXiv ref:2505.23128, 2025
Shengjin Ji, Balázs Patkós, and Erfei Yue. Poset saturation of unions of chains.Preprint, arXiv ref:2505.23128, 2025
-
[22]
Martin, Dömötör Pálvölgyi, and Balázs Patkós
Balázs Keszegh, Nathan Lemons, Ryan R. Martin, Dömötör Pálvölgyi, and Balázs Patkós. Induced and non-induced poset saturation problems.Journal of Combinatorial Theory, Series A, 184:105497, 2021
work page 2021
-
[23]
On disjoint chains of subsets.Journal of Combinatorial Theory, Series A, 94(2):399–404, 2001
Eric Lehman and Dana Ron. On disjoint chains of subsets.Journal of Combinatorial Theory, Series A, 94(2):399–404, 2001
work page 2001
-
[24]
Induced saturation for complete bipartite posets.Discrete Mathematics, 348(7):114462, 2025
Dingyuan Liu. Induced saturation for complete bipartite posets.Discrete Mathematics, 348(7):114462, 2025
work page 2025
-
[25]
American Mathe- matical Society, 2001
Percy A MacMahon.Combinatory analysis, volumes I and II, volume 137. American Mathe- matical Society, 2001
work page 2001
-
[26]
Ryan R. Martin, Heather C. Smith, and Shanise Walker. Improved bounds for induced poset saturation.The Electronic Journal of Combinatorics, 27(2), May 2020
work page 2020
-
[27]
Lutz Mattner and Bero Roos. Maximal probabilities of convolution powers of discrete uniform distributions.Statistics & probability letters, 78(17):2992–2996, 2008
work page 2008
-
[28]
Guy Moshkovitz and Asaf Shapira. Ramsey theory, integer partitions and a new proof of the Erdős–Szekeres theorem.Advances in Mathematics, 262:1107–1129, 2014
work page 2014
-
[29]
On learning sets and functions.Machine Learning, 4(1):67–97, 1989
Balas Kausik Natarajan. On learning sets and functions.Machine Learning, 4(1):67–97, 1989
work page 1989
-
[30]
Jinyoung Park, Michail Sarantis, and Prasad Tetali. Note on the number of antichains in generalizations of the Boolean lattice.Combinatorial Theory, 5(1), 2025
work page 2025
-
[31]
Cosmin Pohoata and Dmitrii Zakharov. On the number of high-dimensional partitions.Pro- ceedings of the London Mathematical Society, 128(2):e12586, 2024. 15
work page 2024
-
[32]
István Tomon. The number of symmetric chain decompositions.Proceedings of the American Mathematical Society, 153(04):1511–1518, 2025
work page 2025
-
[33]
A simple upper bound on the number of antichains in[t]n.Order, 36(3):507–510, 2019
Shen-Fu Tsai. A simple upper bound on the number of antichains in[t]n.Order, 36(3):507–510, 2019. 16
work page 2019
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.