Canonical labelling of sparse random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912054069166080 |
|---|---|
| author | Verbitsky, Oleg Zhukovskii, Maksim |
| author_facet | Verbitsky, Oleg Zhukovskii, Maksim |
| contents | We show that if $p=O(1/n)$, then the Erdős-Rényi random graph $G(n,p)$ with high probability admits a canonical labeling computable in time $O(n\log n)$. Combined with the previous results on the canonization of random graphs, this implies that $G(n,p)$ with high probability admits a polynomial-time canonical labeling whatever the edge probability function $p$. Our algorithm combines the standard color refinement routine with simple post-processing based on the classical linear-time tree canonization. Noteworthy, our analysis of how well color refinement performs in this setting allows us to complete the description of the automorphism group of the 2-core of $G(n,p)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_18109 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Canonical labelling of sparse random graphs Verbitsky, Oleg Zhukovskii, Maksim Discrete Mathematics Combinatorics We show that if $p=O(1/n)$, then the Erdős-Rényi random graph $G(n,p)$ with high probability admits a canonical labeling computable in time $O(n\log n)$. Combined with the previous results on the canonization of random graphs, this implies that $G(n,p)$ with high probability admits a polynomial-time canonical labeling whatever the edge probability function $p$. Our algorithm combines the standard color refinement routine with simple post-processing based on the classical linear-time tree canonization. Noteworthy, our analysis of how well color refinement performs in this setting allows us to complete the description of the automorphism group of the 2-core of $G(n,p)$. |
| title | Canonical labelling of sparse random graphs |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2409.18109 |