Diameters and mixing times for giant components of random graphs with given degrees
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.16511
curl -X POST /api/v1/records/arxiv/2605.16511/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.16511/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'