Celebratio Mathematica

[1] E. S. Mahmoodian and M. Mirzakhani: “Decomposition of complete tripartite graphs into 5-cycles,” pp. 235–241 in Combinatorics advances: Papers presented at the 25th annual Iranian mathematics conference (Tehran, 28–31 March 1994). Edited by C. J. Colbourn and E. S. Mahmoodian. Mathematics and its Applications 329. Kluwer Academic Publishers (Dordrecht), 1995. MR 1366852 Zbl 0837.05088 incollection

A result of Sotteau on the necessary and sufficient conditions for decomposing the complete bipartite graphs into even cycles has been shown in many occasions, that it is a very important tool in the theory of graph decomposition into even cycles. In order to have similar tools in the case of odd cycle decomposition, obviously bipartite graphs are not suitable to be considered. Searching for such tools, we have considered decomposition of complete tripartite graphs, \( K_{r,s,t} \), into 5-cycles. There are some necessary conditions that we have shown their sufficiency in the case of \( r = t \), and some other cases. Our conjecture is that these conditions are always sufficient.

Ebadollah Sayed Mahmoodian	Related
Charles Joseph Colbourn	Related

[2] M. Mirzakhani: “A small non-4-choosable planar graph,” Bull. Inst. Combin. Appl. 17 (1996), pp. 15–18. MR 1386951 Zbl 0860.05029 article

[3] M. Mirzakhani: “A simple proof of a theorem of Schur,” Am. Math. Mon. 105 : 3 (March 1998), pp. 260–262. MR 1615548 Zbl 0916.15004 article

[4] M. Mirzakhani: Simple geodesics on hyperbolic surfaces and the volume of the moduli space of curves. Ph.D. thesis, Harvard University, 2004. Advised by C. T. McMullen. MR 2705986 phdthesis

[5] M. Mirzakhani: “Weil–Petersson volumes and intersection theory on the moduli space of curves,” J. Am. Math. Soc. 20 : 1 (2007), pp. 1–23. MR 2257394 Zbl 1120.32008 article

In this paper, we establish a relationship between the Weil–Petersson volume \( V_{g,n}(b) \) of the moduli space \( \mathcal{M}_{g,n}(b) \) of hyperbolic Riemann surfaces with geodesic boundary components of lengths \( b_1,\dots \), \( b_n \), and the intersection numbers of tautological classes on the moduli space \( \overline{\mathcal{M}}_{g,n} \) of stable curves. As a result, by using the recursive formula for \( V_{g,n}(b) \) obtained in the author’s “Simple geodesics and Weil–Petersson volumes of moduli spaces of bordered Riemann surfaces”, preprint, 2003, we derive a new proof of the Virasoro constraints for a point. This result is equivalent to the Witten–Kontsevich formula.

[6] M. Mirzakhani: “Simple geodesics and Weil–Petersson volumes of moduli spaces of bordered Riemann surfaces,” Invent. Math. 167 : 1 (2007), pp. 179–222. MR 2264808 Zbl 1125.30039 article

In this paper we investigate the Weil–Petersson volume of the moduli space of curves with marked points. We develop a method for integrating geometric functions over the moduli space of curves, and obtain an effective recursive formula for the volume \( V_{g,n}(L_1,\dots \), \( L_n) \) of the moduli space \( \mathcal{M}_{g,n}(L_1,\dots \), \( L_n) \) of hyperbolic Riemann surfaces of genus \( g \) with \( n \) geodesic boundary components. We show that \( V_{g,n}(L) \) is a polynomial whose coefficients are rational multiples of powers of \( \pi \). The constant term of the polynomial \( V_{g,n}(L) \) is the Weil–Petersson volume of the moduli spacemof closed surfaces of genus \( g \) with \( n \) marked points.

[7] M. Mirzakhani: “Random hyperbolic surfaces and measured laminations,” pp. 179–198 in In the tradition of Ahlfors–Bers, IV (Ann Arbor, MI, 19–22 May 2005). Edited by D. Canary, J. Gilman, J. Heinonen, and H. Masur. Contemporary Mathematics 432. American Mathematical Society (Providence, RI), 2007. Available open access here. MR 2342816 Zbl 1129.32011 incollection

Richard Douglas Canary	Related
Juha Heinonen	Related
Howard Masur	Related
Jane Piore Gilman	Related

[8] M. Mirzakhani: “Growth of the number of simple closed geodesics on hyperbolic surfaces,” Ann. Math. (2) 168 : 1 (2008), pp. 97–125. MR 2415399 Zbl 1177.37036 article

[9] M. Mirzakhani: “Ergodic theory of the earthquake flow,” Int. Math. Res. Not. 2008 (2008). MR 2416997 Zbl 1189.30087 article

[10] E. Lindenstrauss and M. Mirzakhani: “Ergodic theory of the space of measured laminations,” Int. Math. Res. Not. 2008 (2008). MR 2424174 Zbl 1160.37006 article

[11] M. Mirzakhani: “On Weil–Petersson volumes and geometry of random hyperbolic surfaces,” pp. 1126–1145 in Proceedings of the International Congress of Mathematicians (Hyderabad, India, 19–27 August 2010), vol. 2. Edited by R. Bhatia, A. Pal, G. Rangarajan, V. Srinivas, and M. Vanninathan. Hindustan Book Agency (New Delhi), 2010. MR 2827834 Zbl 1239.32013 incollection

Vasudevan Srinivas	Related
Rajendra Bhatia	Related
Muthusamy Vanninathan	Related
Govindan Rangarajan	Related
Arup Kumar Pal	Related

[12] A. Eskin and M. Mirzakhani: “Counting closed geodesics in moduli space,” J. Mod. Dyn. 5 : 1 (2011), pp. 71–105. MR 2787598 Zbl 1219.37006 article

[13] J. Athreya, A. Bufetov, A. Eskin, and M. Mirzakhani: “Lattice point asymptotics and volume growth on Teichmüller space,” Duke Math. J. 161 : 6 (2012), pp. 1055–1111. MR 2913101 Zbl 1246.37009 article

Alex Eskin	Related
Jayadev Siddhanta Athreya	Related
Alexander Igorevich Bufetov	Related

[14] M. Mirzakhani: “Growth of Weil–Petersson volumes and random hyperbolic surfaces of large genus,” J. Diff. Geom. 94 : 2 (2013), pp. 267–300. MR 3080483 Zbl 1270.30014 article

[15] M. Mirzakhani and P. Zograf: “Towards large genus asymptotics of intersection numbers on moduli spaces of curves,” Geom. Funct. Anal. 25 : 4 (2015), pp. 1258–1289. MR 3385633 Zbl 1327.14136 article

[16] A. Eskin, M. Mirzakhani, and A. Mohammadi: “Isolation, equidistribution, and orbit closures for the \( \mathrm{SL}(2,\mathbb{R}) \) action on moduli space,” Ann. Math. (2) 182 : 2 (2015), pp. 673–721. MR 3418528 Zbl 1357.37040 article

Alex Eskin	Related
Amir Mohammadi	Related

[17] M. Mirzakhani and J. Vondrák: “Sperner’s colorings, hypergraph labeling problems and fair division,” pp. 873–886 in Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms (San Diego, CA, 4–6 January 2015). Edited by P. Indyk. SIAM (Philadelphia), 2015. MR 3451084 Zbl 1371.05094 incollection

We prove three results about colorings of the simplex reminiscent of Sperner’s Lemma, with applications in hardness of approximation and fair division.

First, we prove a coloring lemma conjectured by Ene and Vondrák [2014]: Let \begin{align*} V_{k,q} &= \bigl\{ \mathbf{v}\in \mathbb{Z}_+^k: \textstyle\sum_{i=1}^k v_i = q \bigr\} \quad\text{and}\\ E_{k,q} &= \bigl\{ \{\mathbf{a} + \mathbf{e}_1,\mathbf{a} + \mathbf{e}_2,\dots, \mathbf{a} + \mathbf{e}_k\}\,:\,\mathbf{a}\in \mathbb{Z}_+^k, \textstyle\sum_{i=1}^k a_i = q-1 \bigr\} . \end{align*} Then for every Sperner-admissible labeling (\( \ell: V_{k,q} \to [k] \) such that \( v_{\ell(\mathbf{v})} > 0 \) for each \( \mathbf{v}\in V_{k,q} \)), there are at least \( {q+k-3\choose k-2} \) non-monochromatic hyperedges in \( E_{k,q} \). This implies an optimal Unique-Games hardness of \( (k{-}1{-}\epsilon) \)-approximation for the Hypergraph Labeling with Color Lists problem [Chekuri and Ene 2011]: Given a \( k \)-uniform hypergraph \( H = (V,E) \) with color lists \( L(v)\subseteq [k] \), \( \forall v\in V \), find a labeling \( \ell(v)\in L(v) \) that minimizes the number of non-monochromatic hyperedges. We also show that a \( (k{-}1) \)-approximation can be achieved.

Second, we show that in contrast to Sperner’s Lemma, there is a Sperner-admissible labeling of \( V_{k,q} \) such that every hyperedge in \( E_{k,q} \) contains at most 4 colors. We present an interpretation of this statement in the context of fair division: There is a preference function on \[ \Delta_{k,q} = \bigl\{ \mathbf{x}\in\mathbb{R}_+^k: \textstyle\sum_{i=}^k x_i = q \bigr\} \] such that for any division of \( q \) units of a resource, \( (x_1,x_2,\dots \), \( x_k)\in\Delta_{k,q} \) such that \[ \textstyle\sum_{i=1}^k \lfloor x_i \rfloor = q-1 ,\] at most 4 players out of \( k \) are satisfied.

Third, we prove that there are subdivisions of the simplex with a fractional labeling (analogous to a fractional solution for Min-CSP problems) such that every hyperedge in the subdivision uses only labelings with 1 or 2 colors. This means that a natural LP cannot distinguish instances of Hypergraph Labeling with Color Lists that can be labeled so that every hyperedge uses at most 2 colors, and instances that must have a rainbow hyperedge. We prove that this problem is indeed NP-hard for \( k = 3 \).

Piotr Indyk	Related
Jan Vondrák	Related

[18] M. Mirzakhani and A. Wright: “The boundary of an affine invariant submanifold,” Invent. Math. 209 : 3 (2017), pp. 927–984. MR 3681397 Zbl 06786974 article

Maryam Mirzakhani

Complete Bibliography