REVIEW 4 major objections 4 minor 16 references
Sperner's colorings of hypergraphs arising from edgewise triangulations
T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read For most permutations, a distance-based Sperner coloring beats the greedy coloring on edgewise-triangulation hypergraphs.
desk verdict Actually new and mostly sound: a distance coloring that beats greedy for most permutations, but Section 2's admissibility criterion has a real off-by-one error that needs correcting before the reduction is valid. 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 load-bearing object is the line graph $G^{\pi}_{k,q}$ of the hypergraph, whose vertices are the facets of type $\pi$ (identified with their initial vertex $v$) and whose edges join facets sharing a vertex; its edges decompose into sets $E_{a,b}$ indexed by consecutive entries of $\pi$. The building block is the graph $G_{\pi}$ on $[k]$, where $ij$ is an edge exactly when $\{i,i+1,\ldots,j-1\}$ appears as a contiguous subsequence of $\pi$. Theorem 3.5 characterizes $G_{\pi}$ as a dissection of a regular $k$-gon into cycle or complete regions, and Proposition 3.9 identifies $G_{\pi}$ with $\sigma_{\pi^{-1}}\cap\Delta^{(\le 1)}_{k,m}$. The distance coloring fixes an independent set $C$ in $G_{\pi}$ and colors each vertex of the line graph by the element of $C$ it is closest to, after mapping $W^{\pi}_{k,q}$ through the difference map $D(x)=(x_{a_1}-x_{a_1-1}-\varepsilon_{a_1},\ldots)$; Definition 4.2's interlacing conditions on $C$ make this coloring a well-defined Sperner labeling (Proposition 4.3).
What would settle it
Enumerate all non-$r$-invariant permutations for $k=5$, $q=3$, compare the greedy count of non-monochromatic hyperedges with the two-color distance-coloring count for a good pair, and check whether the strict decrease predicted by Theorem 4.8 holds in every case; alternatively, search for $x\in A_i$ and $y\in A_j$ with $xy$ an edge of $G^{\pi}_{k,q}$ under the conditions of Definition 4.2, which would disprove Proposition 4.3.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that the greedy Sperner coloring does not exhaust the optimal-labeling problem for the simplex-lattice hypergraphs $H^{\pi}_{k,q}$: once the identity permutation is replaced by any permutation not invariant under the dihedral rotation $r$, there exists a Sperner coloring---the distance coloring attached to a good two-element set of colors---that leaves fewer non-monochromatic hyperedges than the greedy coloring (Theorem 4.8). More sharply, for $\pi=(i-1)(i-2)\cdots 1\,(i+1)(i+2)\cdots(k-1)i$, the distance coloring with colors $1$ and $i+1$ is optimal among all Sperner labelings (Theorem 4.10), giving the exact maximum number of monochromatic hyperedges. The construction rests on a structural characterization of the line graph: the graph $G_{\pi}$ on $[k]$, whose edges record which intervals of consecutive integers appear as contiguous subsequences of $\pi$, is exactly a dissection of a regular $k$-gon into cycle or clique regions, and it can be identified with the intersection of a simplex in the alcoved triangulation of a hypersimplex with the hypersimplex's 1-skeleton.
Load-bearing premise
The construction works only if the interlacing conditions of Definition 4.2 truly prevent every edge of the line graph from joining two vertices colored differently by the distance coloring; the proof of Proposition 4.3 is a single compressed paragraph, and a single missed conflict would break Theorems 4.8 and 4.10.
Editorial extensions
If this is right
- For every permutation $\pi$ not fixed by the dihedral rotation, the greedy coloring is strictly suboptimal for $H^{\pi}_{k,q}$, and the two-color distance coloring supplies the improvement.
- For $\pi=(i-1)(i-2)\cdots 1\,(i+1)(i+2)\cdots(k-1)i$, the exact maximum number of monochromatic hyperedges is attained by the distance coloring with colors $1$ and $i+1$; for $\pi=1\,3\,4\cdots(k-1)\,2$ this maximum equals $\binom{k+q-3}{k-1}-N(k,q,1)$ (Corollary 4.11).
- By Theorem 3.21, the optimality of these distance colorings carries over to every permutation in the dihedral orbit of the special family.
- The number of non-colored vertices in the two-color distance coloring satisfies the recurrence $N(k,q,s)=N(k-1,q,s)+N(k,q-1,s)$ and depends only on $k,q$ and $s=|S(\pi)|$, not on the full permutation.
- The identification $G_{\pi}=\sigma_{\pi^{-1}}\cap\Delta^{(\le 1)}_{k,m}$ ties the Sperner-labeling problem to the alcoved triangulation of a hypersimplex.
Reading between the lines
- The paper leaves open whether distance colorings with a good set of more than two colors remain Sperner and whether they are optimal; a direct computation for small $k$ and $q$ would show whether the improvement over greedy grows with the size of the good set.
- Because the two-color count depends only on $|S(\pi)|$, all non-$r$-invariant permutations with the same number of adjacent inversions might improve over greedy by the same amount; the paper's counting formula makes this plausible but does not state it as a theorem.
- The hypersimplex interpretation suggests a continuous reformulation of the optimal-labeling problem over the alcoved triangulation, which could certify optimality for permutations outside the special family.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Sperner labelings of the hypergraph H^π_{k,q} whose hyperedges are facets of type π in the edgewise triangulation of a (k−1)-simplex. It introduces the line graph G^π_{k,q}, a graph G^π that records which intervals of [k] appear contiguously in π, and a dihedral action on permutations. The main claims are: (i) the number of edges of G^π_{k,q} is governed by a "vector of consecutiveness" of π; (ii) for every permutation not invariant under the dihedral rotation, a "distance coloring" derived from an independent set in G^π yields a Sperner labeling of H^π_{k,q} with strictly more monochromatic hyperedges than the greedy coloring; and (iii) for the particular permutations π=(i−1)(i−2)...1(i+1)...(k−1)i, the distance coloring with colors 1 and i+1 is optimal among all Sperner labelings.
Significance. If the main claims were correct, the paper would contribute an interesting family of Sperner colorings that beat the greedy baseline, together with a graph-theoretic encoding of the edgewise-triangulation hypergraphs. Several components are genuinely appealing and explicit: the counting of edges of G^π_{k,q} in terms of the consecutiveness vector (Theorem 2.6), the dissection characterization of the graphs G^π (Theorem 3.5), and the construction of a dihedral action on S_{k−1} that is equivariant with respect to G^π (Theorem 3.15). The counting formulas in Section 4.2 for non-colored vertices are also closed-form and testable. However, the central reduction in Section 2 on which all of Section 4 rests is false, and the distance coloring is not shown to be a Sperner labeling; in fact it fails for a small example. The main theorems are therefore not supported as stated.
major comments (4)
- [Section 2, Eq. (2.6)] The criterion "F(v,π) can be i-monochromatic iff v_{i−1}<v_i for i∉S(π), and v_{i−1}<v_i−1 for i∈S(π)" is false because it checks only the initial vertex v of the facet, not all vertices of F(v,π). For k=4, π=1 3 2, we have S(π)={2}. Take v=(0,1,2) and i=3. Since i∉S(π), the condition v_2<v_3 holds (1<2), so the criterion puts 3 into L^π(v). But F(v,π) has vertices (0,1,2), (0,2,2), (0,2,3), (1,2,3), and the vertex (0,2,2) has v_2=v_3, so label 3 is not admissible there by (1.2). Thus F(v,π) cannot be 3-monochromatic. Consequently Eq. (2.6) does not describe the set of colors for which the hyperedge can be monochromatic, and the reduction of Sperner labelings of H^π to colorings of the line graph G^π is invalid.
- [Proposition 4.3] The proof of Proposition 4.3 only argues that two vertices of G^π receiving different colors cannot be adjacent in G^π. It never verifies that every vertex of the facet F(x,π) admits the color assigned to x, which is required by (1.2). This is not a cosmetic omission: for π=1 3 2 and the good set C={1,3}, the distance coloring puts x=(0,1,2) in A_3 because x_3−x_2=1 > x_1=0, yet F(x,π) contains (0,2,2), which cannot be labeled 3. Hence the distance coloring is not a Sperner labeling of H^π in this case, contradicting the conclusion of Proposition 4.3. This example belongs to the permutation family of Theorem 4.10 with k=4 and i=2, so the optimality claim for that family is not vacuous; the proposed coloring is invalid.
- [Theorem 4.8] The proof of Theorem 4.8 is a one-sentence assertion: "Applying induction and the recurrence relation (4.3), we conclude that N(k,q,|S(π)|) is strictly less than in the greedy coloring case." No induction is shown, no base cases are treated, and the inequality N(k,q,s) < binomial(k+q−s−3,k−2) is not verified for all relevant q and s. Since the definition of N(k,q,s) depends on the invalid admissibility criterion, this is a load-bearing gap, not a mere matter of exposition.
- [Theorem 4.10] The optimality proof relies on an unproven clique-cover assertion. The families C^1_x and C^{i+1}_y are stated to be cliques and to cover W^π, but no verification is given that each displayed set is a clique, that the cliques are pairwise disjoint, or that the assignment of vertices to cliques is well-defined. In particular, for v∈W^π \(A_1 ∪ A_{i+1}), the choice of the containing clique depends on the unknown color ℓ(v), so the proposed injection from colored vertices to cliques is not a valid upper-bound certificate. Without a correct disjoint-clique cover, the claimed maximum |A_1|+|A_{i+1}| does not follow.
minor comments (4)
- [Abstract and Introduction] There are several typos and grammatical slips: "hyperedegs" should be "hyperedges", "more monochromatic hyperedges then" should be "than", and "This colorings are also optimal" should be "These colorings are also optimal".
- [Remark 1.7] The display for the condition on i∈S(π) contains a malformed brace: "for all j≤π^{-1}(i)}or j≥π^{-1}(i−1)+1" should be split or rewritten.
- [Theorem 3.5] The proof says the base cases k=3,4,5 "can be verified directly" and the converse step is described without checking that the constructed permutation indeed avoids the forbidden crossing edges; this is acceptable as a sketch but should be expanded.
- [Equation (3.2)] The displayed formula ends with an unmatched closing parenthesis: "cs_m(π)=... (3.2)" should be "cs_m(π)=... ."
Circularity Check
No significant circularity: distance coloring is a new construction benchmarked against an external greedy-coloring result; no fitted inputs, no load-bearing self-citations, and no equation reduces by definition to the claimed theorem.
full rationale
The paper's central claim (Theorem 4.8) is that for every permutation not invariant under the rotation r of the dihedral action, there exists a Sperner coloring of H^pi_{k,q} with more monochromatic hyperedges than the greedy coloring. The distance coloring (Definition 4.1) is an explicit construction from a chosen independent set C of the graph G^pi; the 'good set' conditions (Definition 4.2) are hypotheses under which the construction can be shown to be a well-defined Sperner labeling (Proposition 4.3), not parameters fitted to force the desired conclusion. The count of non-colored vertices (Theorem 4.7) is derived from a combinatorial count of weak compositions (Proposition 4.6), and the strict inequality against the greedy baseline is a separate combinatorial comparison. The greedy baseline itself is taken from the external work of Mirzakhani and Vondrak [9], and the paper cites no prior work by its own authors that is load-bearing for the main theorems. The optimality result for the specific permutation family (Theorem 4.10) is argued via an explicit clique-covering construction, again not by defining the target result into the construction. The skeptical concern that Eq. (2.6) may not correctly characterize monochromatic hyperedges is a mathematical correctness issue about the reduction between hypergraph labelings and line-graph colorings, not a circularity: the claimed equivalence is stated as a fact and used as a tool, but the paper's main theorem does not take that equivalence as its conclusion. No equation in the paper is equivalent by construction to the asserted improvement over the greedy coloring, and no fitted parameter is renamed as a prediction. Therefore the derivation chain is self-contained against an external benchmark, and the correct circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption The edgewise subdivision T_{k,q} has facets F(v,pi) exactly as described in (1.1), from Edelsbrunner-Grayson [6].
- standard math The greedy coloring is optimal for H^Id_{k,q} (Mirzakhani-Vondrak, Proposition 1.2).
- domain assumption The alcoved triangulation of the hypersimplex is parametrized by permutations with a fixed number of adjacent inversions (Lam-Postnikov, Theorem 1.8).
Cite this review
Pith. "Pith review of Sperner's colorings of hypergraphs arising from edgewise triangulations." pith.science (2026). https://pith.science/paper/35GQX57L
@misc{pith2026250607201,
author = {Pith},
title = {Pith review of: Sperner's colorings of hypergraphs arising from edgewise triangulations},
year = {2026},
howpublished = {\url{https://pith.science/paper/35GQX57L}},
note = {Machine review of arXiv:2506.07201}
}
abstract
We investigate Sperner's labelings of $H^\pi_{k,q}$, the hypergraph whose hyperedges are facets of the edgewise triangulation of a $(k-1)$-simplex defined by a permutation $\pi\in \mathbb{S}_{k-1}$. Mirzakhani and Vondr\' ak showed that the greedy coloring of $H^{\mathrm{Id}}_{k,q}$ produces the maximal number of monochromatic hyperedges. The line graph of $H_{k,q}^\pi$ is built from the copies of the graph $G_\pi$ that represents which subsets of consecutive numbers of $[k-1]$ are contiguous in $\pi$. We characterize these graphs in terms of dissections a regular $k$-gon and also show how they encode the adjacency relation between a hypersimplex and the facets of its alcoved triangulation. The natural action of the dihedral group $D_k$ on a regular $k$-gon and graphs $G_\pi$ extends on the group of permutations $\mathbb S_{k-1}$. Independent sets of the graphs $G_\pi$ of the permutations that are not invariant under the rotation are used to define a class of Sperner's colorings that produce more monochromatic hyperedges then the greedy colorings. This colorings are also optimal for a certain permutations.
Reference graph
Works this paper leans on
-
[1]
Albert, M. H.; Atkinson, M. D. Simple permutations and pattern restricted permutations. Discrete Math. 300 (2005), no. 1-3, 1–15
work page 2005
-
[2]
Geometric view of interval poset permutations.Preprint, arXiv:2411.13193 [math.CO] (2024)
Bagno, Eli; Eisenberg, Estrella; Reches, Shulamit; Sigron, Moriha. Geometric view of interval poset permutations.Preprint, arXiv:2411.13193 [math.CO] (2024)
-
[3]
Bj¨ orner, A.: Shellable and Cohen-Macaulay partially ordered sets. Trans. Am. Math. Soc. 260, 159–183 (1980)
work page 1980
-
[4]
The interval posets of permutations seen from the decomposition tree perspective
Bouvel, Mathilde; Cioni, Lapo; Izart, Benjamin. The interval posets of permu- tations seen from the decomposition tree perspective. Preprint, arXiv:2110.10000 [math.CO] (2021). 25
work page Pith review arXiv 2021
-
[5]
A survey of simple permutations
Brignall, Robert. A survey of simple permutations. Permutation patterns, 41– 65, London Math. Soc. Lecture Note Ser., 376, Cambridge Univ. Press, Cambridge, 2010
work page 2010
-
[6]
Edelsbrunner, H.; Grayson, D. R. Edgewise subdivision of a simplex. ACM Sym- posium on Computational Geometry (Miami, FL, 1999). Discrete Comput. Geom. 24 (2000), no. 4, 707–719
work page 2000
-
[7]
Lam, Thomas; Postnikov, Alexander. Alcoved polytopes I. Discrete Comput. Geom. 38 (2007), no. 3, 453–478
work page 2007
-
[8]
Closed form formula for the number of restricted compositions
Jakliˇ c, Gaˇ sper; Vitrih, Vito;ˇZagar, Emil. Closed form formula for the number of restricted compositions. Bull. Aust. Math. Soc. 81 (2010), no. 2, 289–297
work page 2010
Show all 16 references
-
[9]
Sperner’s colorings, hypergraph labeling problems and fair division
Mirzakhani, Maryam; Vondr´ ak, Jan. Sperner’s colorings, hypergraph labeling problems and fair division. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 873–886, SIAM, Philadelphia, PA, 2015
2015
-
[10]
Sperner’s colorings and optimal partition- ing of the simplex
Mirzakhani, Maryam; Vondr´ ak, Jan. Sperner’s colorings and optimal partition- ing of the simplex. A journey through discrete mathematics, 615–631, Springer, Cham, 2017
2017
-
[11]
Petersen, T. Kyle. Eulerian numbers. Birkh auser/Springer, New York, 2015
2015
-
[12]
Interval posets of permutations
Tenner, Bridget Eileen. Interval posets of permutations. Order 39, No. 3, 523- 536 (2022)
2022
-
[13]
Neil J. A. Sloane and The OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences
-
[14]
Stanley, R.P Enumerative combinatorics. Vol. 1., Cambridge University Press, 2012
2012
-
[15]
Gr¨ obner bases and convex polytopes, University Lecture Series, 8
Sturmfels, Bernd. Gr¨ obner bases and convex polytopes, University Lecture Series, 8. American Mathematical Society, Providence, RI, 1996
1996
-
[16]
IAS/Park City Mathematics Series 13, 497–615 (2007)
Wachs, M Poset topology: tools and applications, in Miller, Ezra (ed.) et al., Geometric combinatorics. IAS/Park City Mathematics Series 13, 497–615 (2007). Duˇ sko Joji´ c University of Banja Luka, Faculty of Science Mladena Stojanovi´ ca 2, 78 000 Banja Luka Bosnia and Herze...
2007
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.