Canonical labelling of random regular graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908841265856512 |
|---|---|
| author | Isaev, Mikhail Makai, Tamás McKay, Brendan Pralat, Pawel Tan, Jane Zhukovskii, Maksim |
| author_facet | Isaev, Mikhail Makai, Tamás McKay, Brendan Pralat, Pawel Tan, Jane Zhukovskii, Maksim |
| contents | We prove that whenever $d=d(n)\to\infty$ and $n-d\to\infty$ as $n\to\infty$, then with high probability for any non-trivial initial colouring, the colour refinement algorithm distinguishes all vertices of the random regular graph $\mathcal{G}_{n,d}$. This, in particular, implies that with high probability $\mathcal{G}_{n,d}$ admits a canonical labelling computable in time $O(\min\{n^ω,nd^2+nd\log n\})$, where $ω<2.372$ is the matrix multiplication exponent. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17567 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Canonical labelling of random regular graphs Isaev, Mikhail Makai, Tamás McKay, Brendan Pralat, Pawel Tan, Jane Zhukovskii, Maksim Combinatorics Discrete Mathematics Probability We prove that whenever $d=d(n)\to\infty$ and $n-d\to\infty$ as $n\to\infty$, then with high probability for any non-trivial initial colouring, the colour refinement algorithm distinguishes all vertices of the random regular graph $\mathcal{G}_{n,d}$. This, in particular, implies that with high probability $\mathcal{G}_{n,d}$ admits a canonical labelling computable in time $O(\min\{n^ω,nd^2+nd\log n\})$, where $ω<2.372$ is the matrix multiplication exponent. |
| title | Canonical labelling of random regular graphs |
| topic | Combinatorics Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2602.17567 |