2019/05/08 by Moritz Lichter, Lichter, Moritz, Ilia Ponomarenko +3 · 2 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.1905.03008
openalex publication_date 2019/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the 2-dimensional Weisfeiler-Leman algorithm stabilizes n-vertex\ngraphs after at most O(n log n) iterations. This implies that if such graphs\nare distinguishable in 3-variable first order logic with counting, then they\ncan also be distinguished in this logic by a formula of quantifier depth at\nmost O(n log n).\n For this we exploit a new refinement based on counting walks and argue that\nits iteration number differs from the classic Weisfeiler-Leman refinement by at\nmost a logarithmic factor. We then prove matching linear upper and lower bounds\non the number of iterations of the walk refinement. This is achieved with an\nalgebraic approach by exploiting properties of semisimple matrix algebras. We\nalso define a walk logic and a bijective walk pebble game that precisely\ncorrespond to the new walk refinement.\n