The New dinv is Not So New

Michele D’Adderio, Alessandro IraciThe Electronic Journal of Combinatorics 2019 · DOI

TL;DR

This paper demystifies a recently introduced statistic called ndinv by showing it's equivalent to a well-established statistic (dinv) on a specific type of combinatorial object. This connection provides a new, non-recursive proof for a significant case of the "shuffle conjecture," a long-standing problem in combinatorics.

What Problem Does This Paper Address?

The "shuffle conjecture" is a major open problem in the field of symmetric functions and combinatorics, related to the algebraic structure of diagonal harmonics. A compositional refinement of this conjecture introduced a new statistic, ndinv, which, despite having an algorithmic definition, felt somewhat unnatural and its purpose was unclear. This paper aims to shed light on ndinv by establishing a bijective connection between it and the more standard dinv statistic, thereby simplifying and providing new proofs for specific cases of the shuffle conjecture and its generalizations.

Methods

The core of this paper relies on establishing bijective correspondences between different combinatorial objects. Specifically, the authors:

  • Connect ndinv to dinv: They show that ndinv on a particular subset of "partially labelled Dyck paths" is equivalent to the standard dinv statistic on those same paths. This is achieved by composing two existing bijections that map between polyominoes and Dyck paths.
  • Prove a case of the Shuffle Conjecture: They provide a non-compositional proof for the "ehh" case of the shuffle conjecture. This is done by establishing a bijective link between a specific type of "shuffle path" and a related combinatorial object, which then leverages existing results about the "Delta conjecture" (a generalization of the shuffle conjecture).
  • Utilize Symmetric Function Theory: The paper is deeply rooted in the theory of symmetric functions, employing concepts like Macdonald polynomials, Delta operators, and various identities within this framework to formalize their combinatorial arguments.

Datasets

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

Key Insights and Ideas

  • "Unveiling the Mystery" of ndinv: The most significant insight is that ndinv isn't a fundamentally new concept but rather a different way of looking at the standard dinv statistic on a restricted class of combinatorial objects. This demystifies its seemingly artificial nature.
  • Bridging Conjectures: The paper successfully bridges the gap between the "shuffle conjecture" and the "generalized Delta conjecture" by establishing bijections between their respective combinatorial objects. This is crucial for leveraging known results and developing new proof strategies.
  • Non-Compositional Proofs: The paper offers non-compositional proofs for specific cases of these conjectures. This is valuable because compositional refinements, while powerful, can be complex. Non-compositional proofs can offer alternative perspectives and sometimes simpler arguments.
  • The Power of Bijections: The work highlights the power of bijective proofs in combinatorics. By constructing explicit maps between different structures, the authors can transfer properties and simplify complex problems.

Key Results

  • A bijective proof showing that the ndinv statistic on a specific subset of partially labelled Dyck paths is equivalent to the standard dinv statistic.
  • A non-compositional proof of the "ehh" case of the shuffle conjecture, achieved by relating it to the two-part case of the Delta conjecture via a bijection.
  • The paper provides new combinatorial interpretations and proof techniques for problems in symmetric function theory and combinatorics.

Limitations and Future Work

  • Scope of Proofs: While the paper provides new proofs for specific cases of the shuffle and Delta conjectures, it does not solve the full conjectures.
  • Future Directions: The authors suggest that the methods used in this paper could potentially be extended to tackle other open cases of the Delta conjecture, especially those involving "shuffles" of decreasing sequences. The success in demystifying ndinv also opens avenues for further exploration of its properties and connections.

Summary updated

Abstract

In [Duane, Garsia, Zabrocki 2013] the authors introduced a new dinv statistic, denoted ndinv, on the two part case of the shuffle conjecture (Haglund et al. 2005) in order to prove a compositional refinement. Though in [Hicks, Kim 2013] a non-recursive (but algorithmic) definition of ndinv has been given, this statistic still looks a bit unnatural. In this paper we "unveil the mystery" around the ndinv, by showing bijectively that the ndinv actually matches the usual dinv statistic in a special case of the generalized Delta conjecture in [Haglund, Remmel, Wilson 2018]. Moreover, we give also a non-compositional proof of the "ehh" case of the shuffle conjecture (after [Garsia, Xin, Zabrocki 2014]) by bijectively proving a relation with the two part case of the Delta conjecture.
BibTeX
@article{dadderio2019new,
  author = {Michele D’Adderio and Alessandro Iraci},
  title = {{The New dinv is Not So New}},
  journal = {The Electronic Journal of Combinatorics},
  year = {2019},
  doi = {10.37236/8588},
}
Figure