On a Question of Mirzakhani and Vondr'ak concerning Sperner Labelings of the Simplex-Lattice Hypergraph

arXiv:2511.03036 · math.CO · Submitted 2025-11-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "On a Question of Mirzakhani and Vondr'ak concerning Sperner Labelings of the Simplex-Lattice Hypergraph".

Emmy: Here's the gist of the paper. This paper provides a positive answer to whether there is a Sperner-admissible labeling of the simplex-lattice hypergraph such that each hyperedge uses at most 2 colors.

Ada: Theorem 1 proves that for q > k, the mapping l is a well-defined Sperner-admissible labeling of Vk,q.

Emmy: Theorem 2 further establishes that for q > k, the mapping l π is a Sperner-admissible labeling such that each hyperedge of Hπk,q uses at most 2 colors.

Ada: Preliminaries and Definitions The paper begins by defining the simplex-lattice hypergraph Hk,q as a k-uniform hypergraph whose vertex set is Vk,q and whose set of hyperedges Ek,q is given with Ek,q = F(v): v ∈ Vk,q−1.

Title and authors: Ada: So we're talking about this paper today called "On a Question of Mirzakhani and Vondr'ak concerning Sperner Labelings of the Simplex-Lattice Hypergraph". We’re focusing on what they are trying to prove here.

Emmy: They are essentially asking if there is a way to label this simplex-lattice hypergraph, which we call Hk,q, such that every hyperedge uses at most two colors.

Kolya: It seems like the context for this is very specific geometry related to how we subdivide a simplex in k dimensions.

Ada: Right, and the paper sets up these definitions involving functions r and i for each vertex v in Vk,q so they can construct this labeling.

Emmy: The paper then moves on to showing that when q is greater than k, this mapping l is well-defined and Sperner-admissible for the vertices Vk,q.

Kolya: So the first big result seems to be establishing that for the basic simplex lattice hypergraph Hk,q, this labeling works under certain conditions.

The paper's summary: Ada: Looking at what they've summarized in "On a Question of Mirzakhani and Vondr'ak concerning Sperner Labelings of the Simplex-Lattice Hypergraph", the main thrust is proving that for q greater than k, there exists a labeling where every hyperedge has at most two colors.

Emmy: They do this by defining functions r and i on the vertices, which then define a labeling l, and they use these definitions to show that for Hk,q, each hyperedge only uses two colors if q is bigger than k.

Kolya: It’s interesting how they handle the case where r is zero versus when it's greater than zero in proving that the labels are constant along certain sequences of vertices within a hyperedge.

Ada: That's right, and they show that if r is zero, then i is also zero and all vertices in that edge have the same label which is one.

Emmy: But when r is greater than zero, they show the labels stay constant along certain sequences of vertices within the hyperedge based on how the coordinates increase.

The paper's improvements: Ada: Now let's talk about what they suggest as improvements in "On a Question of Mirzakhani and Vondr'ak concerning Sperner Labelings of the Simplex-Lattice Hypergraph". They introduce a generalization to Hpi k,q for any permutation pi.

Emmy: They define i pi and l pi based on that permutation, which essentially modifies the original labeling definitions using the structure of the permutation itself.

Kolya: The key insight they mention is that among all coordinates t of v where t minus v t equals r, the coordinate i of v is special because it's the last one to increase when you move along a hyperedge F(v, pi).

Ada: So by using this structural property related to the permutation pi, they can modify the definitions of i and l so that each hyperedge of Hpi k,q uses at most two colors.

Emmy: It seems they've shown that by incorporating the permutation structure into the labeling, you can achieve this two-color constraint for these generalized simplex lattice hypergraphs.

Conclusion: Ada: So to wrap up "On a Question of Mirzakhani and Vondr'ak concerning Sperner Labelings of the Simplex-Lattice Hypergraph", the main conclusion is that yes, there exists a Sperner-admissible labeling where each hyperedge uses at most two colors for both Hk,q and Hpi k,q when q is greater than k.

Emmy: This means we have a constructive way to get this coloring when you move from the basic structure to the more complex permuted ones too.

Kolya: I just want to say that while they prove it for q greater than k, they don't really discuss what happens when q is smaller than k. That's an important limitation because it might restrict where this fair division algorithm can be applied in practice.

Ada: That's a fair point, Kolya. So the implication for us is that we have a solid framework for resource allocation problems modeled by these geometric structures, provided our input constraints meet that q greater than k requirement.

Emmy: It’s a solid result because it shows that the structure of these hypergraphs allows for this specific type of coloring, which is exactly what we need for better fair division algorithms.

Ognjen Papaz, Dušsko Jojišc

Faculty of Philosophy, University of East Sarajevo, Bosnia and Herzegovina · Faculty of Science, University of Banja Luka, Bosnia and Herzegovina

math.CO

Submitted: 2025-11-04

Updated: 2026-11-09

Comments: We introduce the dominant labeling, which answers the question of Mirzakhani and Vondrák affirmatively. We enumerate the vertices of each color and the hyperedges receiving each pair of colors, expressing both counts through Catalan's triangle. We also characterize the color sets of hyperedges in the other hypergraphs arising from the edgewise triangulation

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 70/100

The gist: This paper provides a positive answer to whether there is a Sperner-admissible labeling of the simplex-lattice hypergraph such that each hyperedge uses at most 2 colors.

Key concepts

Simplex-Lattice Hypergraph ($H_{k,q}$)
This is a $k$-uniform hypergraph defined on integer points in a specific simplex. Its vertices are integer points $(v_1, ext{...}, v_k)$ within the range $[0, q]$. The hyperedges correspond to certain cells in the edgewise subdivision of the simplex, representing geometric structures.
Sperner-Admissible Labeling ($l$ or $l_\pi$)
This is a specific assignment of colors (labels from $[k]$) to vertices. A labeling is 'Sperner-admissible' if for any vertex $v$, the color assigned to it, $\ell(v)$, ensures that the coordinate $v_i$ increases whenever the label is $i$. This condition relates the labeling directly to the ordering of coordinates.
Hyperedge Color Constraint
The core finding is that for both hypergraphs ($H_{k,q}$ and $H_{\pi k,q}$), a specific Sperner-admissible labeling results in each hyperedge using at most two colors. This property is crucial because it guarantees that the division of resources represented by the vertices within any geometric structure adheres to a simple fairness criterion.
Permutation Consistency ($\pi$ consistent with $v$)
A permutation $\pi$ is consistent with a vertex $v$ if, whenever two adjacent coordinates in $v$, say $v_i$ and $v_{i+1}$, are equal ($v_i = v_{i+1}$), the permutation maps the index of the larger coordinate to an index that appears later in $\pi$. This consistency links the geometric structure defined by $H_{\pi k,q}$ to specific ordering rules within the labeling.

Terminology

Summary

This paper provides a positive answer to whether there is a Sperner-admissible labeling of the simplex-lattice hypergraph such that each hyperedge uses at most 2 colors. p. 0

Where the paper says it

A labeling of the Simplex-Lattice Hypergraph with at most 2 colors on each hyperedge Ognjen Papaz∗ Duˇsko Joji´c† Abstract This paper provides a positive answer to the question of Mirzakhani and Vondrak from [2] that asks if there is a Sperner-admissible labeling of the simplex-lattice hypergraph such that each hyperedge uses at most 2 colors. 1 Introduction In ([2], section 4) the authors proved that for k ≥ 4 and q ≥ k 2 , there is a Sperner-admissible labeling of the simplex-lattice hypergraph Hk,q such that every hyperedge of Hk,q contains at most 4 colors.

Theorem 1 proves that for q > k, the mapping l is a well-defined Sperner-admissible labeling of Vk,q. p. 2
Where the paper says it

Proposition 1. For q > k, the mapping ℓ is well-defined Sperner-admissible labeling of Vk,q.

Theorem 2 further establishes that for q > k, the mapping l π is a Sperner-admissible labeling such that each hyperedge of Hπk,q uses at most 2 colors. p. 4
Where the paper says it

Now we consider if there exist a Sperner-admissible labeling of Vk,q such that each hyperedge of Hπ k,q (π ∈ Sk−1) uses at most 2 colors. Analyzing the proof of the previous theorem we see that the labeling ℓ works because among all coordinates vt of v such that t−vt = r(v) the coordinate vi(v) is the last coordinate that increases when obtaining the vertices of the hyperedge F(v).

Preliminaries and Definitions

The paper begins by defining the simplex-lattice hypergraph Hk,q as a k-uniform hypergraph whose vertex set is Vk,q and whose set of hyperedges Ek,q is given with Ek,q = F(v): v ∈ Vk,q−1. The vertices Vk,q are defined as the set of integer points in Rk,q where 0 ≤ vi ≤ vi+1 ≤ q. p. 1

Where the paper says it

, q),(q, q, . Let Vk,q be the set of integer points in Rk,q, i.

The hyperedges F(v) correspond with certain cells of the edgewise subdivision of the simplex Rk,q. p. 1
Where the paper says it

, v + ek−1 + ek−2 + · · · + e1}. The hyperedges of the simplex-lattice hypergraph Hk,q correspond with the certain cells of the edgewise subdivision of the simplex Rk,q.

Specifically, each hyperedge F(v) in Ek,q is equal to F(v, Id(∈ Sk−1)>. p. 1
Where the paper says it

More details about the edgewise subdivision of a simplex can be found in [1]. We see that each hyperedge F(v) in Ek,q is equal to F(v, Id(∈ Sk−1)).

The π-simplex lattice hypergraph Hπk,q (π ∈ Sk−1) is defined with the set of hyperedges Eπk,q given by Eπk,q = F(v, π): v ∈ Vk,q−1 and π is consistent with v. p. 1
Where the paper says it

Extending this correspondence we define the π-simplex-lattice hypergraph. The π-simplex lattice hypergraph is a k-uniform hypergraph Hπ k,q (π ∈ Sk−1) whose set of hyperedges E π k,q is given with E π k,q = {F(v, π) : v ∈ Vk,q−1, π is consistent with v}.

The Sperner-Admissible Labeling Construction

The construction of the labeling relies on defining two functions for each vertex v in Vk,q. Definition 1 defines r(v) as max[t − vt: t ∈ [0, k]] and i(v) as min[t ∈ [0, k]: t − vt = r(v)]. p. 2

Where the paper says it

3 The labeling Definition 1. For each v ∈ Vk,q we define r(v) and i(v) in the following way: r(v) = max{t − vt : t ∈ [0, k]}, i(v) = min{t ∈ [0, k] : t − vt = r(v)}.

The mapping l is then defined by Definition 2 as l(v) = i(v) + 1. p. 2
Where the paper says it

Definition 2. p. 2

Where the paper says it

3 The labeling Definition 1. For each v ∈ Vk,q we define r(v) and i(v) in the following way: r(v) = max{t − vt : t ∈ [0, k]}, i(v) = min{t ∈ [0, k] : t − vt = r(v)}.

We consider the mapping ℓ : Vk,q → [k] defined with ℓ(v) = i(v) + 1.

Proposition 1 states that for q > k, the mapping l is a well-defined Sperner-admissible labeling of Vk,q. p. 2
Where the paper says it

Proposition 1. For q > k, the mapping ℓ is well-defined Sperner-admissible labeling of Vk,q.

The proof shows that if r = 0, then i = 0 and l(v) = 1. p. 4
Where the paper says it

Now we consider if there exist a Sperner-admissible labeling of Vk,q such that each hyperedge of Hπ k,q (π ∈ Sk−1) uses at most 2 colors. Analyzing the proof of the previous theorem we see that the labeling ℓ works because among all coordinates vt of v such that t−vt = r(v) the coordinate vi(v) is the last coordinate that increases when obtaining the vertices of the hyperedge F(v).

Color Constraint Analysis for Hk,q

Theorem 1 demonstrates that for q > k and for the Sperner-admissible labeling l each hyperedge of Hk,q uses at most 2 colors. The proof analyzes the vertices of a hyperedge F(v) and shows that if r = 0, then i = 0 and all vertices in the edge have the same label i + 1 = 1. p. 4

Where the paper says it

Now we consider if there exist a Sperner-admissible labeling of Vk,q such that each hyperedge of Hπ k,q (π ∈ Sk−1) uses at most 2 colors. Analyzing the proof of the previous theorem we see that the labeling ℓ works because among all coordinates vt of v such that t−vt = r(v) the coordinate vi(v) is the last coordinate that increases when obtaining the vertices of the hyperedge F(v).

If r > 0, it is shown that the labels are constant along certain sequences of vertices within the hyperedge. p. 2
Where the paper says it

Let F(v) be a hyperedge of Hk,q and let i = i(v) and r = r(v). p. 2

Where the paper says it

For q > k and for the Sperner-admissible labeling ℓ each hyperedge of Hk,q uses at most 2 colors. Let F(v) be a hyperedge of Hk,q and let i = i(v) and r = r(v).

We denote the vertices of F(v) in the following way v = v, v (k−1) = v+ek−1, v (k−2) = v+ek−1+ek−2, .

Generalization to Hπk,q

The paper then considers the generalization to Hπk,q for π ∈ Sk−1. Definition 3 defines iπ(v) as min[t ∈ [0, k]: π(t) − vπ(t) = r(v)] and lπ(v) as iπ(v) + 1. p. 4

Where the paper says it

For π ∈ Sk−1, let π = 0πk. p. 4

Where the paper says it

Definition 3. For π ∈ Sk−1, let π = 0πk.

For each v ∈ Vk,q we define i π (v) with i π (v) = min{t ∈ [0, k] : π(t) − vπ(t) = r(v)} and ℓ π (v) with ℓ π (v) = i π (v) + 1.

Theorem 2 confirms that for q > k, the mapping l π is a Sperner-admissible labeling such that each hyperedge of Hπk,q uses at most 2 colors. p. 4
Where the paper says it

Now we consider if there exist a Sperner-admissible labeling of Vk,q such that each hyperedge of Hπ k,q (π ∈ Sk−1) uses at most 2 colors. Analyzing the proof of the previous theorem we see that the labeling ℓ works because among all coordinates vt of v such that t−vt = r(v) the coordinate vi(v) is the last coordinate that increases when obtaining the vertices of the hyperedge F(v).

This result is achieved by modifying the definitions of i(v) and l(v) based on the permutation π. p. 4
Where the paper says it

, v+eπ(k−1)+eπ(k−2)+· · ·+eπ(1)} of Hπ k,q, the permutation π prescribes the order in which the coordinates of v are increasing. Thus, we can modify the definitions of i(v) and ℓ accordingly and show that each hyperedge of Hπ k,q will use at most two colors by the same arguments as for ℓ.

Conclusion on Sperner Labeling

The core finding is that the labeling works because among all coordinates vt of v such that t−vt = r(v) the coordinate vi(v) is the last coordinate that increases when obtaining the vertices of the hyperedge F(v, π)> The authors show that by modifying definitions based on π, each hyperedge of Hπk,q will use at most two colors by the same arguments as for l. This confirms a Sperner-admissible labeling exists where each hyperedge uses at most 2 colors. p. 0

Where the paper says it

A labeling of the Simplex-Lattice Hypergraph with at most 2 colors on each hyperedge Ognjen Papaz∗ Duˇsko Joji´c† Abstract This paper provides a positive answer to the question of Mirzakhani and Vondrak from [2] that asks if there is a Sperner-admissible labeling of the simplex-lattice hypergraph such that each hyperedge uses at most 2 colors. 1 Introduction In ([2], section 4) the authors proved that for k ≥ 4 and q ≥ k 2 , there is a Sperner-admissible labeling of the simplex-lattice hypergraph Hk,q such that every hyperedge of Hk,q contains at most 4 colors.

The paper concludes with Theorem 2, which states that for q > k the mapping l π is a Sperner-admissible labeling such that each hyperedge of Hπk,q uses at most 2 colors. p. 4
Where the paper says it

Now we consider if there exist a Sperner-admissible labeling of Vk,q such that each hyperedge of Hπ k,q (π ∈ Sk−1) uses at most 2 colors. Analyzing the proof of the previous theorem we see that the labeling ℓ works because among all coordinates vt of v such that t−vt = r(v) the coordinate vi(v) is the last coordinate that increases when obtaining the vertices of the hyperedge F(v).

References are provided for previous work on related problems. The paper is available as arXiv:2511. p. 0
Where the paper says it

ba †Faculty of Science, University of Banja Luka, Bosnia and Herzegovina dusko. org 1 arXiv:2511.

p. 0
Where the paper says it

ba †Faculty of Science, University of Banja Luka, Bosnia and Herzegovina dusko. org 1 arXiv:2511.

03036v1 [math. p. 0
Where the paper says it

org 1 arXiv:2511. 03036v1 [math.

p. 0
Where the paper says it

org 1 arXiv:2511. 03036v1 [math.

p. 0
Where the paper says it

org 1 arXiv:2511. 03036v1 [math.

p. 0
Where the paper says it

org 1 arXiv:2511. 03036v1 [math.

CO] 4 Nov 2025. p. 0
Where the paper says it

03036v1 [math. CO] 4 Nov 2025

p. 0
Where the paper says it

03036v1 [math. CO] 4 Nov 2025

p. 0
Where the paper says it

03036v1 [math. CO] 4 Nov 2025

p. 0
Where the paper says it

03036v1 [math. CO] 4 Nov 2025

--- Page 1 ---

A labeling of the Simplex-Lattice Hypergraph with at most 2 colors on each hyperedge Ognjen Papaz∗ Duˇsko Joji´c† Abstract This paper provides a positive answer to the question of Mirzakhani and Vondrak from [2] that asks if there is a Sperner-admissible labeling of the simplex-lattice hypergraph such that each hyperedge uses at most 2 colors.

--- Page 2 ---

Denote with Rk,q the simplex in Rk−1 whose vertices are (0, 0,..., 0),(0, 0,..., 0, q),...,(0, q, q..)q),(q, q..)q). Let Vkk be the set of integer points in Rk−1 i. p. 1

Where the paper says it

, q),(q, q, . Let Vk,q be the set of integer points in Rk,q, i.

e. Vkk = [v = (v1, v2) ∈ Z 2: 0 ≤ vi ≤ vi+1 ≤ q). The simplex-lattice hypergraph is a k-uniform hypergraph Hk,q whose vertex set is Vkk and whose set of hyperedges Ekk is given with Ekk = F(v): v ∈ Vkk−1, where F(v) = [v, v + ek−1, v + ek−1 + ek−2,. p. 1
Where the paper says it

, vk−1) ∈ Z k−1 : 0 ≤ vi ≤ vi+1 ≤ q}. The simplex-lattice hypergraph is a k-uniform hypergraph Hk,q whose vertex set is Vk,q and whose set of hyperedges Ek,q is given with Ek,q = {F(v) : v ∈ Vk,q−1}, where F(v) = {v, v + ek−1, v + ek−1 + ek−2, .

.., v + ek-1 + ek-2 + · · ·+e1]. The hyperedges of the simplex-lattice hypergraph Hk,q correspond with the certain cells of the edgewise subdivision of the simplex Rk,q. p. 1
Where the paper says it

, v + ek−1 + ek−2 + · · · + e1}. The hyperedges of the simplex-lattice hypergraph Hk,q correspond with the certain cells of the edgewise subdivision of the simplex Rk,q.

The facets (maximal cells) of the triangulation are indexed with pairs (v, π) where v ∈ Vkk−1 and π ∈ Sk−1 is consistent with v. p. 1
Where the paper says it

The edgewise subdivision of Rk,q is its triangulation whose vertex set is Vk,q. The facets (maximal cells) of the triangulation are indexed with pairs (v, π) where v ∈ Vk,q−1 and π ∈ Sk−1 is consistent with v.

A permutation π ∈ Sk−1 is consistent with v if i appears before i+1 in π whenever vi = vi+1. p. 1
Where the paper says it

The facets (maximal cells) of the triangulation are indexed with pairs (v, π) where v ∈ Vk,q−1 and π ∈ Sk−1 is consistent with v. A permutation π ∈ Sk−1 is consistent with v if i appears before i+1 in π whenever vi = vi+1.

For each v ∈ Vkk−1 and each π ∈ Sk−-1 which is consistent with v the convex hull of the set F(v, π) = [v, v + eπ(k-1), v + eπ(k-1) + eπ(k-2),. p. 1
Where the paper says it

A permutation π ∈ Sk−1 is consistent with v if i appears before i+1 in π whenever vi = vi+1. For each v ∈ Vk,q−1 and each π ∈ Sk−1 which is consistent with v the convex hull of the set F(v, π) = {v, v+eπ(k−1), v+eπ(k−1)+eπ(k−2), .

.., v + eπ(k-1) + eπ(k-2) + · · ·+e1] is a facet of the triangulation. p. 1
Where the paper says it

For each v ∈ Vk,q−1 and each π ∈ Sk−1 which is consistent with v the convex hull of the set F(v, π) = {v, v+eπ(k−1), v+eπ(k−1)+eπ(k−2), . , v+eπ(k−1)+eπ(k−2)+· · ·+eπ(1)} is a facet of the triangulation.

More details about the edgewise subdivision of a simplex can be found in [1]. p. 1
Where the paper says it

, v+eπ(k−1)+eπ(k−2)+· · ·+eπ(1)} is a facet of the triangulation. More details about the edgewise subdivision of a simplex can be found in [1].

We see that each hyperedge F(v) in Ekk is equal to F(v, Id(∈ Sk−1)> Extending this correspondence we define the π-simplex-lattice hypergraph. p. 1
Where the paper says it

We see that each hyperedge F(v) in Ek,q is equal to F(v, Id(∈ Sk−1)). Extending this correspondence we define the π-simplex-lattice hypergraph.

The π-simplex lattice hypergraph is a k-uniform hypergraph Hπk,q (π ∈ Sk−1) whose set of hyperedges Eπk,q is given with Eπk,q = F(v, π): v ∈ Vkk−1, π is consistent with v. p. 1
Where the paper says it

Extending this correspondence we define the π-simplex-lattice hypergraph. The π-simplex lattice hypergraph is a k-uniform hypergraph Hπ k,q (π ∈ Sk−1) whose set of hyperedges E π k,q is given with E π k,q = {F(v, π) : v ∈ Vk,q−1, π is consistent with v}.

The Sperner-admissible labeling of the vertices Vkk is a mapping l: Vkk → [k] such that vi > vi−1 whenever l(v) = i. p. 1
Where the paper says it

The π-simplex lattice hypergraph is a k-uniform hypergraph Hπ k,q (π ∈ Sk−1) whose set of hyperedges E π k,q is given with E π k,q = {F(v, π) : v ∈ Vk,q−1, π is consistent with v}. The Sperner-admissible labeling of the vertices Vk,q is a mapping ℓ : Vk,q → [k] such that vi > vi−1 whenever ℓ(v) = i.

Here we introduce the convention that v0 = 0 and vk = q. p. 1
Where the paper says it

The Sperner-admissible labeling of the vertices Vk,q is a mapping ℓ : Vk,q → [k] such that vi > vi−1 whenever ℓ(v) = i. Here we introduce the convention that v0 = 0 and vk = q.

--- Page 3 ---

Definition 1. For each v ∈ Vkk we define r(v) and i(v) in the following way: r(v) = max[t − vt: t ∈ [0, k], i(v) = min[t ∈ [0, k]: t − vt = r(v)]. p. 2

Where the paper says it

3 The labeling Definition 1. For each v ∈ Vk,q we define r(v) and i(v) in the following way: r(v) = max{t − vt : t ∈ [0, k]}, i(v) = min{t ∈ [0, k] : t − vt = r(v)}.

Recall that v0 = 0 and vk = q. p. 2
Where the paper says it

For each v ∈ Vk,q we define r(v) and i(v) in the following way: r(v) = max{t − vt : t ∈ [0, k]}, i(v) = min{t ∈ [0, k] : t − vt = r(v)}. Recall that v0 = 0 and vk = q.

We can immediately see that r(v) ≥ v0 − 0 = 0 and that i(v) = 0 if r(v) = 0. p. 2
Where the paper says it

Recall that v0 = 0 and vk = q. We can immediately see that r(v) ≥ v0 − 0 = 0 and that i(v) = 0 if r(v) = 0.

Definition 2. We consider the mapping l: Vkk → [k] defined with l(v) = i(v) + 1. p. 2
Where the paper says it

Definition 2. We consider the mapping ℓ : Vk,q → [k] defined with ℓ(v) = i(v) + 1.

--- Page 4 ---

Proposition 1. For q > k, the mapping l is well-defined Sperner-admissible labeling of Vkk. p. 2

Where the paper says it

Proposition 1. For q > k, the mapping ℓ is well-defined Sperner-admissible labeling of Vk,q.

Proof. Let v ∈ Vkk and i = i(v). p. 0
Where the paper says it

2 Preliminaries We review basic definitions following [2]. Let k ≥ 3 and q ≥ 1 throughout the paper.

We first prove that l(v) = i + 1 ∈ [k]. p. 2
Where the paper says it

Let v ∈ Vk,q and i = i(v). We first prove that l(v) = i + 1 ∈ [k].

Since q > k we have k − vk = k − q < 0, hence i < k. p. 2
Where the paper says it

We first prove that l(v) = i + 1 ∈ [k]. Since q > k we have k − vk = k − q < 0, hence i < k.

Now we prove that vi < vi+1. p. 2
Where the paper says it

Since q > k we have k − vk = k − q < 0, hence i < k. Now we prove that vi < vi+1.

By the definition of i(v) we have that i − vi ≥ i + 1 - vi+1, hence vi+1 ≥ vi + 1. p. 2
Where the paper says it

Now we prove that vi < vi+1. By the definition of i(v) we have that i − vi ≥ i + 1 − vi+1, hence vi+1 ≥ vi + 1.

--- Page 5 ---

Theorem 1. For q > k and for the Sperner-admissible labeling l each hyperedge of Hk,q uses at most 2 colors. p. 0

Where the paper says it

A labeling of the Simplex-Lattice Hypergraph with at most 2 colors on each hyperedge Ognjen Papaz∗ Duˇsko Joji´c† Abstract This paper provides a positive answer to the question of Mirzakhani and Vondrak from [2] that asks if there is a Sperner-admissible labeling of the simplex-lattice hypergraph such that each hyperedge uses at most 2 colors. 1 Introduction In ([2], section 4) the authors proved that for k ≥ 4 and q ≥ k 2 , there is a Sperner-admissible labeling of the simplex-lattice hypergraph Hk,q such that every hyperedge of Hk,q contains at most 4 colors.

Proof. Let F(v) be a hyperedge of Hk,q and let i = i(v) and r = r(v). We denote the vertices of F(v) in the following way v = v, v (k−1) = v+ek−1, v (k−2) = v+ek-1 + ek-2,. p. 2
Where the paper says it

Let F(v) be a hyperedge of Hk,q and let i = i(v) and r = r(v). We denote the vertices of F(v) in the following way v = v, v (k−1) = v+ek−1, v (k−2) = v+ek−1+ek−2, .

.., v (1) = v+ek-1 + ek-2 + · · ·+e1. Note that the vertices vk − 1, vk − 2,. p. 2
Where the paper says it

, v (1) = v+ek−1+ek−2+· · ·+e1. Note that the vertices v (k−1) , v (k−2) , .

.., v(1) are obtained by increasing coordinates of v, one by one, from behind. p. 2
Where the paper says it

Note that the vertices v (k−1) , v (k−2) , . , v (1) are obtained by increasing coordinates of v, one by one, from behind.

Let r = 0, then i = 0. p. 0
Where the paper says it

2 Preliminaries We review basic definitions following [2]. Let k ≥ 3 and q ≥ 1 throughout the paper.

Since increasing the coordinates of v doesn’t increase r(v) we have that 0 = r(v (k−1)) = r(v (k−2)) =. p. 2
Where the paper says it

Let r = 0, then i = 0. Since increasing the coordinates of v doesn’t increase r(v) we have that 0 = r(v (k−1)) = r(v (k−2)) = .

.. = r(v (1)).

--- Page 6 ---

Let’s take a closer look at the vertex v(i). By the definition of r(v) we have i − 1 − v(i)i−1 = i − 1 - vi−1 ≤ r(v (i). p. 2

Where the paper says it

3 The labeling Definition 1. For each v ∈ Vk,q we define r(v) and i(v) in the following way: r(v) = max{t − vt : t ∈ [0, k]}, i(v) = min{t ∈ [0, k] : t − vt = r(v)}.

From here we see that vi < vi−1 + 1, hence vi = vi−1 and r(v (i) = r − 1. p. 3
Where the paper says it

By the definition of r(v) we have i − 1 − v (i) i−1 = i − 1 − vi−1 ≤ r(v (i) ) < r = i − vi . From here we see that vi < vi−1 + 1, hence vi = vi−1 and r(v (i) ) = r − 1.

Let i′ = i(v(i)), this is the smallest index t ∈ [0, k] such that t − v(i′)t = r-1. p. 3
Where the paper says it

From here we see that vi < vi−1 + 1, hence vi = vi−1 and r(v (i) ) = r − 1. Let i ′ = i(v (i) ), this is the smallest index t ∈ [0, k] such that t−vt = r−1.

We have r - 1 = r(v(i)) = r(v(i−1)) =... = r(v (i′+1)), i' = i(v(i)) = i(v(i−1)) = and i + 1 = l(v) = l(v (k−1)) =... = l(v (i′+1)> If r − 1 > 0 then i' > 0. When we increase the coordinates vi′, vi+1,. p. 2
Where the paper says it

Let r = 0, then i = 0. Since increasing the coordinates of v doesn’t increase r(v) we have that 0 = r(v (k−1)) = r(v (k−2)) = .

., vk−1 of v and obtain v(i′) we can see that r(v(i′)) = r − 1 and that i becomes the smallest index t ∈ [0, k] such that t − v(i′)t = r-1. p. 3
Where the paper says it

When we increase the coordinates vi ′, vi ′+1, . , vk−1 of v and obtain v (i ′ ) we can see that r(v (i ′ ) ) = r − 1 and that i becomes the smallest index t ∈ [0, k] such that t − v (i ′ ) t = r − 1.

Thus, r - 1 = r(v(i')) = r(v(i′−1)) =... = r(v (1)) and i + 1 = l(v) = l(v (i′−1)) =.

--- Page 7 ---

Now we consider if there exist a Sperner-admissible labeling of Vk,q such that each hyperedge of Hπk,q (π ∈ Sk−1) uses at most 2 colors. Analyzing the proof of the previous theorem we see that the labeling l works because among all coordinates vt of v such that t−vt = r(v) the coordinate vi(v) is the last coordinate that increases when obtaining the vertices of the hyperedge F(v, π)> In a hyperedge F(v, π) = [v, v+eπ(k-1), v+eπ(k-1)+eπ(k-2),. p. 4

Where the paper says it

Analyzing the proof of the previous theorem we see that the labeling ℓ works because among all coordinates vt of v such that t−vt = r(v) the coordinate vi(v) is the last coordinate that increases when obtaining the vertices of the hyperedge F(v). In a hyperedge F(v, π) = {v, v+eπ(k−1), v+eπ(k−1)+eπ(k−2), .

.., v+eπ(k-1)+eπ(k-2)+· · ·+e1] of Hπk,q, the permutation π prescribes the order in which the coordinates of v are increasing. p. 4
Where the paper says it

In a hyperedge F(v, π) = {v, v+eπ(k−1), v+eπ(k−1)+eπ(k−2), . , v+eπ(k−1)+eπ(k−2)+· · ·+eπ(1)} of Hπ k,q, the permutation π prescribes the order in which the coordinates of v are increasing.

Thus, we can modify the definitions of i(v) and l(v) and show that each hyperedge of Hπk,q will use at most two colors by the same arguments as for l. p. 4
Where the paper says it

, v+eπ(k−1)+eπ(k−2)+· · ·+eπ(1)} of Hπ k,q, the permutation π prescribes the order in which the coordinates of v are increasing. Thus, we can modify the definitions of i(v) and ℓ accordingly and show that each hyperedge of Hπ k,q will use at most two colors by the same arguments as for ℓ.

--- Page 8 ---

Definition 3. For π ∈ Sk−1, let π = 0πk. For each v ∈ Vkk we define iπ(v) with iπ(v) = min[t ∈ [0, k]: π(t) − vπ(t) = r(v)] and lπ(v) with lπ(v) = iπ(v) + 1. p. 4

Where the paper says it

For π ∈ Sk−1, let π = 0πk. For each v ∈ Vk,q we define i π (v) with i π (v) = min{t ∈ [0, k] : π(t) − vπ(t) = r(v)} and ℓ π (v) with ℓ π (v) = i π (v) + 1.

--- Page 9 ---

References [1] Herbert Edelsbrunner and Daniel R. Grayson. Edgewise subdivision of a simplex. p. 1

Where the paper says it

, v + ek−1 + ek−2 + · · · + e1}. The hyperedges of the simplex-lattice hypergraph Hk,q correspond with the certain cells of the edgewise subdivision of the simplex Rk,q.

Discrete and Computation Geometry, 24(4):707-719,2000 [2] Maryam Mirzakhani and Jan Vondr´ak. p. 4
Where the paper says it

Edgewise subdivision of a simplex. Discrete and Computation Geometry, 24(4):707-719,2000 [2] Maryam Mirzakhani and Jan Vondr´ak.

Sperner’s colorings, hypergraph labeling problems and fair division. p. 4
Where the paper says it

Discrete and Computation Geometry, 24(4):707-719,2000 [2] Maryam Mirzakhani and Jan Vondr´ak. Sperner’s colorings, hypergraph labeling problems and fair division.

Proc. of ACM-SIAM SODA, 873–886, 2015 [3] The paper is available as arXiv:2511. p. 4
Where the paper says it

Sperner’s colorings, hypergraph labeling problems and fair division. of ACM-SIAM SODA, 873– 886, 2015.

03036v1 [math.CO] 4 Nov 2025.

--- Page 9 ---

The paper is available as arXiv:2511.03036v1 [math.CO] 4 Nov 2025. The paper is available as arXiv:2511.03036v1 [math.CO] 4 Nov 2025.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Better fair division algorithms can be developed for resource allocation problems by utilizing Sperner-admissible colorings of simplex-lattice hypergraphs with at most two colors on each hyperedge, as suggested by Theorem 2.

  2. AI systems can achieve more efficient and equitable division of a set of resources represented by the vertices Vk,q if the labeling l pi is used to assign values to these vertices based on their position within specific hyperedges F(v, pi).

  3. The improved system can handle complex geometric constraints in resource allocation tasks where the constraints are modeled by the structure of Hpi k,q, ensuring that divisions adhere to fairness criteria related to permutations pi.

Abstract

Mirzakhani and Vondrák asked whether the simplex-lattice hypergraph admits a Sperner-admissible labeling in which every hyperedge receives at most two colors. We answer this question affirmatively by introducing the dominant labeling, in which every lattice point is labeled by its unique dominant index. In their hybrid model of fair division, this yields preference functions under which at most two players are nearly satisfied. We determine the number of vertices of each color and the number of hyperedges using a given pair of colors; these counts are expressed through the entries of Catalan's triangle. We also characterize the color sets of hyperedges of the other hypergraphs that arise from the edgewise triangulation of the dilations of the standard unit simplex.

Related papers