On the separability of cyclotomic schemes over finite fields

Ponomarenko, I.

doi:10.1090/spmj/1684

On the separability of cyclotomic schemes over finite fields
HTML articles powered by AMS MathViewer

by I. Ponomarenko
Translated by: the author

St. Petersburg Math. J. 32 (2021), 1051-1066

DOI: https://doi.org/10.1090/spmj/1684

Published electronically: October 20, 2021

PDF | Request permission

Abstract:

It is proved that with finitely many possible exceptions, each cyclotomic scheme over a finite field is determined up to isomorphism by the tensor of $2$-dimensional intersection numbers; for infinitely many schemes, this result cannot be improved. As a consequence, the Weisfeiler–Leman dimension of a Paley graph or tournament is at most $3$ with possible exception of several small graphs.

References

Jin-Yi Cai, Martin Fürer, and Neil Immerman, An optimal lower bound on the number of variables for graph identification, Combinatorica 12 (1992), no. 4, 389–410. MR 1194730, DOI 10.1007/BF01305232
Gang Chen and Ilia Ponomarenko, Coherent configurations associated with TI-subgroups, J. Algebra 488 (2017), 201–229. MR 3680916, DOI 10.1016/j.jalgebra.2017.06.004
—, Coherent configurations, Central China Normal Univ. Press, 2019.
Sergei Evdokimov and Ilia Ponomarenko, Separability number and Schurity number of coherent configurations, Electron. J. Combin. 7 (2000), Research Paper 31, 33. MR 1763969, DOI 10.37236/1509
S. A. Evdokimov and I. N. Ponomarenko, Characterization of cyclotomic schemes and normal Schur rings over a cyclic group, Algebra i Analiz 14 (2002), no. 2, 11–55 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 14 (2003), no. 2, 189–221. MR 1925880
Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky, Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm, 37th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 154, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, pp. Art. No. 43, 18. MR 4093563
Martin Grohe, Descriptive complexity, canonisation, and definable graph structure theory, Lecture Notes in Logic, vol. 47, Association for Symbolic Logic, Ithaca, NY; Cambridge University Press, Cambridge, 2017. MR 3729479, DOI 10.1017/9781139028868
A. Hanaki and I. Miyamoto, Classification of association schemes with small number of vertices, http://math.shinshu-u.ac.jp/~hanaki/as/ (2016).
Mitsugu Hirasaka, Kijung Kim, and Ilia Ponomarenko, Two-valenced association schemes and the Desargues theorem, Arab. J. Math. (Springer) 9 (2020), no. 3, 481–493. MR 4159733, DOI 10.1007/s40065-019-00274-w
M. Klin, C. Pech, and S. Reichard, COCO2P — a GAP$4$ package, ver. $0.18$ (2020); https:// github.com/chpech/COCO2P/archive/coco2p-0.18.tar.gz.
M. Muzychuk, On Skew Hadamard difference sets, arXiv:1012.2089 (2010).
Mikhail Muzychuk and Ilya Ponomarenko, On pseudocyclic association schemes, Ars Math. Contemp. 5 (2012), no. 1, 1–25. MR 2853699, DOI 10.26493/1855-3974.121.885