×

zbMATH — the first resource for mathematics

Deformations of Coxeter hyperplane arrangements. (English) Zbl 0962.05004
The paper investigates the enumeration problem of regions in several real hyperplane arrangements that can be considered as deformations of the Coxeter arrangement of type \(A_{n- 1}\) (\(x_i- x_j= 0\) for \(1\leq i< j\leq n\)). In particular, for the Linial arrangement \(x_i- x_j= 1\) for \(1\leq i< j\leq n\), the number of regions is equal to the number of alternating trees on \(n+1\) vertices, or the number of local binary search trees on \(n\) vertices. The regions of the Linial arrangement also bijectively correspond to sleek posets and semiacyclic tournaments. (A poset on \(n\) vertices is sleek, if it is the intersection of a semiorder with an \(n\)-chain; sleek posets are characterized as not having any of some 4 induced subposets. A tournament on the vertex set \(\{1,2,\dots, n\}\) is semiacyclic, if on every directed cycle more edges go “down” than “up”; semiacyclic tournaments are characterized as not having any of some 6 kinds of cycles of lengths 3 and 4.)
Furthermore, the paper studies the number of regions in the following classes of arrangements: generic arrangement (\(x_i- x_j= a_{ij}\) for \(1\leq i< j\leq n\), where the \(a_{ij}\)’s are generic real numbers); semigeneric arrangement (\(x_i- x_j= a_i\) for \(1\leq i,j\leq n\), \(i\neq j\)); Shi arrangement (\(x_i- x_j= 0, 1\) for \(1\leq i< j\leq n\)); extended Shi arrangement (\(x_i- x_j= -k\), \(-k+ 1,\dots, k+1\) for \(1\leq i< j\leq n\), where \(k\geq 0\) is fixed); Catalan arrangement (\(x_i- x_j= -1, 1\), or \(x_i- x_j= -1, 0, 1\) for \(1\leq i< j\leq n\)); truncated affine arrangement (\(x_i- x_j= -a+1\), \(-a+2,\dots, b-1\) for \(1\leq i< j\leq n\), where \(a\) and \(b\) are fixed integers such that \(a+ b\geq 2\)).
Formulae for the characteristic polynomial of truncated affine arrangements are obtained, and from here an amazing analogue of the Riemann hypothesis for the characteristic roots is derived. Some asymptotic formulae are provided for the characteristic polynomials, in particular for that of the Linial arrangement, and hence for the number of regions in the Linial arrangement and for the number of alternating trees. For root systems other than \(A_{n- 1}\), a number of conjectures are made for expected analogues of the theorems proved in this paper.

MSC:
05A15 Exact enumeration problems, generating functions
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
05A16 Asymptotic enumeration
05C05 Trees
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnold, V.I., The cohomology ring of a colored braid group, Math. notes, 5, 138-140, (1969) · Zbl 0277.55002
[2] Athanasiadis, C.A., Algebraic combinatorics of graph spectra, subspace arrangements and Tutte polynomials, (1996), MIT
[3] Athanasiadis, C.A., Characteristic polynomials of subspace arrangements and finite fields, Adv. in math., 122, 193-233, (1996) · Zbl 0872.52006
[4] 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
[5] Auric, M.A., Généralisation d’un théorème de Laguerre, C.R. acad. sci. Paris, 137, 967-969, (1903) · JFM 34.0100.01
[6] Bourbaki, N., Groupes et algèbres de Lie, (1968), Hermann Paris
[7] Brieskorn, E., Sur LES groupes de tress, Séminaire bourbaki 1971/1972, Lecture notes in mathematics, 317, (1973), Springer-Verlag Berlin/New York, p. 21-44
[8] Chandon, J.L.; Lemaire, J.; Pouget, J., Dénombrement des quasi-ordres sur un ensemble fini, Math. inform. sci. humaines, 62, 61-80, 83, (1978) · Zbl 0446.06001
[9] de Bruijn, N.G., Asymptotic methods in analysis, (1958), North-Holland Amsterdam · Zbl 0082.04202
[10] Edelman, P.; Reiner, V., Free arrangements and rhombic tilings, Discrete comput. geom., 15, 307-340, (1996) · Zbl 0853.52013
[11] Gelfand, I.M.; Graev, M.I.; Postnikov, A., Hypergeometric functions associated with positive roots, (), 205-221 · Zbl 0876.33011
[12] Goulden, I.P.; Jackson, D.M., Combinatorial enumeration, (1983), Wiley New York · Zbl 0519.05001
[13] Harary, F.; Palmer, E.M., Graphical enumeration, (1973), Academic Press New York/London
[14] Headley, P., On a family of hyperplane arrangements related to affine Weyl groups, J. algebraic combin., 6, 331-338, (1997) · Zbl 0911.52009
[15] Obreschkoff, N., Aufgabe 35, section 2, Jahresber. Deutsch. math.-verein., 36, 43-45, (1927)
[16] Orlik, P.; Solomon, L., Combinatorics and topology of complements of hyperplanes, Invent. math., 56, 167-189, (1980) · Zbl 0432.14016
[17] Orlik, P.; Terao, H., Arrangements of hyperplanes, (1992), Springer-Verlag Berlin/Heidelberg/New York · Zbl 0757.55001
[18] Pólya, G., Aufgabe 35, section 2, Jahresber. Deutsch. math.-verein., 35, 48, (1926)
[19] Pólya, G.; Szegő, G., Problems and theorems in analysis, (1976), Springer-Verlag Berlin/Heidelberg/New York · Zbl 0338.00001
[20] Postnikov, A., Intransitive trees, J. combin. theory ser. A., 79, 360-366, (1997) · Zbl 0876.05042
[21] A. Postnikov, and, R. P. Stanley, Deformations of Coxeter hyperplane arrangements, E-print math.CO/9712213, dated, 14 April 1997.
[22] Prüfer, H., Neuer beweis eines satzes über permutationen, Arch. math. phys., 27, 742-744, (1918) · JFM 46.0106.04
[23] R. W. Robinson, personal communication, in, Sloane’s On-Line Encyclopedia of Integer Sequences, www.research.att.com/∼njas/sequences, ID number A007106.
[24] Scott, D.; Suppes, P., Foundational aspects of theories of measurement, J. symbolic logic, 23, 113-128, (1958) · Zbl 0084.24603
[25] Shi, J.-Y., The kazhdan – lusztig cells in certain affine Weyl groups, Lecture notes in mathematics, 179, (1986), Springer-Verlag Berlin/Heidelberg/New York
[26] Shi, J.-Y., Sign types corresponding to an affine Weyl group, J. London math. soc., 35, 56-74, (1987) · Zbl 0681.20033
[27] Stanley, R.P., Enumerative combinatorics, (1986), Wadsworth & Brooks-Cole Belmont · Zbl 0608.05001
[28] Stanley, R.P., Enumerative combinatorics, (1999), Cambridge Univ. Press Cambridge · Zbl 0928.05001
[29] Stanley, R.P., Hyperplane arrangements, interval orders, and trees, Proc. nat. acad. sci. U.S.A., 93, 2620-2625, (1996) · Zbl 0848.05005
[30] Trotter, W.T., Combinatorics and partially ordered sets, (1992), The Johns Hopkins Univ. Press Baltimore/London
[31] Wachs, M.L.; Walker, J.W., On geometric semilattices, Order, 2, 367-385, (1986) · Zbl 0589.06005
[32] Whitney, H., A logical expansion in mathematics, Bull. amer. math. soc., 38, 572-579, (1932) · JFM 58.0605.08
[33] Wine, R.L.; Freund, J.E., On the enumeration of decision patterns involving n means, Ann. math. statist., 28, 256-259, (1957) · Zbl 0078.00905
[34] Zaslavsky, T., Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. amer. math. soc., 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.