Combinatoire
Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs
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.

Reçu le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/crmath.210
Classification : 05C75,  17B22,  52C35,  05C31
Tan Nhat Tran 1 ; Akiyoshi Tsuchiya 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 = {Tan Nhat Tran and Akiyoshi Tsuchiya},
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},
}
TY  - JOUR
AU  - Tan Nhat Tran
AU  - Akiyoshi Tsuchiya
TI  - Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs
JO  - Comptes Rendus. Mathématique
PY  - 2021
DA  - 2021///
SP  - 665
EP  - 674
VL  - 359
IS  - 6
PB  - Académie des sciences, Paris
UR  - https://doi.org/10.5802/crmath.210
DO  - 10.5802/crmath.210
LA  - en
ID  - CRMATH_2021__359_6_665_0
ER  - 
%0 Journal Article
%A Tan Nhat Tran
%A Akiyoshi Tsuchiya
%T Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs
%J Comptes Rendus. Mathématique
%D 2021
%P 665-674
%V 359
%N 6
%U https://doi.org/10.5802/crmath.210
%R 10.5802/crmath.210
%G en
%F CRMATH_2021__359_6_665_0
Tan Nhat Tran; Akiyoshi Tsuchiya. Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs. Comptes Rendus. Mathématique, Tome 359 (2021) no. 6, pp. 665-674. doi : 10.5802/crmath.210. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.210/

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

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

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

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

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

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

[7] Leonhard Euler 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] Tibor Gallai Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung., Volume 18 (1967), pp. 25-66 | Article | MR 221974 | Zbl 0153.26002

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :