Parallelogram polyominoes, partially labelled Dyck paths, and the Delta\n conjecture (FULL VERSION)

Michele D’Adderio, Alessandro Iraci

TL;DR

This paper connects combinatorial objects called parallelogram polyominoes and partially labeled Dyck paths to the celebrated Delta conjecture in algebraic combinatorics. The authors introduce new statistics on these objects and prove that they provide combinatorial interpretations for key symmetric functions, thus solving a long-standing problem in the field.

What Problem Does This Paper Address?

The Delta conjecture, a significant open problem in algebraic combinatorics, proposes a combinatorial interpretation for certain symmetric functions related to the representation theory of the symmetric group. Specifically, this paper tackles a part of the Delta conjecture concerning the symmetric function $\Delta_{h_m} e_{n+1}$ and its variants. Previous work had established interpretations for simpler cases, but a full combinatorial understanding for more general forms, particularly involving the coefficients $\langle \Delta_{h_m} e_{n+1}, s_{k+1,1^{n-k}} \rangle$ and $\langle \Delta_{e_{m+n-k-1}} e_{m+n}, h_m h_n \rangle$, remained elusive. This paper aims to provide these missing combinatorial interpretations using decorated parallelogram polyominoes and partially labeled Dyck paths.

Methods

The authors introduce and study new statistics—area, bounce, and dinv—on decorated parallelogram polyominoes. They then establish bijective connections between these polyominoes and decorated labeled Dyck paths. A key technique is the use of symmetric function identities and operators, particularly the nabla operator ($\nabla$) and the Delta operator ($\Delta$), which are standard tools in the study of symmetric functions and Macdonald polynomials. They leverage existing theorems and lemmas related to these operators and symmetric function bases (like Schur and elementary symmetric functions) to prove their results. The paper also introduces a new statistic, pmaj, on partially labeled Dyck paths, which is shown to be related to the bounce statistic.

Datasets

Not discussed in the paper. The paper deals with theoretical combinatorial objects and their properties, not empirical data or machine learning models.

Key Insights and Ideas

  • Bridging Combinatorial Worlds: The paper masterfully connects seemingly disparate combinatorial objects (parallelogram polyominoes, Dyck paths) with abstract algebraic structures (symmetric functions, Delta conjecture). This cross-pollination is a hallmark of progress in algebraic combinatorics.
  • New Statistics, New Interpretations: The introduction of decorated versions of area, bounce, and dinv statistics on parallelogram polyominoes, and the pmaj statistic on Dyck paths, provides the crucial combinatorial machinery to interpret complex symmetric functions.
  • Solving a Piece of the Delta Conjecture: The paper provides a complete combinatorial interpretation for specific coefficients related to the Delta conjecture, a significant step towards resolving this major open problem.
  • Bijective Proofs as the Core: The reliance on bijective correspondences is a powerful technique. Showing that different combinatorial objects count the same thing provides deep structural understanding and elegant proofs.
  • Recursive Structures: The use of recursions for enumerating these combinatorial objects is a standard but powerful approach, allowing for systematic computation and proof.

Key Results

  • The authors introduce and study statistics (area, bounce, dinv) on decorated parallelogram polyominoes and prove that their q,t-enumerators match specific symmetric functions, extending previous work.
  • A bijective connection is established between decorated parallelogram polyominoes and decorated labeled Dyck paths. This bijection allows them to prove a combinatorial interpretation for the coefficient $\langle \Delta_{e_{m+n-k-1}} e_{m+n}, h_m h_n \rangle$, a key part of the Delta conjecture.
  • A new statistic, pmaj, is defined on partially labeled Dyck paths, offering another conjectural combinatorial interpretation for related symmetric functions.
  • The paper provides explicit recursions for various q,t-enumerators of these combinatorial objects, which are crucial for their computation and analysis.

Limitations and Future Work

  • Conjectural Nature: While the paper proves several key results, it also presents conjectures (e.g., Conjecture 7.4 and Conjecture 8.3) that are supported by computer verification but not yet formally proven. These conjectures suggest further avenues for research.
  • Generalization: The paper focuses on specific forms of symmetric functions related to the Delta conjecture. Future work could explore extending these combinatorial interpretations to even more general symmetric functions or related conjectures.
  • Deeper Connections: The paper hints at deeper connections between different combinatorial objects and algebraic structures. Further exploration of these relationships could lead to new insights and broader theories.
  • Specific Statistics: The paper notes that a decorated version of the dinv statistic on parallelogram polyominoes is complex and not needed for their main results, suggesting that further investigation into its properties might be fruitful.

Summary updated

Abstract

We introduce area, bounce and dinv statistics on decorated parallelogram\npolyominoes, and prove that some of their q,t-enumerators match $\\langle\n\\Delta_{h_m} e_{n+1},s_{k+1,1^{n-k}}\\rangle$, extending in this way the work in\n(Aval et al. 2014). Also, we provide a bijective connection between decorated\nparallelogram polyominoes and decorated labelled Dyck paths, which allows us to\nprove the combinatorial interpretation of the coefficient $\\langle\n\\Delta_{e_{m+n-k-1}}'e_{m+n},h_m h_n\\rangle$ predicted by the Delta conjecture\nin (Haglund et al. 2015). Finally, we define a statistic pmaj on partially\nlabelled Dyck paths, which provides another conjectural combinatorial\ninterpretation of $\\Delta_{h_{\\ell}}\\Delta_{e_{n-k-1}}'e_n$, cf. (Haglund et\nal. 2015).\n This is the full version of (D'Adderio, Iraci 2017) arXiv:1711.03923.\n
BibTeX
@misc{dadderio2017parallelogram,
  author = {Michele D’Adderio and Alessandro Iraci},
  title = {{Parallelogram polyominoes, partially labelled Dyck paths, and the Delta\textbackslash\{\}n conjecture (FULL VERSION)}},
  year = {2017},
  eprint = {1711.03923},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.03923},
}
Figure