Geodesic
Half-graphs, other non-stable degree sequences, and the switch Markov chain
Péter L. Erdős1 ; Ervin Győri1 ; Tamás Róbert Mezei2 ; István Miklós1 ; Dániel Soltész3
1Alfréd Rényi Institute of Mathematics, Budapest, Hungary
2Alfréd Rény Institute of Mathematics
3*Alfréd Rényi Institute of Mathematics, Budapest, Hungary
The electronic journal of combinatorics, Tome 28 (2021) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

One of the simplest methods of generating a random graph with a given degree sequence is provided by the Monte Carlo Markov Chain method using switches. The switch Markov chain converges to the uniform distribution, but generally the rate of convergence is not known. After a number of results concerning various degree sequences, rapid mixing was established for so-called P-stable degree sequences (including that of directed graphs), which covers every previously known rapidly mixing region of degree sequences. In this paper we give a non-trivial family of degree sequences that are not P-stable and the switch Markov chain is still rapidly mixing on them. This family has an intimate connection to Tyshkevich-decompositions and strong stability as well.
DOI : 10.37236/9652
Classification : 05C80, 05C07, 60J10, 68R10
Mots-clés : random graphs with a given degree sequence, Monte Carlo Markov chain method

Péter L. Erdős  1   ; Ervin Győri  1   ; Tamás Róbert Mezei  2   ; István Miklós  1   ; Dániel Soltész  3

1 Alfréd Rényi Institute of Mathematics, Budapest, Hungary
2 Alfréd Rény Institute of Mathematics
3 *Alfréd Rényi Institute of Mathematics, Budapest, Hungary 
@article{10_37236_9652,
     author = {P\'eter L. Erd\H{o}s and Ervin Gy\H{o}ri and Tam\'as R\'obert Mezei and Istv\'an Mikl\'os and D\'aniel Solt\'esz},
     title = {Half-graphs, other non-stable degree sequences, and the switch {Markov} chain},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {3},
     doi = {10.37236/9652},
     zbl = {1467.05241},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9652/}
}
TY  - JOUR
AU  - Péter L. Erdős
AU  - Ervin Győri
AU  - Tamás Róbert Mezei
AU  - István Miklós
AU  - Dániel Soltész
TI  - Half-graphs, other non-stable degree sequences, and the switch Markov chain
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9652/
DO  - 10.37236/9652
ID  - 10_37236_9652
ER  - 
%0 Journal Article
%A Péter L. Erdős
%A Ervin Győri
%A Tamás Róbert Mezei
%A István Miklós
%A Dániel Soltész
%T Half-graphs, other non-stable degree sequences, and the switch Markov chain
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9652/
%R 10.37236/9652
%F 10_37236_9652
Péter L. Erdős; Ervin Győri; Tamás Róbert Mezei; István Miklós; Dániel Soltész. Half-graphs, other non-stable degree sequences, and the switch Markov chain. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9652

Cité par Sources :