Combinatorics
Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs
Comptes Rendus. Mathématique, Volume 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.

Received:
Accepted:
Published online:
DOI: 10.5802/crmath.210
Classification: 05C75, 17B22, 52C35, 05C31
Tran, Tan Nhat 1; Tsuchiya, Akiyoshi 2

1 Tan Nhat Tran, Department of Mathematics, Hokkaido University, Kita 10, Nishi 8, Kita-Ku, Sapporo 060-0810, Japan
2 Akiyoshi Tsuchiya, Graduate School of Mathematical Sciences, University of Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo 153-8914, Japan
@article{CRMATH_2021__359_6_665_0,
     author = {Tran, Tan Nhat and Tsuchiya, Akiyoshi},
     title = {Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {665--674},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {359},
     number = {6},
     year = {2021},
     doi = {10.5802/crmath.210},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/crmath.210/}
}
TY  - JOUR
AU  - Tran, Tan Nhat
AU  - Tsuchiya, Akiyoshi
TI  - Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs
JO  - Comptes Rendus. Mathématique
PY  - 2021
SP  - 665
EP  - 674
VL  - 359
IS  - 6
PB  - Académie des sciences, Paris
UR  - http://www.numdam.org/articles/10.5802/crmath.210/
DO  - 10.5802/crmath.210
LA  - en
ID  - CRMATH_2021__359_6_665_0
ER  - 
%0 Journal Article
%A Tran, Tan Nhat
%A Tsuchiya, Akiyoshi
%T Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs
%J Comptes Rendus. Mathématique
%D 2021
%P 665-674
%V 359
%N 6
%I Académie des sciences, Paris
%U http://www.numdam.org/articles/10.5802/crmath.210/
%R 10.5802/crmath.210
%G en
%F CRMATH_2021__359_6_665_0
Tran, Tan Nhat; Tsuchiya, Akiyoshi. Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs. Comptes Rendus. Mathématique, Volume 359 (2021) no. 6, pp. 665-674. doi : 10.5802/crmath.210. http://www.numdam.org/articles/10.5802/crmath.210/

[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 , 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

Cited by Sources: