Results on the switch chain, pair resamplings, three-row matrices, slices and exact sampling, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Total variation from a spectral gap — Lemma 1.1. If the eigenvalues of a symmetric Markov kernel on mean-zero functions lie in [0, 1 - gamma], its law after t steps is within (1/2) sqrt|Omega| exp(-gamma t) of uniform in total variation.
• The switch chain — Lemma 2.1. Switch neighbours have transition probability 1/(12 C(n,4)); I - P_d = L/(12 C(n,4)); the eigenvalues of P_d lie in [0,1].
• Connectivity of switches (after Havel) — Lemma 3.1. Any two simple graphs with the same degree vector are joined by switches, and the greedy prescription realizes every graphical degree vector.
• Pair fibers are slices — Lemma 4.1. A pair fiber is in bijection with the q-element subsets of its singletons.
• Comparison with switches — Lemma 5.2. h_a <= n^2 J_a for every pair a, the sum of the J_a is twice the switch Laplacian L, and H <= 2 n^2 L.
• From the operator inequality to mixing — Proposition 5.3. If H^2 >= H, then Var(f) <= 2 n^2 <f, Lf> and the mixing theorem follows.
• Polynomial mixing of the switch chain (OpenAI) — Theorem 5.4. For n >= 4 and every graphical degree vector, the switch chain has mixing time at most 2 n^8 and spectral gap at least 1/(24 n^2 C(n,4)).
• Fixed block sizes — Lemma 1.1. For independent uniform ordered partitions with prescribed block sizes, the variance of a sum of three functions of single blocks is at most twice the sum of their variances.
• Adjacent totals (Fu, Qin and Wang) — Lemma 2.1. Laws proportional to w_alpha(y) w_beta(s - y) with adjacent totals admit a coupling with Y_{s-1} <= Y_s <= Y_{s-1} + 1.
• Random block sizes — Proposition 2.2. For triples with law proportional to the product of w_{alpha_i}(x_i), the variance of b_1(x_1) + b_2(x_2) + b_3(x_3) is at most twice the sum of the variances.
• Three-row variance inequality (Fu, Qin and Wang; OpenAI) — Theorem 3.1. For a uniform binary matrix with three rows and prescribed margins, the variance of a sum of three row functions is at most twice the sum of their variances.
• Pair resamplings on a triple (OpenAI) — Theorem 4.1. H_T^2 >= H_T for every vertex triple T.
• Disjoint-pair interaction (OpenAI) — Proposition 1.1. 2 <h_a f, h_b f> >= 2 |g_{a,b} f|^2 - |R_{a,b} f|^2 - |R_{b,a} f|^2 for disjoint pairs a, b.
• Equality indicators on a slice (OpenAI) — Lemma 2.1. On a slice of the Boolean cube, the sum of the projections onto the centered equality indicators is at most (1/2) times the sum of I - tau_ij.
• Summed equality energy (OpenAI) — Corollary 2.2. For every pair a, the sum over disjoint b of |R_{a,b} f|^2 is at most the sum of |g_{a,b} f|^2.
• Positivity of the disjoint terms (OpenAI) — Corollary 3.1. The sum D of h_a h_b over ordered pairs of disjoint vertex pairs is positive semidefinite.
• Expansion of the square — Lemma 3.2. H^2 = (sum over triples of H_T^2) - (n - 3) H + D.
• The operator inequality H^2 >= H (OpenAI) — Theorem 3.3. The sum H of the pair resampling projections satisfies H^2 >= H.
• Residual mixtures — Lemma 1.1. If (1 - delta) p <= pi pointwise, then r = (pi - (1 - delta) p)/delta is a probability measure and (1 - delta) p + delta r = pi.
• Domination after t steps — Lemma 2.1. With delta = 2^-D, D = 4 C(n,2) + 10 and t = ceil(gamma_0^-1 (C(n,2) + 2D + 2)), the law after t steps satisfies (1 - delta) p_G <= 1/|Omega_d|.
• The chain in integers — Lemma 3.1. 12 C(n,4) P_d is a nonnegative integer matrix with row sums 12 C(n,4).
• Exact uniform sampling (OpenAI) — Theorem 4.1. A randomized algorithm with unbiased bits outputs an exactly uniform graph with a given degree vector, stops with probability one, and has expected polynomial bit cost.

Reading order

Read the lessons in order; each uses the notation and results of the previous ones.