REVIEW 3 major objections 2 minor 6 references
A grid generalisation of the Kruskal-Katona theorem
T0 review · 3 major / 2 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A grid analogue of the Kruskal-Katona theorem: an explicit order's initial segments have the smallest d-shadow.
desk verdict A real generalization of Kruskal-Katona, probably correct; the printed proof has a fixable error in Theorem 2 and an unproved compression lemma, but the stress-test counterexample is wrong. 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 order $\le$ is the central object: it sorts points first by number of zero coordinates, with more zeros earlier, and then, when the zero count is equal, compares the largest value $i$ for which the position sets $R_i(x)=\{j:x_j=i\}$ differ using the binary order $\max(X\triangle Y)\in Y$. The proof machinery is a family of coordinate-wise compression operators $C_s$ that replace each slice of $A$ by an initial segment and never increase the shadow size; repeated compression reduces the problem to compressed sets. Structural lemmas show that compressed sets and their $d$-shadows are down-sets and that every compressed set sits between two layers $B_{\ge r+1}$ and $B_{\ge r}$, reducing the comparison to a single layer. The remaining analysis splits into the case $s=1$, which is exactly the Kruskal-Katona theorem, and $s\ge 2$, where the largest component class $C_T$ carries the argument.
What would settle it
Enumerate all initial segments of the $\le$-order on a small grid such as $[3]^3$ and check whether each one's $d$-shadow is again an initial segment; finding one that is not would invalidate equation (6) and collapse the proof of Claim 1. Independently, a brute-force search over all subsets of $[k]^n_r$ of a fixed size would settle the theorem itself if any subset has a strictly smaller $d$-shadow than the initial segment of the same size.
Extended reading notes
Core claim
The central claim is Theorem 2: if $A$ is a finite subset of $\mathbb{N}^n_r$ and $C$ is the initial segment of the $\le$-order on $\mathbb{N}^n_r$ with $|C|=|A|$, then $|d(A)|\ge |d(C)|$. Theorem 1 establishes the analogous statement for all subsets of $[k]^n$ without a rank restriction. Consequently the initial segments of $\le$ are exactly the $d$-shadow minimizers in every layer, the sets $[t]^n_r$ (points with coordinates in $\{0,\dots,t-1\}$ and exactly $r$ nonzero coordinates) are extremal for every $t$, and in the unrestricted problem the sets of points with at least $r$ zeroes are extremal for every $r$.
Load-bearing premise
The proof assumes, without demonstration, that the $d$-shadow of an initial segment of the $\le$-order is again an initial segment; if this ever failed, the compression argument that reduces every set to a compressed set would no longer yield the needed shadow-size inequality.
Editorial extensions
If this is right
- For every $n,r,k$ and every size $m$, the initial segment of $\le$ in $[k]^n_r$ has the smallest possible $d$-shadow among all subsets of $[k]^n_r$ of size $m$.
- In each layer the sets $[t]^n_r$ are extremal for every $t$, and the initial segments give the full tradeoff between size and shadow as $t$ grows.
- In the unrestricted grid $[k]^n$, the set of points with at least $r$ zeroes is extremal for every $r$.
- Taking $k=2$ recovers the Kruskal-Katona theorem, so the theorem is a genuine generalisation rather than a parallel result.
- The order on $[k]^n_r$ is consistent as $k$ grows, so the same initial segments minimise the $d$-shadow among all finite subsets of $\mathbb{N}^n_r$.
Reading between the lines
- One testable extension: for the dual operator $d^+$ that changes a zero to a nonzero value, the same compression strategy may or may not pick the same order; the paper notes that no simple duality exists for $k\ge 3$, so a brute-force comparison on small grids would tell whether the two minimisation problems are truly separate.
- The theorem implies a limit-shape statement: as $k$ grows, the extremal set of any size in $\mathbb{N}^n_r$ is exactly a finite initial segment, so all extremal data are encoded in the counting sequence of the order; comparing that sequence with random sampling in moderate dimensions would test the effect numerically.
- Because the proof's compression step rests on an unproved initial-segment property of $d$-shadows, checking that property directly for small grids would be a cheap way to stress-test the method; if it holds, the same proof strategy might adapt to shadow operators that decrease a coordinate by 1 rather than flip it to 0.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines a d-shadow operator on the grid [k]^n that flips one nonzero coordinate to zero, and proposes an order ≤ on [k]^n whose initial segments are claimed to minimize the d-shadow among sets of a given size (Theorem 1). It then restricts the order to fixed-rank layers [k]^n_r and claims that initial segments minimize the d-shadow in that setting as well (Theorem 2). The proof of Theorem 1 is an induction on n, with the main weight carried by codimension-1 compression operators: Claim 1 asserts that compressions do not increase the d-shadow, Claim 2 reduces to compressed sets, and a long structural analysis (Claims 3–14) is then used to handle compressed sets. Theorem 2 is deduced from Theorem 1 by embedding a finite set A⊆N^n_r into [nk]^n_r and comparing shadows after adding the lower layers [nk]^n_{≤r-1}.
Significance. If the theorems were correct, they would give a natural and attractive grid generalization of the Kruskal-Katona theorem, with explicit extremal sets: the boxes [t]^n_r in the fixed-rank case and the sets of points with at least r zeroes in the unrestricted case. The proposed order is well motivated, and the structural decomposition in Sections 2.3–2.4 is elaborate and partly instructive. However, the central proof is not valid as written: the main compression lemma rests on a false assertion, and the deduction of Theorem 2 contains independent size-identity errors. The paper therefore does not currently establish its advertised results; the interesting extremal statements remain plausible but unproved.
major comments (3)
- [2.1, Claim 1, Eq. (6)] The proof of Claim 1 relies on the assertion that 'the d-shadow of an initial segment is also an initial segment, and initial segments are nested.' This assertion is false in general. In [4]^2 with the ≤-order, the initial segment C of size 11 is C={00,10,01,20,02,30,03,11,12,21,13}; its d-shadow is d(C)={00,10,01,20,02,03}. Since 30<03 in the ≤-order but 30∉d(C), the set d(C) is not an initial segment. The smaller example C_7⊂[3]^2 that is sometimes quoted for this failure is not actually a counterexample, because d(C_7)={00,10,01,02} is the initial segment of size 4; the [4]^2 example shows the phenomenon at larger parameters. Consequently Eq. (6) does not follow, and with it Eq. (8) and the inequality |d(A)|≥|d(C_s(A))| in Eq. (9) are unsupported. Since Claim 2 reduces Theorem 1 to compressed sets precisely through Claim 1, the proof of Theorem 1 collapses at this point.
- [3, proof of Theorem 2] The proof of Theorem 2 contains false size decompositions. For B=[nk]^n_{≤r-1}∪A, one has d([nk]^n_{≤r-1})=[nk]^n_{≤r-2}, not [nk]^n_{≤r-1}, and d(A) is contained in the single layer [nk]^n_{r-1}, which is itself a subset of [nk]^n_{≤r-1}. Thus d(A) is not disjoint from [nk]^n_{≤r-1}, and the displayed equalities |d(B)|=|[nk]^n_{≤r-1}|+|d(A)| and |d(X)|=|[nk]^n_{≤r-1}|+|d(C)| are false. The correct additive decompositions would use |[nk]^n_{≤r-2}| and the disjointness of d(A) from that lower union. This is a load-bearing error in the deduction of Theorem 2 from Theorem 1.
- [3, proof of Theorem 2 (reduction to [nk]^n_r)] The reduction 'by reordering coordinates if necessary we may assume that A⊆[nk]^n_r' is not justified. The parameter k is set to |A|, but the coordinate values appearing in A need not be bounded by |A|; for example, with n=r=1 the single point (M) has |A|=1 and yet does not lie in [1]^1 for M≥1. Reordering coordinates changes the positions of the entries but does not cap their values, and an arbitrary relabelling of the alphabet would not preserve the ≤-order, since the order distinguishes numeric values. A separate argument is needed for this reduction.
minor comments (2)
- [1, d+-shadow definition] In the paragraph defining the d+-shadow, the displayed union is written as d(A)=⋃_{x∈A} d({x}), but it should be d+(A)=⋃_{x∈A} d+({x}).
- [3, Theorem 2] The notation 'Nn r' in the statement of Theorem 2 should be 'N^n_r' for consistency with the rest of the paper.
Circularity Check
No significant circularity: Theorem 2 is derived from Theorem 1 by a direct padding argument, and the only external theorem used is the classical Kruskal-Katona theorem in a genuine boundary subcase.
full rationale
The paper's central claims are proved by induction with compression operators. Theorem 2 is obtained from Theorem 1 by an explicit construction: B = [nk]^n_{≤r-1} ∪ A and X = [nk]^n_{≤r-1} ∪ C, with the observation that the d-shadows split as [nk]^n_{≤r-1} ∪ d(A) and [nk]^n_{≤r-1} ∪ d(C). This is a direct reduction, not a renaming or a restatement of the input. The only external theorem invoked is the classical Kruskal-Katona theorem, used in Case 1.1 for sets contained in {0,1}^n; this is a legitimate boundary case, not an assumption of the target result. No parameter is fitted to data, no self-citation is load-bearing, and no uniqueness theorem from the author's own prior work is used. The unproved assertion in Claim 1 that the d-shadow of an initial segment is an initial segment is a potential correctness gap, but it is not circular: it does not assume the theorem being proved. Therefore no circularity is present.
Assumptions & free parameters
assumptions (4)
- standard math Kruskal-Katona theorem for the binary case k=2.
- standard math Induction hypothesis that Theorem 1 holds for [k]^{n-1}.
- ad hoc to paper The d-shadow of an initial segment under the ≤-order is itself an initial segment, and initial segments are nested.
- domain assumption The ≤-order is a total order and its components C_x are consecutive blocks.
Cite this review
Pith. "Pith review of A grid generalisation of the Kruskal-Katona theorem." pith.science (2026). https://pith.science/paper/PWZAMCCJ
@misc{pith2026190802253,
author = {Pith},
title = {Pith review of: A grid generalisation of the Kruskal-Katona theorem},
year = {2026},
howpublished = {\url{https://pith.science/paper/PWZAMCCJ}},
note = {Machine review of arXiv:1908.02253}
}
abstract
For a set $A\subseteq\left[k\right]^{n}=\left\{ 0,\dots,k-1\right\} ^{n}$, we define the $d$-shadow of $A$ to be the set of points obtained by flipping to zero one of the non-zero coordinates of some point in $A$. Let $\left[k\right]_{r}^{n}$ be the set of those points in $\left[k\right]^{n}$ with exactly $r$ non-zero coordinates. Given the size of $A$, how should we choose $A\subseteq\left[k\right]_{r}^{n}$ so as to minimise the $d$-shadow? Note that the case $k=2$ is answered by the Kruskal-Katona theorem. Our aim in this paper is to give an exact answer to this question. In particular, we show that the sets $\left[t\right]_{r}^{n}$ are extremal for every $t$. We also give an exact answer to the 'unrestricted' question when we just have $A\subseteq\left[k\right]^{n}$, showing for example that the set of points with at least $r$ zeroes is extremal for every $r$.
Reference graph
Works this paper leans on
-
[3]
G. F. Clements, B. Lindstr¨ om, A generalization of a combinatorial theorem of Macaulay, Journal of Combinatorial Theory 7 (1969), 230-238
work page 1969
-
[4]
Katona, A theorem of finite sets, Theory of Graphs , Akademiai Kiado (1968), 187-207
G. Katona, A theorem of finite sets, Theory of Graphs , Akademiai Kiado (1968), 187-207
work page 1968
-
[1]
B. Bollob´ as, I. Leader, Exact Face-isoperimetric inequalities,European Journal of Combinatorics 11 (1990), 335-340
work page 1990
-
[2]
G. F. Clements, Another Generalization of the Kruskal-Katona T heorem, Journal of Combina- torial Theory, Series A 68 (1994), 239-245
work page 1994
-
[5]
Kleitman, Extremal hypergraph problems
D. Kleitman, Extremal hypergraph problems. In Surveys in Comb inatorics, B. Bollobas (Ed.), Cambridge University Press, Cambridge, 1979, 44-65
work page 1979
-
[6]
J. B. Kruskal, The number of simplices in a complex, Mathematical Optimization Techniques , University of Californa Press (1963), 251-278 23
work page 1963
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.