no. 13 · Wednesday 11 November 2026
On a Question of Mirzakhani and Vondrák concerning Sperner Labelings of the Simplex-Lattice Hypergraph
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