ALGEBRAIC COMBINATORICS

no. 6
On the WL-dimension of circulant graphs of prime power order
Ponomarenko, Ilia1
1 Steklov Institute of Mathematics at St. Petersburg, Russia
Algebraic Combinatorics, Volume 6 (2023) no. 6, pp. 1469-1490.

The WL-dimension of a graph X is the smallest positive integer m such that the m-dimensional Weisfeiler–Leman algorithm correctly tests the isomorphism between X and any other graph. It is proved that the WL-dimension of any circulant graph of prime power order is at most 3, and this bound cannot be reduced. The proof is based on using theories of coherent configurations and Cayley schemes over a cyclic group.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.315
Classification: 05C60, 05E30
Keywords: Weisfeiler–Leman algorithm, circulant graphs, coherent configurations
Ponomarenko, Ilia 1

1 Steklov Institute of Mathematics at St. Petersburg, Russia
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2023__6_6_1469_0,
     author = {Ponomarenko, Ilia},
     title = {On the {WL-dimension} of circulant graphs of prime power order},
     journal = {Algebraic Combinatorics},
     pages = {1469--1490},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {6},
     year = {2023},
     doi = {10.5802/alco.315},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.315/}
}
TY  - JOUR
AU  - Ponomarenko, Ilia
TI  - On the WL-dimension of circulant graphs of prime power order
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 1469
EP  - 1490
VL  - 6
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.315/
DO  - 10.5802/alco.315
LA  - en
ID  - ALCO_2023__6_6_1469_0
ER  - 
%0 Journal Article
%A Ponomarenko, Ilia
%T On the WL-dimension of circulant graphs of prime power order
%J Algebraic Combinatorics
%D 2023
%P 1469-1490
%V 6
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.315/
%R 10.5802/alco.315
%G en
%F ALCO_2023__6_6_1469_0
Ponomarenko, Ilia. On the WL-dimension of circulant graphs of prime power order. Algebraic Combinatorics, Volume 6 (2023) no. 6, pp. 1469-1490. doi : 10.5802/alco.315. https://alco.centre-mersenne.org/articles/10.5802/alco.315/

[1] Babai, L. Group, graphs, algorithms: the graph isomorphism problem, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3319-3336 | Zbl

[2] Bagherian, J.; Memarzadeh, H. The generalized X-join of Cayley graphs and their automorphisms, Ars Math. Contemp., Volume 24 (2024), Paper no. 6, 23 pages | Zbl

[3] Chen, G.; Ponomarenko, I. Coherent Configurations, Central China Normal University Press, 2019 (the updated version is available at http://www.pdmi.ras.ru/~inp/ccNOTES.pdf)

[4] Evdokimov, S.; Kovács, I.; Ponomarenko, I. Characterization of cyclic Schur groups, St. Petersburg Math. J., Volume 25 (2014), pp. 755-773 | DOI | Zbl

[5] Evdokimov, S.; Ponomarenko, I. On a family of Schur rings over a finite cyclic group, St. Petersburg Math. J., Volume 13 (2002) no. 3, pp. 441-451 | Zbl

[6] Evdokimov, S.; Ponomarenko, I. Characterization of cyclotomic schemes and normal Schur rings over a cyclic group, St. Petersburg Math. J., Volume 14 (2003) no. 2, pp. 189-221

[7] Evdokimov, S.; Ponomarenko, I. Recognizing and isomorphism testing circulant graphs in polynomial time, St. Petersburg Math. J., Volume 15 (2004) no. 6, pp. 813-835 | DOI | Zbl

[8] Evdokimov, S.; Ponomarenko, I. Schurity of S-rings over a cyclic group and generalized wreath product of permutation groups, St. Petersburg Math. J., Volume 24 (2013) no. 3, pp. 431-460 | DOI | Zbl

[9] Evdokimov, S.; Ponomarenko, I. On the separability problem for circulant S-rings, St. Petersburg Math. J., Volume 28 (2017) no. 1, pp. 21-35 | DOI | MR | Zbl

[10] Fuhlbrück, F.; Köbler, J.; Verbitsky, O. Identifiability of Graphs with Small Color Classes by the Weisfeiler–Leman Algorithm, SIAM J. Discrete Math., Volume 35 (2021) no. 3, pp. 1792-1853 | DOI | MR | Zbl

[11] Gol’fand, Y. Y.; Klin, M. H.; Naimark, N. L. The structure of S-rings over Z 2 m , Sixteenth All Union Algebraic Conference. Part 2, Leningrad (1981), pp. 195-196

[12] Grohe, M. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Cambridge University Press, 2017 | DOI

[13] Helfgott, H.; Bajpai, J.; Dona, D. Graph isomorphisms in quasi-polynomial time, 2017 | arXiv

[14] Muzychuk, M. A wedge product of association schemes, European J. Combin., Volume 30 (2009) no. 3, pp. 705-715 | DOI | MR | Zbl

[15] Pikhurko, O.; Verbitsky, O. Logical complexity of graphs: a survey, Model theoretic methods in finite combinatorics, Amer. Math. Soc., Providence, RI, 2011, pp. 129-179 | DOI | Zbl

[16] Pöschel, R. Untersuchungen von S-Ringen, insbesondere im Gruppenring von p-Gruppen, Math. Nachr., Volume 60 (1974), pp. 1-27 | DOI | MR | Zbl

[17] Weisfeiler, B. Yu.; Leman, A. A. The reduction of a graph to canonical form and the algebra which appears therein, NTI, Ser. 2, Volume 9 (1968), pp. 12-16 (English translation is available at https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf)

Cited by Sources: