The shuffle conjecture

van Willigenburg, Stephanie

doi:10.1090/bull/1672

The shuffle conjecture
HTML articles powered by AMS MathViewer

by Stephanie van Willigenburg HTML | PDF

Bull. Amer. Math. Soc. 57 (2020), 77-89 Request permission

Abstract:

Walks in the plane taking unit-length steps north and east from $(0,0)$ to $(n,n)$ never dropping below $y=x$ and parking cars subject to preferences are two intriguing ingredients in a formula conjectured in 2005, now famously known as the shuffle conjecture.

Here we describe the combinatorial tools needed to state the conjecture. We also give key parts and people in its history, including its eventual algebraic solution by Carlsson and Mellit, which was published in the Journal of the American Mathematical Society in 2018. Finally, we conclude with some remaining open problems.

References

Marcelo Aguiar, Nantel Bergeron, and Frank Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math. 142 (2006), no. 1, 1–30. MR 2196760, DOI 10.1112/S0010437X0500165X
Sami Assaf, Toward the Schur expansion of Macdonald polynomials, Electron. J. Combin. 25 (2018), no. 2, Paper No. 2.44, 20. MR 3814278
François Bergeron, Algebraic combinatorics and coinvariant spaces, CMS Treatises in Mathematics, Canadian Mathematical Society, Ottawa, ON; A K Peters, Ltd., Wellesley, MA, 2009. MR 2538310, DOI 10.1201/b10583
F. Bergeron and A. M. Garsia, Science fiction and Macdonald’s polynomials, Algebraic methods and $q$-special functions (Montréal, QC, 1996) CRM Proc. Lecture Notes, vol. 22, Amer. Math. Soc., Providence, RI, 1999, pp. 1–52. MR 1726826, DOI 10.1090/crmp/022/01
E. Carlsson and A. Mellit, A proof of the shuffle conjecture, arXiv:1508.06239v1 (2015).
Erik Carlsson and Anton Mellit, A proof of the shuffle conjecture, J. Amer. Math. Soc. 31 (2018), no. 3, 661–697. MR 3787405, DOI 10.1090/jams/893
A. Cauchy, Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu’elles renferment, J. Éc. Polytech. Oeuvres, Series 2, Volume 1 (1815), 91–169.
Robert Cori and Dominique Rossin, On the sandpile group of dual graphs, European J. Combin. 21 (2000), no. 4, 447–459. MR 1756151, DOI 10.1006/eujc.1999.0366
Susanna Fishel, Statistics for special $q,t$-Kostka polynomials, Proc. Amer. Math. Soc. 123 (1995), no. 10, 2961–2969. MR 1264811, DOI 10.1090/S0002-9939-1995-1264811-3
Adriano M. Garsia and Mark Haiman, A graded representation model for Macdonald’s polynomials, Proc. Nat. Acad. Sci. U.S.A. 90 (1993), no. 8, 3607–3610. MR 1214091, DOI 10.1073/pnas.90.8.3607
A. M. Garsia and M. Haiman, A remarkable $q,t$-Catalan sequence and $q$-Lagrange inversion, J. Algebraic Combin. 5 (1996), no. 3, 191–244. MR 1394305, DOI 10.1023/A:1022476211638
Ira M. Gessel, Multipartite $P$-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983) Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289–317. MR 777705, DOI 10.1090/conm/034/777705
A. Girard, Invention nouvelle en l’algèbre, Amsterdam (1629).
James Haglund, The $q$,$t$-Catalan numbers and the space of diagonal harmonics, University Lecture Series, vol. 41, American Mathematical Society, Providence, RI, 2008. With an appendix on the combinatorics of Macdonald polynomials. MR 2371044, DOI 10.1007/s10711-008-9270-0
J. Haglund, M. Haiman, N. Loehr, J. B. Remmel, and A. Ulyanov, A combinatorial formula for the character of the diagonal coinvariants, Duke Math. J. 126 (2005), no. 2, 195–232. MR 2115257, DOI 10.1215/S0012-7094-04-12621-1
J. Haglund, J. Morse, and M. Zabrocki, A compositional shuffle conjecture specifying touch points of the Dyck path, Canad. J. Math. 64 (2012), no. 4, 822–844. MR 2957232, DOI 10.4153/CJM-2011-078-4
J. Haglund and G. Xin, Lecture notes on the Carlsson-Mellit proof of the shuffle conjecture, arXiv:1705.11064v1 (2017).
Mark Haiman, Hilbert schemes, polygraphs and the Macdonald positivity conjecture, J. Amer. Math. Soc. 14 (2001), no. 4, 941–1006. MR 1839919, DOI 10.1090/S0894-0347-01-00373-3
Mark Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002), no. 2, 371–407. MR 1918676, DOI 10.1007/s002220200219
Patricia Hersh and Samuel K. Hsiao, Random walks on quasisymmetric functions, Adv. Math. 222 (2009), no. 3, 782–808. MR 2553370, DOI 10.1016/j.aim.2009.05.014
A. Hicks, Combinatorics of the diagonal harmonics, Recent Trends in Algebraic Combinatorics, Association for Women in Mathematics, Series 16 (2019), 159–188.
Kevin W. J. Kadell, A proof of some $q$-analogues of Selberg’s integral for $k=1$, SIAM J. Math. Anal. 19 (1988), no. 4, 944–968. MR 946654, DOI 10.1137/0519066
A. Konheim and B. Weiss, An occupancy discipline and applications, SIAM J. Appl. Math. 14 (1966), 1266–1274.
Nicholas A. Loehr and Gregory S. Warrington, Square $q,t$-lattice paths and $\nabla (p_n)$, Trans. Amer. Math. Soc. 359 (2007), no. 2, 649–669. MR 2255191, DOI 10.1090/S0002-9947-06-04044-X
Nicholas A. Loehr and Gregory S. Warrington, Nested quantum Dyck paths and $\nabla (s_\lambda )$, Int. Math. Res. Not. IMRN 5 (2008), Art. ID rnm 157, 29. MR 2418288, DOI 10.1093/imrn/rnm157
I. Macdonald, A new class of symmetric functions, Sém. Lothar. Combin. 20 (1988), 131–171.
Ronald Pyke, The supremum and infimum of the Poisson process, Ann. Math. Statist. 30 (1959), 568–576. MR 107315, DOI 10.1214/aoms/1177706269
Bruce E. Sagan, The symmetric group, 2nd ed., Graduate Texts in Mathematics, vol. 203, Springer-Verlag, New York, 2001. Representations, combinatorial algorithms, and symmetric functions. MR 1824028, DOI 10.1007/978-1-4757-6804-6
I. Schur, Über eine Klasse von Matrizen, die sich einer gegebenen Matrix zuordnen lassen, Dissertation, Berlin (1901).
Emily Sergel, A proof of the square paths conjecture, J. Combin. Theory Ser. A 152 (2017), 363–379. MR 3682738, DOI 10.1016/j.jcta.2017.06.013
E. Sergel, A combinatorial model for $\nabla m_\mu$, arXiv:1804.06037v1 (2018).
Richard P. Stanley, Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, Providence, R.I., 1972. MR 0332509
Richard P. Stanley, Hyperplane arrangements, parking functions and tree inversions, Mathematical essays in honor of Gian-Carlo Rota (Cambridge, MA, 1996) Progr. Math., vol. 161, Birkhäuser Boston, Boston, MA, 1998, pp. 359–375. MR 1627378
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
John R. Stembridge, Some particular entries of the two-parameter Kostka matrix, Proc. Amer. Math. Soc. 121 (1994), no. 2, 367–373. MR 1182707, DOI 10.1090/S0002-9939-1994-1182707-1
Catherine H. Yan, Parking functions, Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015, pp. 835–893. MR 3409354
Alfred Young, On Quantitative Substitutional Analysis, Proc. London Math. Soc. (2) 28 (1928), no. 4, 255–292. MR 1575854, DOI 10.1112/plms/s2-28.1.255