Geodesic
Rate of convergence of the short cycle distribution in random regular graphs generated by pegging
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/133
Classification : 05C80, 05C38
Mots-clés : pegging algorithm 
@article{10_37236_133,
     author = {Pu Gao and Nicholas Wormald},
     title = {Rate of convergence of the short cycle distribution in random regular graphs generated by pegging},
     journal = {The electronic journal of combinatorics},
     year = {2009},
     volume = {16},
     number = {1},
     doi = {10.37236/133},
     zbl = {1215.05160},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/133/}
}
TY  - JOUR
AU  - Pu Gao
AU  - Nicholas Wormald
TI  - Rate of convergence of the short cycle distribution in random regular graphs generated by pegging
JO  - The electronic journal of combinatorics
PY  - 2009
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/133/
DO  - 10.37236/133
ID  - 10_37236_133
ER  - 
%0 Journal Article
%A Pu Gao
%A Nicholas Wormald
%T Rate of convergence of the short cycle distribution in random regular graphs generated by pegging
%J The electronic journal of combinatorics
%D 2009
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/133/
%R 10.37236/133
%F 10_37236_133
Pu Gao; Nicholas Wormald. Rate of convergence of the short cycle distribution in random regular graphs generated by pegging. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/133

Cité par Sources :