Diameters and mixing times for giant components of random graphs with given degrees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916017844781056 |
|---|---|
| author | Addario-Berry, Louigi Reed, Bruce Yap, Corrine |
| author_facet | Addario-Berry, Louigi Reed, Bruce Yap, Corrine |
| contents | A sequence $D = \{d_1,...d_n\}$ is a feasible degree sequence if there is a graph on $\{1,...,n\}$ such that $i$ has degree $d_i$. For such a sequence, $G(D)$ is a graph chosen uniformly at random from those with the given degree sequence. We consider sequences $\{D_\ell\}_{\ell \geq 1}$ of feasible degree sequences which have a giant component. We show that with high probability this giant component is unique, and bound its diameter and the mixing time of the random walk on it. We also bound the size and diameter of the other components and show that many of these bounds are tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_16511 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Diameters and mixing times for giant components of random graphs with given degrees Addario-Berry, Louigi Reed, Bruce Yap, Corrine Combinatorics Probability A sequence $D = \{d_1,...d_n\}$ is a feasible degree sequence if there is a graph on $\{1,...,n\}$ such that $i$ has degree $d_i$. For such a sequence, $G(D)$ is a graph chosen uniformly at random from those with the given degree sequence. We consider sequences $\{D_\ell\}_{\ell \geq 1}$ of feasible degree sequences which have a giant component. We show that with high probability this giant component is unique, and bound its diameter and the mixing time of the random walk on it. We also bound the size and diameter of the other components and show that many of these bounds are tight. |
| title | Diameters and mixing times for giant components of random graphs with given degrees |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2605.16511 |