Pith. sign in

REVIEW 3 major objections 5 minor 19 references

On the minimum number of non-monochromatic simplices for Sperner labelings of a regular triangulation

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper establishes that every Sperner labeling of the regular triangulation of $\Delta_{k,q}$ has at least $\binom{q+k-3}{k-2}$ non-monochromatic simplices, and that some Sperner labeling has at most $q^{k-1}-(q-1)^{k-1}$ of them.

desk verdict Likely-correct step toward Mirzakhani–Vondrák's conjecture for the standard triangulation, but the graph-characterization proof needs repair before acceptance. read the letter →

arxiv 2506.05581 v1 pith:FRBULL5P submitted 2025-06-05 math.CO

L. Á. Calvo , S. Merchán , D. Raboso , J. Rodrigo , J. S. Rodríguez This is my paper · ORCID
classification math.CO MSC 05C1505B25
keywords Spernerlabelingnon-monochromaticsimplicesregulartriangulationsimplex-latticehypergraphproblemdiscretesimplexfirstchoiceedgewisesubdivision
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies a question left open in the literature: for a Sperner labeling of a triangulated integer simplex, how few simplices can fail to be monochromatic? Working with the regular triangulation of the discrete simplex $\Delta_{k,q}$, the paper proves that every Sperner labeling produces at least $\binom{q+k-3}{k-2}$ non-monochromatic simplices. It also constructs a Sperner labeling with at most $q^{k-1}-(q-1)^{k-1}$ such simplices, so for fixed dimension $k$ the true minimum has order $\Theta(q^{k-2})$. This matches the growth predicted for cells using at least two colors and gives matching-order bounds for this triangulation. Exact values are obtained when $k=2$ or when $q\in\{1,2\}$.

What carries the argument

The carrying object is the graph $G_k$ on the integer points of $\Delta_{k,q}$: two vertices are adjacent when their coordinate-wise difference has entries in $\{-1,0,1\}$, with equally many $+1$'s and $-1$'s, and with the nonzero signs alternating from left to right. Corollary 3.15 states that the cells of the regular triangulation $T$ are exactly the convex hulls of $k$ pairwise adjacent vertices of $G_k$. This graph criterion is what allows each hyperedge of the simplex-lattice hypergraph to be recognized as a cell of $T$, so that the known hypergraph lower bound applies unchanged to the triangulation.

What would settle it

Test the small case $k=3,q=3$ by exhaustive search over all Sperner labelings of $T$; if any labeling has fewer than $\binom{3}{1}=3$ non-monochromatic simplices, the lower bound is false. Alternative check: find a set $\{b+e_1,\ldots,b+e_k\}$ whose vertices are not pairwise adjacent in $G_k$, which would break the claimed embedding of hyperedges into $T$.

Watch

Extended reading notes

Core claim

The central claim is that the minimum number $m_{k,q}$ of non-monochromatic simplices in a Sperner labeling of the regular triangulation $T$ of $\Delta_{k,q}$ satisfies $$\binom{q+k-3}{k-2} \le m_{k,q} \le $q^{{k-1}}$-(q-1)^{k-1}.$$ The lower bound is obtained by embedding the simplex-lattice hypergraph into $T$: each hyperedge $\{b+e_1,\ldots,b+e_k\}$ with $b\in\Delta_{k,q-1}$ is claimed to be a cell of $T$, so any Sperner labeling must make at least as many non-monochromatic simplices as the hypergraph forces. The upper bound is attained by the first-choice labeling, which colors each vertex by its smallest positive coordinate; in that labeling the non-monochromatic cells are exactly those touching the facet $x_1=0$, and counting them yields the formula. Equality cases include $k=2$, $q=1$, and $q=2$.

Load-bearing premise

The lower bound assumes both that the cited hypergraph count is correct and that each set of $k$ lattice points obtained by moving one step in each coordinate direction from a common base point is a cell of the regular triangulation; if either fails, the triangulation lower bound does not follow.

Editorial extensions

If this is right

  • For fixed dimension $k$, the minimum $m_{k,q}$ grows like $\Theta(q^{k-2})$, because the lower bound $\binom{q+k-3}{k-2}$ and the upper bound $q^{k-1}-(q-1)^{k-1}$ have the same order.
  • The two-color case of the open conjecture is settled for this triangulation: every Sperner labeling has $\Omega(q^{k-2})$ cells containing at least two labels.
  • The exact values are $m_{2,q}=1$ for all $q$, $m_{k,1}=1$, and $m_{k,2}=2^{k-1}-1$.
  • The first-choice labeling realizes the upper bound, so colorings that assign each vertex its first nonzero coordinate are within a constant factor of optimal for fixed $k$.
  • The gap between the lower-bound constant $1/(k-2)!$ and the upper-bound constant $k-1$ remains open for $k>2$ and $q>2$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the same graph-embedding method extends to cells containing $j>2$ labels, the conjecture's higher-color cases would reduce to analogous hypergraph counting problems, provided such bounds exist.
  • The upper bound suggests a testable strengthening: exhaustive search for small $k$ and $q$ could check whether the exact value always equals the first-choice-labeling count, as the paper conjectures.
  • Because the regular triangulation is the edgewise subdivision of a simplex, the bounds might be reproducible by an inductive subdivision count, which would give a route toward the exact constant.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the minimum number m_{k,q} of non-monochromatic maximal simplices in Sperner labelings of a particular triangulation T of the discrete simplex Δ_{k,q} (the set of integer points in a (k-1)-simplex). The main results are a lower bound m_{k,q} ≥ binom(q+k-3,k-2) (Theorem 1.1, proved in Section 4) and an upper bound m_{k,q} ≤ q^{k-1}-(q-1)^{k-1} (Theorem 1.2, proved in Section 5). The upper bound is obtained from the explicit first-choice labeling; the lower bound is obtained by embedding the hyperedges of the simplex-lattice hypergraph H_{k,q} as cells of T and then invoking Proposition 2.1 of Mirzakhani–Vondrák. The proof of the embedding relies on a graph-theoretic characterization of T developed in Section 3.

Significance. If the lower-bound proof can be completed, the paper resolves the j=2 case of the Mirzakhani–Vondrák conjecture for this triangulation: for fixed k, m_{k,q} is Θ(q^{k-2}). The upper bound is explicit and constructive, and the lower-bound strategy (embedding a known hypergraph into the triangulation) is natural. The paper does not rely on numerical fitting or self-citation. The main caveat is that the characterization of T in Section 3 is not rigorously established as written; however the specific embedding of hyperedges appears to admit a direct proof, so the central claim is likely correct.

major comments (3)
  1. [Section 3, Proposition 3.8] The converse direction is not proved. From Conv(v_1,...,v_k) intersecting the interior of some σ(w,π), the text asserts 'Since this edge is an intersection of simplices of T_k, then σ(w',π) contains an interior point of σ(w,π) for some w'...' This does not follow, and it also presupposes that T_k is already known to be a triangulation with the intersection property, which is not proved in the paper. Since Proposition 3.8 is used to obtain Corollary 3.12 and hence Corollary 3.15, the characterization used in Theorem 4.3 is not rigorously established. Please replace this by a complete proof, or supply a precise citation establishing that the collection σ(w,π) is a triangulation.
  2. [Section 3, Proposition 3.11] The proof of E''_k ⊆ E'_k contains indexing errors in Case 2. The displayed permutation sets π(j+1)=i_k, but the indices are i_1,...,i_{k-1}, so i_k is undefined; moreover π(k) is outside the domain {1,...,k-1}. The verification of consistency with w_2 also treats only some subcases. Consequently the isomorphism G'_k ≅ G''_k is not established as written. This is load-bearing because Corollary 3.12 and Corollary 3.15 depend on it.
  3. [Section 4, Theorem 4.3] The reduction to Proposition 2.1 of [5] requires that the map from hyperedges of H_{k,q} to simplices of T is injective and that each hyperedge is actually a maximal cell of T. The proof only checks pairwise adjacency in G_k, so it inherits the unresolved status of Corollary 3.15. Injectivity is not addressed, although it follows easily from the fact that the sum of the k vertices of a hyperedge determines b. Please add this verification and either repair Corollary 3.15 or give the direct construction: for b∈V_{k,q-1}, set w_j=b_1+...+b_j; then the hyperedge equals φ(σ(w,id)).
minor comments (5)
  1. [Section 2, Definition 2.3] There is a typo: 'v_i = 0 ⇒ c(v),i' should read 'v_i = 0 ⇒ c(v) ≠ i'.
  2. [Section 3, Proposition 3.8] The notation 'Conv(v_1,...,v_k) < T'_k' should be 'Conv(v_1,...,v_k) ∉ T'_k'.
  3. [Section 5, Theorem 5.1] The proof should justify that the restriction of T to the region x_1 ≥ 1 is exactly the regular triangulation of Δ_{k,q-1}; this is standard but should be stated explicitly rather than asserted.
  4. [Section 4, Example 4.4] The proof that there is at most one monochromatic simplex for q=2 is hard to follow; the assertion that there is 'just one simplex' with the stated property should be proved by describing the structure of the q=2 triangulation.
  5. [Section 4, Theorem 4.3] The paper should state explicitly the exact form of Proposition 2.1 of [5] that is being invoked, so that the lower-bound argument is self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is transferred from an external theorem and the upper bound is an explicit construction.

full rationale

The derivation chain is self-contained in the sense relevant to circularity. Theorem 4.3 obtains the lower bound by observing that every hyperedge of the simplex-lattice hypergraph H_{k,q} is a cell of the regular triangulation T, and then invoking Proposition 2.1 of Mirzakhani and Vondrák [5] for the lower bound on non-monochromatic hyperedges; that result is an external, parameter-free theorem about a different object and is not equivalent to Theorem 1.1. The upper bound in Theorem 5.1 is a direct construction using the first-choice labeling, counting the cells not containing a vertex with x_1=0; it introduces no fitted parameter and does not presuppose the lower bound. The graph-based characterization of T (Corollary 3.15) may have proof gaps—Proposition 3.8's converse is only sketched and Proposition 3.11 contains apparent indexing issues—but those are correctness risks, not circularity, since the characterization is not assumed as an input. The paper contains no self-citations by the present authors and does not rename a known empirical pattern as a new prediction. Hence no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

No free parameters, no invented entities. The central derivation relies on the external lower-bound theorem [5, Prop 2.1] and standard convex-geometric facts about triangulations; both are inherited assumptions rather than contributions.

assumptions (2)
  • domain assumption Mirzakhani-Vondrák Proposition 2.1: for the simplex-lattice hypergraph H_{k,q}, any Sperner labeling has at least binomial(q+k-3,k-2) non-monochromatic hyperedges.
    The proof of Theorem 4.3 cites [5] for exactly this bound; the paper does not prove it, so the lower bound rests on this external result.
  • standard math Standard properties of simplicial complexes: cells of a triangulation intersect only in common faces and have disjoint interiors.
    Used in the definition of T_k and in Proposition 3.8's attempted proof, and implicitly in the counting arguments of Sections 4 and 5.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the minimum number of non-monochromatic simplices for Sperner labelings of a regular triangulation." pith.science (2026). https://pith.science/paper/FRBULL5P

@misc{pith2026250605581,
  author       = {Pith},
  title        = {Pith review of: On the minimum number of non-monochromatic simplices for Sperner labelings of a regular triangulation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FRBULL5P}},
  note         = {Machine review of arXiv:2506.05581}
}
abstract

Attending to an open problem in the literature stated by Mirzakhani and Vondr\'ak, we give a lower bound of the number of non-monochromatic simplices for Sperner labelings of the vertices of a triangulation of a given $ k$-simplex with vertices of integer coordinates. This triangulation maximizes the number of simplices over all the triangulations of the $ k$-simplex with vertices of integer coordinates.

Figures

Figures reproduced from arXiv: 2506.05581 by the authors.

Figure 1
Figure 1. Comparison of Lower Bound and First Choice mk,q, for k = 4. References [1] A. Ene, J. Vondr´ak (2014) Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture, In Proc. of APPROX, 144–159. [2] C. Chekuri, A. Ene (2011) Submodular Cost Allocation Problem and Applications, Proc. of ICALP, 354–366. [3] J. M. Kleinberg, E. Tardos (2002) Approximation Algorithms for Classification Prob￾l… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [5]

    Mirzakhani, J

    M. Mirzakhani, J. Vondr´ ak (2015)Sperner’s Colorings, Hypergraph Labeling Prob- lems and Fair Division, Proc. of ACM-SIAM SODA, 873–886

    work page 2015

  2. [1]

    A. Ene, J. Vondr´ ak (2014)Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture, In Proc. of APPROX, 144–159

    work page 2014

  3. [2]

    Chekuri, A

    C. Chekuri, A. Ene (2011)Submodular Cost Allocation Problem and Applications, Proc. of ICALP, 354–366

    work page 2011

  4. [3]

    J. M. Kleinberg, E. Tardos (2002)Approximation Algorithms for Classification Prob- lems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Jour- nal of the ACM, 49, 5, 616–639

    work page 2002

  5. [4]

    Mirzakhani, J

    M. Mirzakhani, J. Vondr´ ak (2017)Sperner’s Colorings and Optimal Partitioning of the Simplex, A Journey Through Discrete Mathematics, Springer, 615–631

    work page 2017

  6. [6]

    W. M. Douglas (1992)Simplicial Mesh Generation with Applications, Ph.D. thesis, Cornell University

    work page 1992

  7. [7]

    Edelsbrunner, D

    H. Edelsbrunner, D. R. Grayson (2000)Edgewise Subdivision of a Simplex, Discrete & Computational Geometry, 24, 4, 707–719

    work page 2000

  8. [8]

    T. Le, C. Van, N.-S. Pham, C. Saglam (2022)A Direct Proof of the Gale–Nikaido–Debreu Lemma Using Sperner’s Lemma, Journal of Optimization The- ory and Applications, 194. 15

    work page 2022

Show all 19 references
  1. [9]

    Le Van (1982)Topological Degree and the Sperner Lemma, Journal of Optimization Theory and Applications, 37, 3, 371–377

    C. Le Van (1982)Topological Degree and the Sperner Lemma, Journal of Optimization Theory and Applications, 37, 3, 371–377

    1982

  2. [10]

    Kumar, K

    A. Kumar, K. G. (2017)The Simplex Reminiscent of Sperner’s Lemma, IARJSET, 4

    2017

  3. [11]

    F. E. Su (1999)Rental Harmony: Sperner’s Lemma in Fair Division, The American Mathematical Monthly, 106, 10, 930–942

    1999

  4. [12]

    Meunier (2006)Sperner labellings: A combinatorial approach, Journal of Combi- natorial Theory, Series A, 113, 7, 1462–1475

    F. Meunier (2006)Sperner labellings: A combinatorial approach, Journal of Combi- natorial Theory, Series A, 113, 7, 1462–1475

    2006

  5. [13]

    J. A. De Loera, E. Peterson, F. E. Su (2002)A Polytopal Generalization of Sperner’s Lemma, Journal of Combinatorial Theory, Series A, 100, 1, 1–26

    2002

  6. [14]

    H. Aziz, S. Mackenzie (2016)A Discrete and Bounded Envy-Free Cake Cutting Pro- tocol for Any Number of Agents, Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 416–427

    2016

  7. [15]

    S. Liu, X. Lu, M. Suzuki, T. Walsh (2024)Mixed Fair Division: A Survey, Journal of Artificial Intelligence Research, 80, 1373–1406

    2024

  8. [16]

    K. T. Atanassov (1996)On Sperner’s Lemma, Studia Scientiarum Mathematicarum Hungarica, 32, 1, 71–74

    1996

  9. [17]

    Asada, F

    M. Asada, F. Frick, V. Pisharody, M. Polevy, D. Stoner, L. H. Tsang, Z. Wellner (2018)Fair Division and Generalizations of Sperner- and KKM-type Results, SIAM Journal on Discrete Mathematics, 32, 1, 591–610

    2018

  10. [18]

    Duli´ nski (2020)Homotopies and Transcendental Extensions in Colouring Prob- lems, available athttps://arxiv.org/abs/2011.12273

    W. Duli´ nski (2020)Homotopies and Transcendental Extensions in Colouring Prob- lems, available athttps://arxiv.org/abs/2011.12273

    2020 arXiv

  11. [19]

    Kaiser, M

    T. Kaiser, M. Stehl´ ık, R.ˇSkrekovski (2024)Criticality in Sperner’s Lemma, Combi- natorica, 44, 5, 1041–1051. Luis ´Angel Calvo Pascual, Dpto. de M ´etodos Cuantitativos, ICADE, Universidad Pon- tificia Comillas de Madrid, Spain Email address:lacalvo@comillas.edu Susana Merc...

    2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.