The diameter of random Schreier graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909597254549504 |
|---|---|
| author | Dona, Daniele Sabatini, Luca |
| author_facet | Dona, Daniele Sabatini, Luca |
| contents | We give a combinatorial proof of the following theorem. Let $G$ be any finite group acting transitively on a set of cardinality $n$. If $S \subseteq G$ is a random set of size $k$, with $k \geq (\log n)^{1+\varepsilon}$ for some $\varepsilon >0$, then the diameter of the corresponding Schreier graph is $O(\log_k n)$ with high probability. Except for the implicit constant, this result is the best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_16733 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The diameter of random Schreier graphs Dona, Daniele Sabatini, Luca Combinatorics Group Theory Primary 05C89, 20F69 We give a combinatorial proof of the following theorem. Let $G$ be any finite group acting transitively on a set of cardinality $n$. If $S \subseteq G$ is a random set of size $k$, with $k \geq (\log n)^{1+\varepsilon}$ for some $\varepsilon >0$, then the diameter of the corresponding Schreier graph is $O(\log_k n)$ with high probability. Except for the implicit constant, this result is the best possible. |
| title | The diameter of random Schreier graphs |
| topic | Combinatorics Group Theory Primary 05C89, 20F69 |
| url | https://arxiv.org/abs/2406.16733 |