# 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
OEIS
Full Text:
##### References:
  Arnold, V.I., The cohomology ring of a colored braid group, Math. notes, 5, 138-140, (1969) · Zbl 0277.55002  Athanasiadis, C.A., Algebraic combinatorics of graph spectra, subspace arrangements and Tutte polynomials, (1996), MIT  Athanasiadis, C.A., Characteristic polynomials of subspace arrangements and finite fields, Adv. in math., 122, 193-233, (1996) · Zbl 0872.52006  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  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  Bourbaki, N., Groupes et algèbres de Lie, (1968), Hermann Paris  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  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  de Bruijn, N.G., Asymptotic methods in analysis, (1958), North-Holland Amsterdam · Zbl 0082.04202  Edelman, P.; Reiner, V., Free arrangements and rhombic tilings, Discrete comput. geom., 15, 307-340, (1996) · Zbl 0853.52013  Gelfand, I.M.; Graev, M.I.; Postnikov, A., Hypergeometric functions associated with positive roots, (), 205-221 · Zbl 0876.33011  Goulden, I.P.; Jackson, D.M., Combinatorial enumeration, (1983), Wiley New York · Zbl 0519.05001  Harary, F.; Palmer, E.M., Graphical enumeration, (1973), Academic Press New York/London  Headley, P., On a family of hyperplane arrangements related to affine Weyl groups, J. algebraic combin., 6, 331-338, (1997) · Zbl 0911.52009  Obreschkoff, N., Aufgabe 35, section 2, Jahresber. Deutsch. math.-verein., 36, 43-45, (1927)  Orlik, P.; Solomon, L., Combinatorics and topology of complements of hyperplanes, Invent. math., 56, 167-189, (1980) · Zbl 0432.14016  Orlik, P.; Terao, H., Arrangements of hyperplanes, (1992), Springer-Verlag Berlin/Heidelberg/New York · Zbl 0757.55001  Pólya, G., Aufgabe 35, section 2, Jahresber. Deutsch. math.-verein., 35, 48, (1926)  Pólya, G.; Szegő, G., Problems and theorems in analysis, (1976), Springer-Verlag Berlin/Heidelberg/New York · Zbl 0338.00001  Postnikov, A., Intransitive trees, J. combin. theory ser. A., 79, 360-366, (1997) · Zbl 0876.05042  A. Postnikov, and, R. P. Stanley, Deformations of Coxeter hyperplane arrangements, E-print math.CO/9712213, dated, 14 April 1997.  Prüfer, H., Neuer beweis eines satzes über permutationen, Arch. math. phys., 27, 742-744, (1918) · JFM 46.0106.04  R. W. Robinson, personal communication, in, Sloane’s On-Line Encyclopedia of Integer Sequences, www.research.att.com/∼njas/sequences, ID number A007106.  Scott, D.; Suppes, P., Foundational aspects of theories of measurement, J. symbolic logic, 23, 113-128, (1958) · Zbl 0084.24603  Shi, J.-Y., The kazhdan – lusztig cells in certain affine Weyl groups, Lecture notes in mathematics, 179, (1986), Springer-Verlag Berlin/Heidelberg/New York  Shi, J.-Y., Sign types corresponding to an affine Weyl group, J. London math. soc., 35, 56-74, (1987) · Zbl 0681.20033  Stanley, R.P., Enumerative combinatorics, (1986), Wadsworth & Brooks-Cole Belmont · Zbl 0608.05001  Stanley, R.P., Enumerative combinatorics, (1999), Cambridge Univ. Press Cambridge · Zbl 0928.05001  Stanley, R.P., Hyperplane arrangements, interval orders, and trees, Proc. nat. acad. sci. U.S.A., 93, 2620-2625, (1996) · Zbl 0848.05005  Trotter, W.T., Combinatorics and partially ordered sets, (1992), The Johns Hopkins Univ. Press Baltimore/London  Wachs, M.L.; Walker, J.W., On geometric semilattices, Order, 2, 367-385, (1986) · Zbl 0589.06005  Whitney, H., A logical expansion in mathematics, Bull. amer. math. soc., 38, 572-579, (1932) · JFM 58.0605.08  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  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.