Paperlane

no. 13 · Wednesday 11 November 2026

On a Question of Mirzakhani and Vondrák concerning Sperner Labelings of the Simplex-Lattice Hypergraph

Ognjen Papaz and Duško Jojić

math.CO · v2

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 \emph{dominant labeling}, in which every lattice point is labeled by its unique \emph{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.

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
fields
Combinatorics
pdf ↗ page arXiv:2511.03036 ↗