Half-graphs, other non-stable degree sequences, and the switch Markov chain

D\'aniel Solt\'esz; Ervin Gy\H{o}ri; Istv\'an Mikl\'os; P\'eter L. Erd\H{o}s; Tam\'as R\'obert Mezei

REVIEW 2 major objections 4 minor 23 references

Half-graphs, other non-stable degree sequences, and the switch Markov chain

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For any fixed k, every bipartite degree sequence within $\ell^1$-distance $2k$ of the half-graph sequence is rapidly mixed by the switch Markov chain, despite the family failing $P$-stability.

desk verdict A real advance in the P-stability/rapid-mixing question, but the central buffer lemma has a duplicated case that must be fixed before Theorem 1.7 is accepted. read the letter →

arxiv 1909.02308 v2 pith:WU4ADCXD submitted 2019-09-05 math.CO cs.DM

Péter L. Erdős , Ervin Győri , Tamás Róbert Mezei , István Miklós , Dániel Soltész This is my paper · ORCID

classification math.COcs.DM MSC 05C0705C8005C8560J10

keywords switchMarkovchainrapidmixingdegreesequencehalf-graphP-stabilityTyshkevichdecompositioncanonicalpathsbipartitegraphs

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks when the switch Markov chain, the standard swap-based walk for sampling graphs with a prescribed degree sequence, can be guaranteed to mix quickly. Previous rapid-mixing results were captured by $P$-stability, a condition that compares the number of graphs realizing a degree sequence with the number realizing nearby sequences; every previously known rapidly mixing region was $P$-stable. The paper establishes that this condition is not necessary: for any fixed $k$, all bipartite degree sequences within $\ell^1$-distance $2k$ of the half-graph degree sequence $h_0(n)$ are rapidly mixing, with explicit bound $\tau(\epsilon)=O(n^8 \log \epsilon^{-1})$. It also shows that the class $H_k$ of sequences obtained by subtracting $k$ from the two extreme degrees is not $P$-stable, so these new rapidly mixing sequences genuinely lie beyond the old boundary. The proof works by representing each realization as a flow in a triangular network relative to the half-graph and moving a constant-width buffer across the two color classes.

What carries the argument

The central objects are the half-graph degree sequence $h_0(n)$ and its unique realization $H_0(n)$. The argument's engine is a flow representation: any realization $G$ of a nearby degree sequence differs from $H_0(n)$ in a sparse error graph, and orienting that difference along the threshold directions makes it a unit-capacity integer flow in a triangular network; sources and sinks are prescribed by the degree perturbation. To connect two realizations $X,Y$, the canonical path moves a buffer of constant width across the vertices, and the buffer lemma guarantees, via an auxiliary network and a flow-cut condition, an intermediate realization $T$ whose left window matches $Y$ and whose right window matches $X$. Short switch sequences between milestones come from a swap-distance bound, and each milestone receives an encoding, another realization plus two left-compressed constant-size subgraphs and the buffer position, from which the endpoints $X,Y$ can be reconstructed. For the non-stability direction, type matrices $P_k$ track how partial $k$-flows extend one vertex at a time; their primitivity and Perron-Frobenius eigenvalues give the exponential count of realizations of $h_k(n)$.

What would settle it

Exhaustively enumerate all degree sequences in $B_{2k}(h_0(n))$ for small $n$ and $k$, enumerate every pair of realizations $X,Y$, and for each buffer position $i$ with $z=2k+\lceil\sqrt{2k+1}\rceil$ search for a realization $T$ whose induced subgraph on $U_i$ equals that of $Y$ and whose induced subgraph on $U_{i+z}$ equals that of $X$; a single pair for which no such $T$ exists refutes Lemma 5.1 and with it Theorem 1.7.

Watch

Extended reading notes

Core claim

Define $h_0(n)=(1,2,\ldots,n;\,n,\ldots,2,1)$, the degree sequence whose unique bipartite realization is the half-graph $H_0(n)$, and let $B_{2k}(H_0)$ be the set of bipartite degree sequences whose $\ell^1$-distance from some $h_0(n)$ is at most $2k$. The main theorem states that for every fixed $k$, the switch Markov chain on every degree sequence in $B_{2k}(H_0)$ is rapidly mixing, with mixing time $\tau(\epsilon)=O(n^8 \log \epsilon^{-1})$. The paper exhibits this as a non-trivial family of degree sequences that are not $P$-stable yet mix in polynomial time: the class $H_k=\{h_0(n)-k\cdot 1_{a_1}-k\cdot 1_{b_n}\}$ is proved not $P$-stable for every $k$, by counting realizations via type matrices whose dominant eigenvalues grow with $k$. The paper also connects the example to Tyshkevich decompositions, shows that compositions of nontrivial bipartite factors are never $P$-stable, and pulls the rapid-mixing family back to unconstrained simple graphs through the split-graph correspondence.

Load-bearing premise

The load-bearing premise is that a buffer graph always exists: for any two realizations $X$ and $Y$ of a degree sequence inside the ball and any buffer position, there is a third realization $T$ whose left part coincides with $Y$ and whose right part coincides with $X$ (Lemma 5.1); the proof of that lemma is a flow-cut argument, with the small base case $k=z=1$ asserted as manually checked, and if the lemma fails for some sequence, the polynomial mixing bound no longer follows.

Editorial extensions

If this is right

Every degree sequence in $B_{2k}(H_0)$ has switch-chain mixing time $O(n^8 \log \epsilon^{-1})$ for fixed $k$, so uniform random sampling of these graphs is guaranteed to be efficient.
Because $H_k \subset S_{2k}(H_0)$ is not $P$-stable, $P$-stability is not a necessary condition for rapid mixing of the switch Markov chain.
The rapid-mixing result pulls back under the split-graph correspondence to a family of unconstrained simple graph degree sequences, so the phenomenon is not an artifact of the bipartite model.
The proof works verbatim when $k \le c\sqrt{\log n}$, so the rapidly mixing ball can grow slowly with $n$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the buffer lemma extends to other sequences with a unique or near-unique staircase realization and an associated triangular flow network, the same canonical-path construction should yield further non-$P$-stable rapidly mixing families; the paper's Conjecture 7.1 about the class $H_{\le k}$ is the natural target.
The exponential realization counts for $h_k(n)$ suggest a general phenomenon: perturbing the two extremes of a uniquely realizable degree sequence built from Tyshkevich composition produces exponentially many realizations, so non-$P$-stability may be common in neighborhoods of such sequences.
Because the flow representation is acyclic and threshold-based, an analogous buffer argument may work for directed degree sequences represented by Ferrers-like matrices, yielding rapidly mixing non-$P$-stable directed examples.
A computational check of the buffer lemma for small $k$ and $n$ would show whether the asymptotic $n^8$ bound is loose and whether the hand-checked $k=z=1$ case hides any obstruction.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Zoli, you should know: this paper proves a real first. It gives a non-trivial family of bipartite degree sequences, the radius-2k ball around the half-graph H0, that are not P-stable and yet the switch Markov chain is rapidly mixing, with an explicit O(n^8 log 1/epsilon) bound. The proof technique is genuinely new: realizations are represented as k-flows in a directed grid, and a left-to-right buffer is used to build canonical paths with reconstructible encodings. That alone is worth a referee's time.

The non-stability part is also solid. The type-matrix recursion and Perron-Frobenius comparison in Section 6 are clean, and Lemma 6.9 is plausible as written.

But there is a load-bearing gap. Lemma 5.1, which produces the buffer realization and is the engine of Theorem 1.7, has a four-case verification in which Case 2 is printed identical to Case 1. The missing case, |S cap (A_{i+z}\A_i)| >= z-k and |S cap (B_{i+z}\B_i)| <= k, is exactly the symmetric opposite of Case 1 and is never checked. Without the cut condition (4) for those S, the buffer flow W is not shown to exist, and the canonical path system collapses. I do not think the lemma is false; the network is close enough to symmetric that swapping A and B may carry the argument through. But 'may' is not a proof, and Theorem 1.7 is conditional on that repair.

Two smaller issues: the k=z=1 base case is only asserted as 'manually checked' with no details, and the introduction claims h0(n)-1a1-1bn has Theta((1+sqrt5)/2)^n realizations while Corollary 6.2 correctly gives Theta((3+sqrt5)/2)^n. The first is minor since the construction uses z=3k+1; the second is a confusing typo.

Who this is for: anyone working on graph sampling, stability notions, or the Kannan-Tetali-Vempala question. The paper is honest about prior examples and gives a meaningful family where P-stability fails but mixing is polynomial. If Lemma 5.1 gets fixed, it is an important step.

My recommendation: send this to a serious referee. The central idea deserves scrutiny, and the gap is probably repairable. I would not desk-reject it; I would ask the authors to repair the case split and fix the growth-constant typo before acceptance.

Referee Report

2 major / 4 minor

Summary. The paper studies the switch Markov chain on bipartite degree sequences in a fixed-radius neighborhood of the half-graph degree sequence h0(n). It introduces a flow representation of realizations (Corollary 4.3), then constructs a canonical path system with a moving buffer to prove Theorem 1.7: for every fixed k, the switch chain is rapidly mixing on B2k(H0), with an explicit bound tau(epsilon) = O(n^8 log epsilon^{-1}). The proof relies on Lemma 5.1, which asserts the existence of a buffer realization T_{X,Y}[i+1,i+z] matching Y on the left window and X on the right window. The paper also proves Theorem 1.9, that the class Hk = {h0(n) - k*1_{a1} - k*1_{bn}} is not P-stable for any k, using type matrices, primitivity, and a Perron-Frobenius eigenvalue comparison. Sections 2 and 7 connect the construction to Tyshkevich decompositions, strong stability, and possible generalizations.

Significance. If Theorem 1.7 is established, the paper provides the first explicit family of bipartite degree sequences that are not P-stable yet on which the switch Markov chain mixes rapidly, with an explicit polynomial bound and an underlying canonical path system. The flow representation of realizations is clean and the non-stability proof via type matrices and primitive matrices is elegant and appears correct. The contribution is significant for the line of work on P-stability and rapid mixing of switch chains, because it shows that non-stability is not an obstruction to rapid mixing. The main reservation is that the central rapid-mixing proof depends on Lemma 5.1, whose printed case analysis contains a duplicated case and leaves a symmetric region untreated; this is likely repairable but is currently a genuine gap in the proof of Theorem 1.7.

major comments (2)

[Section 5.1, Lemma 5.1] The case analysis verifying the cut condition (4) is incomplete. Case 2 is printed exactly as Case 1: both require |S ∩ (A_{i+z}\A_i)| ≤ k and |S ∩ (B_{i+z}\B_i)| ≥ z−k. The symmetric region |S ∩ (A_{i+z}\A_i)| ≥ z−k and |S ∩ (B_{i+z}\B_i)| ≤ k is never treated. Since condition (4) is the only mechanism proving existence of the buffer flow W, and W is used to construct every milestone T_{X,Y}[i+1,i+z] in the canonical path system, this gap directly affects Theorem 1.7. The missing case appears repairable by swapping the roles of A and B in the Case 1 counting argument, but as printed the proof is incomplete.
[Section 5.1, Lemma 5.1] The statement 'The case k=z=1 can be manually checked at this point' is asserted without any verification, and the claim that for k=1 even z=1 is sufficient is not demonstrated. Because the construction later uses z=3k+1, this is not the main obstruction to Theorem 1.7, but the lemma as stated is not fully proved; the authors should either supply the check or restrict the statement to the range actually used.

minor comments (4)

[Section 5.1] The reduction 'Without loss of generality d ∈ S2k(H0)' is not explicitly justified. A sequence in B2k(H0) may have distance 2j for some j<k; the proof should state that it applies to S2j with j≤k and that the constants depending on k provide a uniform bound over the ball.
[Section 5.2, Lemma 5.2] In the proof, 'the at most k−k edges entering U_{i+1} and leaving U_{i+z+1}' appears to contain a typo; presumably this should read 'the at most k edges' or 'O(k) edges'.
[Section 7.2] The statement that Ψ^{-1} 'induces an isomorphism between the Markov-graphs M(d) and M(Ψ^{-1}(d))' is too strong: the unconstrained switch chain contains additional switches involving edges of the clique, so the image of the bipartite Markov graph is generally a proper subgraph of the simple Markov graph. The load comparison argument only needs the image to be a subgraph, which is sufficient, but the wording should be corrected.
[Section 6, Lemma 6.9] The inequality M(n) ≥ (M(1))^n is used without comment. It follows from nonnegativity of P_{k+1} and the fact that a walk of length n that stays within S in each of its n steps is one particular walk counted in (P_{k+1}^n)_{ij}; stating this explicitly would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the rapid-mixing theorem is derived from a constructed path system, and the cited self-results are independent published lemmas, not assumptions of the conclusion.

full rationale

The paper's central claim (Theorem 1.7) is proved by explicitly constructing canonical paths between arbitrary realizations using a buffer flow (Lemma 5.1), bounding the load via encodings (Lemma 5.4), and applying Sinclair's lemma; none of these steps assumes rapid mixing or P-stability. The family B2k(H0) is defined independently of the mixing-time conclusion, and non-P-stability of Hk is established separately by counting flows and comparing Perron roots of type matrices. Self-citations appear (Theorem 2.5 from [9], Lemma 5.2 from [5]), but they are used as published external facts about decomposition and swap distance, not as assumptions containing Theorem 1.7; hence they are not load-bearing circularity. The only identified weakness is internal to Lemma 5.1: its four-case cut verification prints Case 2 identical to Case 1 and leaves the symmetric region unexamined, and the k=z=1 base case is asserted without detail. This is a proof gap, not a circular reduction: Lemma 5.1 is not derived from the theorem it supports. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces mathematical definitions such as the flow representation, the buffer, and the type matrix, but no unexplained physical or structural entities. No parameters are fitted to data; the integer k in the theorems is a fixed radius parameter, not a fitted constant. The proofs rely on the standard external theorems listed above.

assumptions (6)

domain assumption Tyshkevich decomposition theorem for splitted bipartite graphs (Theorem 2.3, adapted from [9] and [21]): every splitted bipartite degree sequence decomposes uniquely into indecomposable components, and switches respect the components.
The paper relies on this external structural theorem in Section 2 to explain the half-graph examples and to motivate the flow-buffer approach; it is not proved in this paper.
standard math Sinclair's canonical path bound (Lemma 3.5, from [19]): if a canonical path system has load rho and maximum path length l, the mixing time is at most rho * l * (log state space size + log epsilon inverse).
This is the backbone of the rapid-mixing proof in Section 5 and is quoted from the literature.
standard math Menger's theorem and max-flow min-cut, used in Lemma 5.1 to assert that the buffer flow W exists whenever all cut conditions hold.
Invoked explicitly in the proof of Lemma 5.1, the load-bearing existence step of the canonical path construction.
standard math Perron-Frobenius theory for primitive nonnegative matrices, used in Lemma 6.9 to compare largest eigenvalues of the type matrices P_k.
The proof of Theorem 1.9 depends on the strict growth of the Perron root, which follows from this standard theorem.
domain assumption Swap-distance bound of Erdos, Kiraly, and Miklos [5], quoted as Lemma 5.2, stating that two realizations can be connected by at most half the size of their symmetric difference in switches.
Used to connect consecutive milestones in the canonical path system; it is an external result not re-derived here.
domain assumption Bipartite graphicality constraint: a degree sequence e is only considered when the sums of degrees on the two color classes are equal, as imposed in Definition 1.6.
Implicit in defining B2k and S2k and in the flow representation; it restricts the perturbations considered.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Half-graphs, other non-stable degree sequences, and the switch Markov chain." pith.science (2026). https://pith.science/paper/WU4ADCXD

@misc{pith2026190902308,
  author       = {Pith},
  title        = {Pith review of: Half-graphs, other non-stable degree sequences, and the switch Markov chain},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WU4ADCXD}},
  note         = {Machine review of arXiv:1909.02308}
}

abstract

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.

Figures

Figures reproduced from arXiv: 1909.02308 by the authors.

**Figure 2.** The unique realization H0(n) of h0(n) is isomorphic to the half-graph. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** The flow representation of a realization of a degree seque [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: A realization along γX,Y and the main part of the associated encoding. Let Ai = An \ Ai and Bi = Bn \ Bi . Also, let Ui = Ai ∪ Bi and Ui = Ai ∪ Bi . The following lemma shows the existence of a suitable buffer which can be used to interface two different realizations a…

**Figure 5.** Figure 5: Roadmap of the switch sequence between X and Y . The existence of a short switch sequence between milestones of the sequence is guaranteed by Lemma 5.2. Lemma 5.2. There is a switch sequence of length O(k 2 ) that connects TX,Y [i + 1, i + z] to TX,Y [i + 1, i + z + 1]…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

[1]

Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices

Amanatidis, G., and Kleer, P. Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , Proceedings. Society for Industrial and Applied Mathematics, Jan. 2019, pp. 966–985

work page 2019
[2]

Sampling Regular Graphs and a Peer-to- Peer Network

Cooper, C., Dyer, M., and Greenhill, C. Sampling Regular Graphs and a Peer-to- Peer Network. Combinatorics, Probability and Computing 16 , 4 (July 2007), 557–593

work page 2007
[3]

Probability: Theory and Examples

Durrett, R. Probability: Theory and Examples . Cambridge University Press, Aug. 2010. Google-Books-ID: evbGTPhuvSoC

work page 2010
[4]

L., Greenhill, C., Mezei, T

Erd˝os, P. L., Greenhill, C., Mezei, T. R., Mikl ´os, I., Solt ´ esz, D., and Soukup, L. The mixing time of switch Markov chains: a uniﬁed approach. arXiv:1903.06600 [cs, math] (Nov. 2019). arXiv: 1903.06600

arXiv 1903
[5]

L., Kir ´aly, Z., and Mikl ´os, I

Erd˝os, P. L., Kir ´aly, Z., and Mikl ´os, I. On the Swap-Distances of Diﬀerent Real- izations of a Graphical Degree Sequence. Combinatorics, Probability and Computing 22 , 3 (May 2013), 366–383

work page 2013
[6]

L., Kiss, S

Erd˝os, P. L., Kiss, S. Z., Mikl ´os, I., and Soukup, L. Approximate Counting of Graphical Realizations. PLOS ONE 10 , 7 (July 2015), e0131300

work page 2015
[7]

L., Mezei, T

Erd˝os, P. L., Mezei, T. R., Mikl ´os, I., and Solt ´ esz, D. Eﬃciently sampling the realizations of bounded, irregular degree sequences of bip artite and directed graphs. PLOS ONE 13 , 8 (Aug. 2018), e0201995

work page 2018
[8]

L., Mikl ´os, I., and Toroczkai, Z

Erd˝os, P. L., Mikl ´os, I., and Toroczkai, Z. A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Join t Degree Matrix. SIAM Journal on Discrete Mathematics 29 , 1 (Jan. 2015), 481–499

work page 2015

Show all 23 references

[9]

L., Mikl ´os, I., and Toroczkai, Z

Erd˝os, P. L., Mikl ´os, I., and Toroczkai, Z. New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling. Combinatorics, Probability and Computing 27 , 2 (Mar. 2018), 186–207. 26

2018
[10]

F¨oldes, S., and Hammer, P. L. Split graphs. In Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louis iana State Univ., Baton Rouge, La., 1977) (1977), pp. 311–315. Congressus Numerantium, No. XIX

1977
[11]

Mixing time of the switch Markov chain and stable degree sequences

Gao, P., and Greenhill, C. Mixing time of the switch Markov chain and stable degree sequences. arXiv:2003.08497 [math] (Apr. 2020). arXiv: 2003.08497

2003 arXiv
[12]

The switch Markov chain for sampling irregular graphs and digraphs

Greenhill, C., and Sfragara, M. The switch Markov chain for sampling irregular graphs and digraphs. Theoretical Computer Science 719 (Apr. 2018), 1–20

2018
[13]

Greenhill, C. S. A Polynomial Bound on the Mixing Time of a Markov Chain for Sampling Regular Directed Graphs. Electronic Journal of Combinatorics 18 (2011)

2011
[14]

L., and Simeone, B

Hammer, P. L., and Simeone, B. The splittance of a graph. Combinatorica 1 , 3 (Sept. 1981), 275–284

1981
[15]

D., and Sinclair, A

Jerrum, M., McKay, B. D., and Sinclair, A. When is a Graphical Sequence Sta- ble? University of Edinburgh, Department of Computer Science, 1 989. Google-Books-ID: Iv3zHgAACAAJ
[16]

Fast uniform generation of regular graphs

Jerrum, M., and Sinclair, A. Fast uniform generation of regular graphs. Theoretical Computer Science 73 , 1 (June 1990), 91–100

1990
[17]

Simple Markov-chain algorithms for gen- erating bipartite graphs and tournaments

Kannan, R., Tetali, P., and Vempala, S. Simple Markov-chain algorithms for gen- erating bipartite graphs and tournaments. Random Structures & Algorithms 14 , 4 (1999), 293–308

1999
[18]

L., and Soukup, L

Mikl´os, I., Erd ˝os, P. L., and Soukup, L. Towards random uniform sampling of bipartite graphs with given degree sequence. Electronic Journal of Combinatorics 20 , 1 (2013), Paper 16, 51

2013
[19]

Improved Bounds for Mixing Rates of Markov Chains and Multic ommodity Flow

Sinclair, A. Improved Bounds for Mixing Rates of Markov Chains and Multic ommodity Flow. Combinatorics, Probability and Computing 1 , 4 (Dec. 1992), 351–370

1992
[20]

Algorithms for Random Generation and Counting: A Markov Chain Ap- proach

Sinclair, A. Algorithms for Random Generation and Counting: A Markov Chain Ap- proach. Progress in Theoretical Computer Science. Birkh¨ auser Ba sel, 1993

1993
[21]

Decomposition of graphical sequences and unigraphs

Tyshkevich, R. Decomposition of graphical sequences and unigraphs. Discrete Mathe- matics 220 , 1 (June 2000), 201–238

2000
[22]

I., and Chernyak, A

Tyshkevich, R. I., and Chernyak, A. A. Decomposition of graphs. Cybernetics 21, 2 (Mar. 1985), 231–242

1985
[23]

On Counting Perfect Matchings in General Graphs

ˇStefankoviˇc, D., Vigoda, E., and Wilmes, J. On Counting Perfect Matchings in General Graphs. In LATIN 2018: Theoretical Informatics (Cham, 2018), M. A. Bender, M. Farach-Colton, and M. A. Mosteiro, Eds., Lecture Notes in Computer Science, Springer International Publishing, p...

2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices

Amanatidis, G., and Kleer, P. Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , Proceedings. Society for Industrial and Applied Mathematics, Jan. 2019, pp. 966–985

work page 2019

[2] [2]

Sampling Regular Graphs and a Peer-to- Peer Network

Cooper, C., Dyer, M., and Greenhill, C. Sampling Regular Graphs and a Peer-to- Peer Network. Combinatorics, Probability and Computing 16 , 4 (July 2007), 557–593

work page 2007

[3] [3]

Probability: Theory and Examples

Durrett, R. Probability: Theory and Examples . Cambridge University Press, Aug. 2010. Google-Books-ID: evbGTPhuvSoC

work page 2010

[4] [4]

L., Greenhill, C., Mezei, T

Erd˝os, P. L., Greenhill, C., Mezei, T. R., Mikl ´os, I., Solt ´ esz, D., and Soukup, L. The mixing time of switch Markov chains: a uniﬁed approach. arXiv:1903.06600 [cs, math] (Nov. 2019). arXiv: 1903.06600

arXiv 1903

[5] [5]

L., Kir ´aly, Z., and Mikl ´os, I

Erd˝os, P. L., Kir ´aly, Z., and Mikl ´os, I. On the Swap-Distances of Diﬀerent Real- izations of a Graphical Degree Sequence. Combinatorics, Probability and Computing 22 , 3 (May 2013), 366–383

work page 2013

[6] [6]

L., Kiss, S

Erd˝os, P. L., Kiss, S. Z., Mikl ´os, I., and Soukup, L. Approximate Counting of Graphical Realizations. PLOS ONE 10 , 7 (July 2015), e0131300

work page 2015

[7] [7]

L., Mezei, T

Erd˝os, P. L., Mezei, T. R., Mikl ´os, I., and Solt ´ esz, D. Eﬃciently sampling the realizations of bounded, irregular degree sequences of bip artite and directed graphs. PLOS ONE 13 , 8 (Aug. 2018), e0201995

work page 2018

[8] [8]

L., Mikl ´os, I., and Toroczkai, Z

Erd˝os, P. L., Mikl ´os, I., and Toroczkai, Z. A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Join t Degree Matrix. SIAM Journal on Discrete Mathematics 29 , 1 (Jan. 2015), 481–499

work page 2015