On a Question of Mirzakhani and Vondr'ak concerning Sperner Labelings of the Simplex-Lattice Hypergraph
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 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. Proposition 1. For q > k, the mapping ℓ is well-defined Sperner-admissible
labeling of Vk,q. 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).Where the paper says it
Where the paper says it
Where the paper says it
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 , q),(q, q, . Let Vk,q be the set of integer points in Rk,q, i. , 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. 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)). 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}.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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)}. Definition 2. p. 2 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)}. Proposition 1. For q > k, the mapping ℓ is well-defined Sperner-admissible
labeling of Vk,q. 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).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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). Let F(v) be a hyperedge of Hk,q and let i = i(v) and r = r(v). p. 2 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).Where the paper says it
Where the paper says it
Where the paper says it
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 For π ∈ Sk−1, let π = 0πk. p. 4 Definition 3. For π ∈ Sk−1, let π = 0πk. 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). , 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 ℓ.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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). ba
†Faculty of Science, University of Banja Luka, Bosnia and Herzegovina
dusko. org
1
arXiv:2511. ba
†Faculty of Science, University of Banja Luka, Bosnia and Herzegovina
dusko. org
1
arXiv:2511. org
1
arXiv:2511. 03036v1 [math. org
1
arXiv:2511. 03036v1 [math. org
1
arXiv:2511. 03036v1 [math. org
1
arXiv:2511. 03036v1 [math. 03036v1 [math. CO] 4 Nov 2025 03036v1 [math. CO] 4 Nov 2025 03036v1 [math. CO] 4 Nov 2025 03036v1 [math. CO] 4 Nov 2025Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 , q),(q, q, . Let Vk,q be the set of integer points in Rk,q, i. , 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. 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. 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. 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), . 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. , 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 Ek,q is equal to F(v, Id(∈ Sk−1)). Extending this correspondence we define the π-simplex-lattice hypergraph. 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 π-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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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)}. 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. 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 ℓ : Vk,q → [k] defined with
ℓ(v) = i(v) + 1.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- Page 4 ---
Proposition 1. For q > k, the mapping l is well-defined Sperner-admissible labeling of Vkk. p. 2 Proposition 1. For q > k, the mapping ℓ is well-defined Sperner-admissible
labeling of Vk,q. 2 Preliminaries
We review basic definitions following [2]. Let k ≥ 3 and q ≥ 1 throughout the paper. Let v ∈ Vk,q and i = i(v). We first prove that l(v) = i + 1 ∈ [k]. We first prove that l(v) = i + 1 ∈ [k]. Since q > k we have k − vk = k − q < 0, hence i < k. Since q > k we have k − vk = k − q < 0, hence i < k. Now we prove that
vi < vi+1. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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. 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 v
(k−1)
, v
(k−2)
, . Note that the vertices v
(k−1)
, v
(k−2)
, . , v
(1) are obtained by increasing coordinates of v, one by one, from behind. 2 Preliminaries
We review basic definitions following [2]. Let k ≥ 3 and q ≥ 1 throughout the paper. 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)) = .Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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)}. 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. 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. 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)) = . 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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), . 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. , 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 ℓ.Where the paper says it
Where the paper says it
Where the paper says it
--- 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 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.Where the paper says it
--- Page 9 ---
References [1] Herbert Edelsbrunner and Daniel R. Grayson. Edgewise subdivision of a simplex. p. 1 , 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. Edgewise subdivision of
a simplex. Discrete and Computation Geometry, 24(4):707-719,2000
[2] Maryam Mirzakhani and Jan Vondr´ak. 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. Sperner’s colorings, hypergraph
labeling problems and fair division. of ACM-SIAM SODA, 873–
886, 2015.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
--- 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
-
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.
-
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).
-
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality