×

Deformations of the braid arrangement and trees. (English) Zbl 1394.05056

Summary: We establish general counting formulas and bijections for deformations of the braid arrangement. Precisely, we consider real hyperplane arrangements such that all the hyperplanes are of the form \(x_i - x_j = s\) for some integer \(s\). Classical examples include the braid, Catalan, Shi, semiorder and linial arrangements, as well as graphical arrangements. We express the number of regions of any such arrangement as a signed count of decorated plane trees. The characteristic and coboundary polynomials of these arrangements also have simple expressions in terms of these trees.
We then focus on certain “well-behaved” deformations of the braid arrangement that we call transitive. This includes the Catalan, Shi, semiorder and linial arrangements, as well as many other arrangements appearing in the literature. For any transitive deformation of the braid arrangement we establish a simple bijection between regions of the arrangement and a set of labeled plane trees defined by local conditions. This answers a question of I. M. Gessel [“Counting labeled binary trees by ascents and descents” (2016), Preprint].

MSC:

05C30 Enumeration in graph theory
14N15 Classical problems, Schubert calculus
20F55 Reflection and Coxeter groups (group-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ardila, F., Computing the Tutte polynomial of a hyperplane arrangement, Pacific J. Math., 230, 1, 1-26, (2007) · Zbl 1152.52011
[2] Ardila, F., Semimatroids and their Tutte polynomials, Rev. Colombiana Mat., 41, 1, 39-66, (2007) · Zbl 1136.05008
[3] Armstrong, D.; Rhoades, B., The shi arrangement and the ish arrangement, Trans. Amer. Math. Soc., 364, 3, 1509-1528, (2012) · Zbl 1238.05271
[4] Assi, A.; García-Sánchez, P. A., Numerical semigroups and applications, (2016), Springer · Zbl 1368.20001
[5] Athanasiadis, C. A., Characteristic polynomials of subspace arrangements and finite fields, Adv. Math., 122, 2, 193-233, (1996) · Zbl 0872.52006
[6] Athanasiadis, C. A., Algebraic combinatorics of graph spectra, subspace arrangements and Tutte polynomials, (1996), MIT, PhD thesis
[7] Athanasiadis, C. A., On free deformations of the braid arrangement, European J. Combin., 19, 7-18, (1998) · Zbl 0898.52008
[8] Athanasiadis, C. A., Extended linial hyperplane arrangements for root systems and a conjecture of postnikov and Stanley, J. Algebraic Combin., 10, 207-225, (1999) · Zbl 0948.52012
[9] Athanasiadis, C. A., Deformations of Coxeter hyperplane arrangements and their characteristic polynomials, (Arrangements - Tokyo 1998, Adv. Stud. Pure Math., vol. 27, (2000)), 1-26 · Zbl 0976.32016
[10] Athanasiadis, C. A., Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. Lond. Math. Soc., 36, 3, 294-302, (2004) · Zbl 1068.20038
[11] Athanasiadis, C. A.; Linusson, S., A simple bijection for the regions of the shi arrangement of hyperplanes, Discrete Math., 204, 1, 27-39, (1999) · Zbl 0959.52019
[12] Bernardi, O., Solution to a combinatorial puzzle arising from Mayer’s theory of cluster integrals, Sém. Lothar. Combin., 59, (2008) · Zbl 1193.05012
[13] Carlitz, L.; Scoville, R., Generalized Eulerian numbers: combinatorial applications, J. Reine Angew. Math., 265, 110-137, (1974) · Zbl 0276.05006
[14] Chandon, J. L.; Lemaire, J.; Pouget, J., Dénombrement des quasi-ordres sur un ensemble fini, Math. Inform. Sci. Hum., 62, 62, 61-80, (1978) · Zbl 0446.06001
[15] Corteel, S.; Forge, D.; Ventos, V., Bijections between affine hyperplane arrangements and valued graphs, European J. Combin., 50, 30-37, (2015) · Zbl 1323.52012
[16] Crapo, H. H., The Tutte polynomial, Aequationes Math., 3, 211-229, (1969) · Zbl 0197.50202
[17] Drake, B., An inversion theorem for labeled trees and some limits of areas under lattice paths, (2008), Brandeis University, PhD thesis
[18] Flajolet, P.; Sedgewick, R., Analytic combinatorics, (2009), Cambridge University Press · Zbl 1165.05001
[19] Forge, D., Linial arrangements and local binary search trees, (2014), ArXiv preprint:
[20] Gessel, I. M., A combinatorial proof of the multivariable Lagrange inversion formula, J. Combin. Theory Ser. A, 45, 2, (1987) · Zbl 0651.05009
[21] I.M. Gessel, Problems in enumerative combinatorics, personal communication.; I.M. Gessel, Problems in enumerative combinatorics, personal communication.
[22] I.M. Gessel, Counting labeled binary trees by ascents and descents, preprint, 2016.; I.M. Gessel, Counting labeled binary trees by ascents and descents, preprint, 2016.
[23] Gessel, I. M.; Griffin, S.; Tewari, V., Labeled plane binary trees and Schur-positivity, (2017) · Zbl 1384.05135
[24] Good, I. J., Generalizations to several variables of Lagrange’s expansion, with applications to stochastic processes, Proc. Camb. Philos. Soc., 56, 367-380, (1960) · Zbl 0135.18802
[25] Headley, P., On a family of hyperplane arrangements related to the affine Weyl groups, J. Algebraic Combin., 6, 4, 331-338, (1997) · Zbl 0911.52009
[26] Hopkins, S.; Perkinson, D., Orientations, semiorders, arrangements, and parking functions, Electron. J. Combin., 19, 4, (2012), Paper #P8 · Zbl 1267.05138
[27] Hopkins, S.; Perkinson, D., Bigraphical arrangements, Trans. Amer. Math. Soc., 368, 709-725, (2016) · Zbl 1325.05089
[28] Kalikow, L. H., Symmetries in trees and parking functions, Discrete Math., 256, 3, 719-741, (2002) · Zbl 1010.05021
[29] C. Krattenthaler, The theory of heaps and the Cartier-Foata monoid, Appendix to the electronic republication of P. Cartier, D. Foata, Problèmes combinatoires de commutation et réarrangements, 2006.; C. Krattenthaler, The theory of heaps and the Cartier-Foata monoid, Appendix to the electronic republication of P. Cartier, D. Foata, Problèmes combinatoires de commutation et réarrangements, 2006.
[30] Leroux, P., Enumerative problems inspired by Mayer’s theory of cluster integrals, Electron. J. Combin., 11, (2006) · Zbl 1054.05056
[31] Leven, E.; Rhoades, B.; Wilson, A. T., Bijections for the shi and ish arrangements, European J. Combin., 39, 1-23, (2014) · Zbl 1284.05331
[32] Mayer, J. E.; Mayer, M. G., Statistical mechanics, (1940), Wiley · JFM 66.1175.01
[33] Orlik, P.; Solomon, L., Combinatorics and topology of complements of hyperplanes, Invent. Math., 56, 2, 167-189, (1980) · Zbl 0432.14016
[34] Orlik, P.; Terao, H., Arrangements of hyperplanes, (1992), Springer-Verlag · Zbl 0757.55001
[35] Postnikov, A., Enumeration in algebra and geometry, (1997), MIT, PhD thesis
[36] Postnikov, A., Intransitive trees, J. Combin. Theory Ser. A, 77, 360-366, (1997) · Zbl 0876.05042
[37] Postnikov, A.; Stanley, R., Deformations of Coxeter hyperplane arrangements, J. Combin. Theory Ser. A, 2000, 544-597, (2000) · Zbl 0962.05004
[38] Shi, J. Y., The Kazhdan-Lusztig cells in certain affine Weyl groups, Lecture Notes in Mathematics, vol. 1179, (1986), Springer-Verlag · Zbl 0582.20030
[39] Shi, J. Y., Sign types corresponding to an affine Weyl group, J. Lond. Math. Soc., 35, 2, 56-74, (1987) · Zbl 0681.20033
[40] Stanley, R. P., Acyclic orientations of graphs, Discrete Math., 5, 171-178, (1973) · Zbl 0258.05113
[41] Stanley, R. P., Hyperplane arrangements, interval orders and trees, Proc. Nat. Acad. Sci., 93, 6, 2620-2625, (1996) · Zbl 0848.05005
[42] Stanley, R. P., Hyperplane arrangements, parking functions and tree inversions, (Progress in Mathematics, vol. 161, (1998)) · Zbl 0917.52013
[43] Stanley, R. P., Enumerative combinatorics, vol. 2, (1999), Cambridge University Press · Zbl 0928.05001
[44] Stanley, R. P., An introduction to hyperplane arrangements, (Lecture Notes, (2004), IAS/Park City Mathematics Institute)
[45] Viennot, X. G., Heaps of pieces. I. basic definitions and combinatorial lemmas, Lecture Notes in Math., vol. 1234, (1986), Springer · Zbl 0618.05008
[46] Zaslavsky, T., Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc., 154, 1, (1975) · Zbl 0296.50010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.