Comptes Rendus
Combinatoire
Worpitzky-compatible subarrangements of braid arrangements and cocomparability graphs
Tan Nhat Tran1  ; Akiyoshi Tsuchiya2
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
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.

Reçu le :
Accepté le :
Publié le :
DOI : 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
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@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
SP  - 665
EP  - 674
VL  - 359
IS  - 6
PB  - Académie des sciences, Paris
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
%I Académie des sciences, Paris
%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, Volume 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 | Zbl

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

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

[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 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

[23] Daisuke Suyama; Michele Torielli; Shuhei Tsujie 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] Marko Thiel On floors and ceilings of the k-Catalan arrangement, Electron. J. Comb., Volume 21 (2014) no. 4, P4.36, 15 pages | MR | Zbl

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

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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Introduction to GPGPU, a hardware and software background

Guillaume Colin de Verdière

C. R. Méca (2011)