The shuffle conjecture

van Willigenburg, Stephanie

doi:10.1090/bull/1672

The shuffle conjecture

Author: Stephanie van Willigenburg
Journal: Bull. Amer. Math. Soc. 57 (2020), 77-89
MSC (2010): Primary 05E05, 05E10, 20C30
DOI: https://doi.org/10.1090/bull/1672
Published electronically: July 1, 2019
MathSciNet review: 4037408
Full-text PDF Free Access
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

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 https://doi.org/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
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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1023/A%3A1022476211638

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 https://doi.org/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

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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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

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 https://doi.org/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, American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. 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

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 https://doi.org/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 https://doi.org/10.1112/plms/s2-28.1.255