Problemet med effektiv provtagning från en uppsättning (oriktade, eller riktade) grafer med en given grad sekvens har många tillämpningar. En metod för detta problem använder en enkel Markovkedja, som vi kallar switchkedjan, för att utföra provtagningen. Switchkedjan är känd för att snabbt blandas för regelbundna grader sekvenser, både i oriktad och riktad inställning. Vi bevisar att omkopplaren kedja för oriktade grafer snabbt blandas för någon grad sekvens med minsta grad minst 1 och med maximal grad d max som uppfyller 3 ≤ d max ≤ 1 3 ⁄ M, där M är summan av grader. Den erhållna blandningstiden är endast en faktor n större än den som fastställts i det vanliga fallet, där n är antalet hörn. Vårt resultat täcker ett brett spektrum av grader sekvenser, inklusive power-law densitetsbundna grafer med parameter γ > 5/2 och tillräckligt många kanter. För riktade gradsekvenser så att omkopplarkedjan är irreducerbar, bevisar vi att omkopplaren snabbt blandas när alla in-grader och ut-grader är positiva och avgränsade ovan av ε m, där m är antalet bågar, och inte alla in-grader och ut-grader lika med 1. Den blandningstid som erhålls i det riktade fallet är en ordning av m 2 större än den som fastställts i det vanliga fallet.
I det senare dokumentet REF beaktas endast gradsekvenser för vilka kantbrytaren Markov-kedjan är irreducerbar för en given gradsekvens.
The switch Markov chain for sampling irregular graphs and digraphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}