{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T09:28:11Z","timestamp":1771406891283,"version":"3.50.1"},"reference-count":47,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T00:00:00Z","timestamp":1764115200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    It is well known that almost all graphs are canonizable by a simple combinatorial routine known as colour refinement, also referred to as the 1-dimensional Weisfeiler\u2013Leman algorithm. With high probability, this method assigns a unique label to each vertex of a random input graph and, hence, it is applicable only to asymmetric graphs. The strength of combinatorial refinement techniques becomes a subtle issue if the input graphs are highly symmetric. We prove that the combination of colour refinement and vertex individualization yields a canonical labelling for almost all circulant digraphs (i.e., Cayley digraphs of a cyclic group). This result provides first evidence of good average-case performance of combinatorial refinement within the class of vertex-transitive graphs. Remarkably, we do not even need the full power of the colour refinement algorithm. We show that the canonical label of a vertex\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S096354832510028X_inline1.png\"\/>\n                        <jats:tex-math>$v$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    can be obtained just by counting walks of each length from\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S096354832510028X_inline2.png\"\/>\n                        <jats:tex-math>$v$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    to an individualized vertex. Our analysis also implies that almost all circulant graphs are compact in the sense of Tinhofer, that is, their polytops of fractional automorphisms are integral. Finally, we show that a canonical Cayley representation can be constructed for almost all circulant graphs by the more powerful 2-dimensional Weisfeiler\u2013Leman algorithm.\n                  <\/jats:p>","DOI":"10.1017\/s096354832510028x","type":"journal-article","created":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T08:06:07Z","timestamp":1764144367000},"page":"178-206","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Canonization of a random circulant graph by counting walks"],"prefix":"10.1017","volume":"35","author":[{"given":"Oleg","family":"Verbitsky","sequence":"first","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8763-9533","authenticated-orcid":false,"given":"Maksim","family":"Zhukovskii","sequence":"additional","affiliation":[{"name":"University of Sheffield"}]}],"member":"56","published-online":{"date-parts":[[2025,11,26]]},"reference":[{"key":"S096354832510028X_ref31","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.11"},{"key":"S096354832510028X_ref6","volume-title":"Algorithmic Number Theory, Vol. 1: Efficient Algorithms","author":"Bach","year":"1996"},{"key":"S096354832510028X_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.09.033"},{"key":"S096354832510028X_ref44","unstructured":"[44] Verbitsky, O. and Zhukovskii, M. Canonization of a random graph by two matrix-vector multiplications. In 31st Annual European Symposium on Algorithms (ESA\u201923), volume 274 of LIPIcs, pp. 100:1, 100:13."},{"key":"S096354832510028X_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-76244-4"},{"key":"S096354832510028X_ref10","volume-title":"Random Circulant Matrices","author":"Bose","year":"2019"},{"key":"S096354832510028X_ref4","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.25"},{"key":"S096354832510028X_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"S096354832510028X_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/9781108553995"},{"key":"S096354832510028X_ref1","volume-title":"Introduction to Analytic Number Theory","author":"Apostol","year":"1998"},{"key":"S096354832510028X_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0147-6"},{"key":"S096354832510028X_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-021-01065-3"},{"key":"S096354832510028X_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3136-5"},{"key":"S096354832510028X_ref27","unstructured":"[27] Immerman, N. and Sengupta, R. (2019) The $k$ -dimensional Weisfeiler\u2013Leman algorithm. Technical report, arXiv:1907.09582."},{"key":"S096354832510028X_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"S096354832510028X_ref35","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611503014412"},{"key":"S096354832510028X_ref36","first-page":"241","volume-title":"Codes and Association Schemes, Volume 56 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Muzychuk","year":"1999"},{"key":"S096354832510028X_ref45","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-97-0566-5_23"},{"key":"S096354832510028X_ref46","first-page":"12","article-title":"The reduction of a graph to canonical form and the algebra which appears therein","volume":"9","author":"Weisfeiler","year":"1968","journal-title":"NTI Ser. 2"},{"key":"S096354832510028X_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895854"},{"key":"S096354832510028X_ref39","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(82)90104-5"},{"key":"S096354832510028X_ref28","doi-asserted-by":"publisher","DOI":"10.1145\/3333003"},{"key":"S096354832510028X_ref9","first-page":"33","article-title":"Distinguishing vertices of random graphs","volume":"13","author":"Bollob\u00e1s","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"S096354832510028X_ref34","doi-asserted-by":"publisher","DOI":"10.1214\/09-IMSCOLL514"},{"key":"S096354832510028X_ref40","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch87"},{"key":"S096354832510028X_ref14","volume-title":"Circulant Matrices","author":"Davis","year":"1994"},{"key":"S096354832510028X_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90016-0"},{"key":"S096354832510028X_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"S096354832510028X_ref13","unstructured":"[13] Chen, G. and Ponomarenko, I. (2019) Coherent Configurations. Central China Normal University Press, Wuhan. A draft version is available at http:\/\/www.pdmi.ras.ru\/\u223cinp\/ccNOTES.pdf."},{"key":"S096354832510028X_ref38","first-page":"1469","article-title":"On the WL-dimension of circulant graphs of prime power order","volume":"6","author":"Ponomarenko","year":"2023","journal-title":"Universitext"},{"key":"S096354832510028X_ref8","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.315.868"},{"key":"S096354832510028X_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90049-3"},{"key":"S096354832510028X_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80068-0"},{"key":"S096354832510028X_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(88)90054-7"},{"key":"S096354832510028X_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-024-00255-2"},{"key":"S096354832510028X_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"S096354832510028X_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00324-5"},{"key":"S096354832510028X_ref37","doi-asserted-by":"publisher","DOI":"10.1137\/15M1049622"},{"key":"S096354832510028X_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02175828"},{"key":"S096354832510028X_ref47","unstructured":"[47] Wu, Y. and Ponomarenko, I. (2024) On the Weisfeiler\u2013Leman dimension of circulant graphs. Technical report, arxiv.org\/abs\/2406.15822."},{"key":"S096354832510028X_ref30","unstructured":"[30] Kriege, N. M. (2022) Weisfeiler and Leman go walking: Random walk kernels revisited. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022 (NeurIPS\u201922)."},{"key":"S096354832510028X_ref42","doi-asserted-by":"publisher","DOI":"10.1007\/BF02240204"},{"key":"S096354832510028X_ref21","first-page":"189","article-title":"Characterization of cyclotomic schemes and normal Schur rings over a cyclic group","volume":"14","author":"Evdokimov","year":"2003","journal-title":"St. Petersbg. Math. J."},{"key":"S096354832510028X_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9686-0"},{"key":"S096354832510028X_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-012-0156-3"},{"key":"S096354832510028X_ref19","doi-asserted-by":"publisher","DOI":"10.1090\/S1061-0022-04-00833-7"},{"key":"S096354832510028X_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90047-4"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354832510028X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T08:53:44Z","timestamp":1771404824000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354832510028X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,26]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["S096354832510028X"],"URL":"https:\/\/doi.org\/10.1017\/s096354832510028x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,26]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}