Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs

Tran, Tan Nhat; Tsuchiya, Akiyoshi

Comptes Rendus. Mathématique, Tome 359 (2021) no. 6, pp. 665-674.

The class of Worpitzky-compatible subarrangements of a Weyl arrangement together with an associated Eulerian polynomial was recently introduced by Ashraf, Yoshinaga and the first author, which brings the characteristic and Ehrhart quasi-polynomials into one formula. The subarrangements of the braid arrangement, the Weyl arrangement of type $A$, are known as the graphic arrangements. We prove that the Worpitzky-compatible graphic arrangements are characterized by cocomparability graphs. This can be regarded as a counterpart of the characterization by Stanley and Edelman–Reiner of free and supersolvable graphic arrangements in terms of chordal graphs. Our main result yields new formulas for the chromatic and graphic Eulerian polynomials of cocomparability graphs.

Classification : 05C75, 17B22, 52C35, 05C31

[1] Abe, Takuro; Barakat, Mohamed; Cuntz, Michael; Hoge, Torsten; Terao, Hiroaki The freeness of ideal subarrangements of Weyl arrangements, J. Eur. Math. Soc., Volume 18 (2016) no. 6, pp. 1339-1348 | MR | Zbl

[2] Ashraf, Ahmed Umer; Tran, Tan Nhat; Yoshinaga, Masahiko Eulerian polynomials for subarrangements of Weyl arrangements, Adv. Appl. Math., Volume 120 (2020), 102064, 24 pages | MR | Zbl

[3] Athanasiadis, Christos A. On a refinement of the generalized Catalan numbers for Weyl groups, Trans. Am. Math. Soc., Volume 357 (2005) no. 1, pp. 179-196 | DOI | MR | Zbl

[4] Brenti, Francesco Expansions of chromatic polynomials and log-concavity, Trans. Am. Math. Soc., Volume 332 (1992) no. 2, pp. 729-756 | DOI | MR | Zbl

[5] Chung, Fan-Rong K.; Graham, Ronald L. On the cover polynomial of a digraph, J. Comb. Theory, Ser. B, Volume 65 (1995) no. 2, pp. 273-290 | DOI | MR | Zbl

[6] Edelman, Paul H.; Reiner, Victor Free hyperplane arrangements between $A_{n-1}$ and $B_n$, Math. Z., Volume 215 (1994) no. 3, pp. 347-365 | DOI | MR | Zbl

[7] Euler, Leonhard Methodus universalis series summandi ulterius promota, Commentarii Acd. Scientiarum Imperialis Petropolitanae, Volume 8 (1736), pp. 147-158 (Reprinted in his Opera Omnia, series 1, volume 14, 124-137, 1741)

[8] Gallai, Tibor Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung., Volume 18 (1967), pp. 25-66 | DOI | MR | Zbl

[9] Gilmore, Paul C.; Hoffman, Alan J. A characterization of comparability graphs and interval graphs, Can. J. Math., Volume 16 (1964), pp. 539-548 | DOI | MR | Zbl

[10] Humphreys, James E. Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, 29, Cambridge University Press, 1990 | MR | Zbl

[11] Jambu, Michel; Terao, Hiroaki Free arrangements of hyperplanes and supersolvable lattices, Adv. Math., Volume 52 (1984) no. 3, pp. 248-258 | DOI | MR | Zbl

[12] Jonsson, Jakobb The Topology of the Coloring Complex, J. Algebr. Comb., Volume 21 (2005) no. 3, pp. 311-329 | DOI | MR | Zbl

[13] Józefiak, Tadeusz; Sagan, Bruce E. Basic derivations for subarrangements of Coxeter arrangements, J. Algebr. Comb., Volume 2 (1993) no. 3, pp. 291-320 | DOI | MR | Zbl

[14] Kratsch, Dieter; Stewart, Lorna Domination on cocomparability graphs, SIAM J. Discrete Math., Volume 6 (1993) no. 3, pp. 400-417 | DOI | MR | Zbl

[15] Looges, Peter J.; Olariu, Stephan Optimal greedy algorithms for indifference graphs, Comput. Math. Appl., Volume 25 (1993) no. 7, pp. 15-25 | DOI | MR | Zbl

[16] McConnell, Ross M.; Spinrad, Jeremy P. Modular decomposition and transitive orientation, Discrete Math., Volume 201 (1999) no. 1-3, pp. 189-241 | DOI | MR | Zbl

[17] Olariu, Stephan An optimal greedy heuristic to color interval graphs, Inf. Process. Lett., Volume 37 (1991) no. 1, pp. 21-25 | DOI | MR | Zbl

[18] Orlik, Peter; Terao, Hiroaki Arrangements of hyperplanes, Grundlehren der Mathematischen Wissenschaften, 300, Springer, 1992 | MR | Zbl

[19] Petersen, T. Kyle Eulerian numbers, Birkhäuser Advanced Texts. Basler Lehrbücher, Birkhäuser, 2015 | Zbl

[20] Shi, Jian-Yi Alcoves corresponding to an affine Weyl group, J. Lond. Math. Soc., Volume 35 (1987), pp. 42-55 | MR | Zbl

[21] Stanley, Richard P. Supersolvable lattices, Algebra Univers., Volume 2 (1972), pp. 197-217 | DOI | MR | Zbl

[22] Steingrímsson, Einar The coloring ideal and coloring complex of a graph, J. Algebr. Comb., Volume 14 (2001) no. 1, pp. 73-84 | DOI | MR | Zbl

[23] Suyama, Daisuke; Torielli, Michele; Tsujie, Shuhei Signed graphs and the freeness of the Weyl subarrangements of type $B_{\ell }$, Discrete Math., Volume 342 (2019) no. 1, pp. 233-249 | DOI | MR | Zbl

[24] Thiel, Marko On floors and ceilings of the $k$-Catalan arrangement, Electron. J. Comb., Volume 21 (2014) no. 4, P4.36, 15 pages | MR | Zbl

[25] Trotter, William T. Combinatorics and partially ordered sets: Dimension theory, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, 1992 | Zbl

[26] Yoshinaga, Masahiko Worpitzky partitions for root systems and characteristic quasi-polynomials, Tôhoku Math. J., Volume 70 (2018) no. 1, pp. 39-63 | MR | Zbl