Bijections for faces of the Shi and Catalan arrangements

DOI10.37236/10008MaRDI QIDQ2665971zbMATH OpenOpenAlexFDO

Authors Duncan Levear

Publication date 22 November 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2008.02357

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bijective proofdecorated binary treeshyperplane arrangementShi arrangement

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Trees (05C05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: In 1986, Shi derived the famous formula $(n+1{)}^{n-1}$ for the number of regions of the Shi arrangement, a hyperplane arrangement in $mathbb{R}^n$. There are at least two different bijective explanations of this formula, one by Pak and Stanley, another by Athanasiadis and Linusson. In 1996, Athanasiadis used the finite field method to derive a formula for the number of $k$-dimensional faces of the Shi arrangement for any $k$. Until now, the formula of Athanasiadis did not have a bijective explanation. In this paper, we extend a bijection for regions defined by Bernardi to obtain a bijection between the $k$-dimensional faces of the Shi arrangement for any $k$ and a set of decorated binary trees. Furthermore, we show how these trees can be converted to a simple set of functions of the form $f:[n-1]o[n+1]$ together with a marked subset of $extIm(f)$. This correspondence gives the first bijective proof of the formula of Athanasiadis. In the process, we also obtain a bijection and counting formula for the faces of the Catalan arrangement. All of our results generalize to both extended arrangements.

Review text

Summary: \textit{J.-Y. Shi} [The Kazhdan-Lusztig cells in certain affine Weyl groups. Springer, Cham (1986; Zbl 0582.20030)] derived the famous formula \((n+1)^{n-1}\) for the number of regions of the Shi arrangement, a hyperplane arrangement in \({R}^n\). There are at least two different bijective explanations of this formula, one by Pak and Stanley, another by \textit{C. A. Athanasiadis} and \textit{S. Linusson} [Discrete Math. 204, No. 1--3, 27--39 (1999; Zbl 0959.52019)]. \textit{C. A. Athanasiadis} [Algebraic combinatorics of graph spectra, subspace arrangements and Tutte polynomials. Cambridge, Massachusetts: Massachusetts Institute of Technology (PhD Thesis) (1996)] used the finite field method to derive a formula for the number of \(k\)-dimensional faces of the Shi arrangement for any \(k\). Until now, the formula of Athanasiadis did not have a bijective explanation. In this paper, we extend a bijection for regions defined by \textit{O. Bernardi} [Adv. Math. 335, 466--518 (2018; Zbl 1394.05056)] to obtain a bijection between the \(k\)-dimensional faces of the Shi arrangement for any \(k\) and a set of decorated binary trees. Furthermore, we show how these trees can be converted to a simple set of functions of the form \(f: [n-1] \to [n+1]\) together with a marked subset of \(\text{Im}(f)\). This correspondence gives the first bijective proof of the formula of Athanasiadis. In the process, we also obtain a bijection and counting formula for the faces of the Catalan arrangement. All of our results generalize to both extended arrangements.

Recommendations

• A bijection for Shi arrangement faces
• The Shi arrangement and the Ish arrangement
• A simple bijection for the regions of the Shi arrangement of hyperplanes
• The Shi arrangement and the Ish arrangement
• Bijections between affine hyperplane arrangements and valued graphs

Cites work

• A bijection for Shi arrangement faces
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• A combinatorial reciprocity theorem for hyperplane arrangements
• A simple bijection for the regions of the Shi arrangement of hyperplanes
• An introduction to hyperplane arrangements
• Analytic combinatorics
• Bigraphical arrangements
• Bijections between affine hyperplane arrangements and valued graphs
• Catalan Numbers
• Characteristic polynomials of subspace arrangements and finite fields
• Counting faces in the extended Shi arrangement
• Deformations of Coxeter hyperplane arrangements
• Deformations of the braid arrangement and trees
• GENERALIZED CATALAN NUMBERS, WEYL GROUPS AND ARRANGEMENTS OF HYPERPLANES
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• Hyperplane arrangements, interval orders, and trees.
• Labeled binary trees, subarrangements of the Catalan arrangements, and Schur positivity
• Orientations, semiorders, arrangements, and parking functions
• Random walks and hyperplane arrangements
• Shi threshold arrangement
• The braid and the Shi arrangements and the Pak-Stanley labelling
• The cycle lemma and some applications
• The Kazhdan-Lusztig cells in certain affine Weyl groups
• The number of elements in a generalized partition semilattice
• The Shi arrangement and the Ish arrangement
• Topics in hyperplane arrangements

Cited in

(16)

• A simple bijection for the regions of the Shi arrangement of hyperplanes
• Labeling the regions of the type C_n Shi arrangement
• Counting faces in the extended Shi arrangement
• Bijections on \(r\)-Shi and \(r\)-Catalan arrangements
• A bijection for Shi arrangement faces
• Bijections for the Shi and Ish arrangements
• Combinatorial enumeration of the regions of some linear arrangements
• Dominant Shi regions with a fixed separating wall: bijective enumeration
• A bijection between (bounded) dominant Shi regions and core partitions
• Bijections between affine hyperplane arrangements and valued graphs
• Enumeration of flats of the extended Catalan and Shi arrangements with species
• Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
• Activity from matroids to rooted trees and beyond
• A bijection between dominant Shi regions and core partitions
• Bijections between generalized Catalan families of types \(A\) and \(C\)
• Bijections for faces of braid-type arrangements

This page was built for publication: Bijections for faces of the Shi and Catalan arrangements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2665971)