go-v.orgdoi

Rate of Convergence of the Short Cycle Distribution in Random Regular Graphs Generated by Pegging

Pu Gao, Nicholas Wormald · The Electronic Journal of Combinatorics · 2009

  • DOI 10.37236/133
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2009

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009

Abstract

The pegging algorithm is a method of generating large random regular graphs beginning with small ones. The $\epsilon$-mixing time of the distribution of short cycle counts of these random regular graphs is the time at which the distribution reaches and maintains total variation distance at most $\epsilon$ from its limiting distribution. We show that this $\epsilon$-mixing time is not $o(\epsilon^{-1})$. This demonstrates that the upper bound $O(\epsilon^{-1})$ proved recently by the authors is essentially tight.

Open the resolved locator · 10.37236/133

Metadata licence: OpenAlex metadata (CC0)