1 Introduction↩︎

Let \(G=(V,E)\) be a strongly connected directed multigraph with \[\deg^+(v)=\deg^-(v) \qquad\text{for every }v\in V.\] Arcs are distinguishable, and loops are allowed; a loop contributes one incoming and one outgoing incidence at its endpoint. An Eulerian tour of \(G\) is a cyclic ordering of the arcs in which consecutive arcs are head-to-tail incident and every arc appears exactly once. Eulerian tours are among the most classical objects in graph theory. In directed graphs, their enumeration is governed by the BEST theorem of de Bruijn, van Aardenne-Ehrenfest, Smith, and Tutte [1]–[3]. The theorem expresses the number of tours as an arborescence count times a product of local factorials, and it suggests a natural exact sampler: sample the arborescence part and then sample the local orders. This approach was used for sequence shuffling by Kandel, Matias, Unger, and Winkler [4] and sharpened using Wilson’s cycle-popping algorithm [5], [6]. Its running time, however, is tied to the cost of sampling random arborescences. On Eulerian digraphs, the best general random-walk mixing bounds for this task are on the \(mn\) scale [7], which is not nearly linear on sparse graphs.

The goal of this paper is to break this running-time barrier, at least for sparse graphs. We do this by sampling tours directly rather than sampling an arborescence and then completing it to a tour. The state of the chain is always a tour, and each transition changes only a small number of local successor choices.

A convenient language for local successor choices is that of transition systems. A transition system chooses, at every vertex \(v\), a bijection from the incoming arcs of \(v\) to the outgoing arcs of \(v\). Such a choice induces a permutation of the arc set \(E\): after an arc enters a vertex, the bijection specifies the next arc. The transition system is an Eulerian tour exactly when this permutation has one cycle. We write \(\mathrm{ET}(G)\) for the set of transition systems whose induced permutation has one cycle; this is the tour convention used throughout the paper. An initial tour can be found in linear time by the classical algorithm of Hierholzer [8].

The basic obstruction is also the key move. Changing one local successor choice usually breaks a tour into two circuits. The chain therefore makes one such break, uses the resulting two-circuit state as an intermediate layer, and then chooses uniformly among the local changes that glue the circuits back into one tour. We call this local transition the flip–repair move.

Our main result is the following.

The proof has two algorithmic ingredients. The first is the sampler for \(2\)-in/\(2\)-out directed Eulerian graphs, where one local transition flip is a single bit.

The second ingredient is a standard reduction from arbitrary degrees to degree two. The reduction replaces a degree-\(D\) vertex by a \(D\)-wire switching network: \(D\) input wires enter a small directed gadget of two-state \(2\)-in/\(2\)-out switches, \(D\) output wires leave it, and a setting of all switches routes the inputs to the outputs, thereby realizing a permutation in \(S_D\). Networks that realize permutations by composing binary switches are classical in the theory of rearrangeable connecting and permutation networks [9], [10]; randomized versions have also been studied as ways to generate almost-random permutations [11]–[13]. For our reduction, the network needs pointwise multiplicative control on every local permutation. This is stronger than merely saying that the induced permutation is almost uniform in total variation distance. We use the following pointwise \(L_\infty\) form as an auxiliary tool.

The runtime bound is driven by the degree-two sampler in 2: the chain mixes in nearly linear many steps and the data structure implements each step in \(O(\sqrt M\,\polylog M)\) time. The extension from arbitrary degrees to degree two is a supporting wrapper around this core. The one feature we need from that wrapper is pointwise control: common total-variation formulations of almost-random switching networks do not by themselves imply the multiplicative lift-counting estimate used here.

This places the paper in a broader algorithmic theme. Several recent breakthroughs in combinatorial optimization obtain near-linear running times by combining an optimization primitive with a data structure that maintains the primitive under many local updates; the almost-linear time algorithms for maximum flow and minimum-cost flow are a prominent example [14]. The analogous story has been rarer in sampling. Random spanning tree generation is one important exception: the near-linear sampler of Anari, Liu, Oveis Gharan, Vinzant, and Vuong combines sharp mixing bounds for down-up walks with graph-algorithmic data structures that implement the walk efficiently [15]. The present paper gives another example of this sampling-side paradigm: the speedup comes from matching a new local Markov chain to a representation in which its updates can be maintained dynamically.

The algorithm has three pieces, shown schematically in 1. The degree-two flip–repair chain is the core of the paper. The expansion and projection steps are the interface between this core sampler and general Eulerian digraphs: they convert high-degree local choices into degree-two switches, run the degree-two sampler, and then project the sampled tour back to the original graph.

1.0.0.1 Degree two.

When every vertex has indegree and outdegree two, each vertex has exactly two possible local transitions. Fix a reference Eulerian tour \(C\). At a vertex \(v\), one transition is the pairing used by \(C\); the other swaps the two successors. Thus every transition system is obtained by flipping a subset \(S\subseteq V\) of vertices relative to \(C\). The Cohn–Lempel interlacement theorem [16], [17], together with Bouchet’s unimodular orientation theorem for circle graphs [18]–[20], gives a real skew-symmetric matrix \(A=A_C\) such that \[\det(A_{S,S})\in\{0,1\}, \qquad \det(A_{S,S})=1 \Longleftrightarrow C^S \text{ is one Eulerian tour}.\] Thus the uniform distribution on degree-two tours is the skew-determinantal measure \[\mu_A(S)\propto \det(A_{S,S})\] for a real skew-symmetric matrix \(A\). We call such a measure flat when all positive determinants are equal; in the degree-two tour case they are all \(1\). This name emphasizes that the probability weights are principal determinants of a skew-symmetric matrix, and no additional structure is meant by the terminology. Since every odd skew-symmetric principal determinant is zero, this also explains why all feasible flips lie on one parity layer.

The degree-two sampler uses the flip–repair walk on this support. From a feasible \(S\), choose \(i\in V\) uniformly and move to the odd set \(Y=S\triangle\{i\}\). Then repair by choosing uniformly among all feasible \(T\) with \(\card{T\triangle Y}=1\). In tour language, the first flip splits the current tour into two cycles. The repair flip is chosen uniformly among the local flips that merge the two cycles back into one; this set includes flipping \(i\) back, which gives the self-loop \(T=S\).

1.0.0.2 Mixing.

The main proof ingredient behind the runtime is a mixing theorem for the larger family of skew-determinantal measures. If \(A\) is any real skew-symmetric \(n\times n\) matrix, define \[w_A(S)=\det(A_{S,S}), \qquad \mu_A(S)=\frac{w_A(S)}{\sum_T w_A(T)}.\] By a basic linear-algebra fact for real skew-symmetric matrices [21], odd principal determinants are zero and even principal determinants are nonnegative. The formula has the same principal-minor shape as determinant-based sampling measures, but the matrix is skew-symmetric and the support lies on one parity class. The same even-to-odd flip–repair walk has stationary distribution \(\mu_A\). We prove:

The spectral-gap statement is the structural part of the theorem. The constant \(2/n\) is sharp in the following simple case: \(A\) is a direct sum of \(2\times2\) skew-symmetric blocks, so the support is a product of independent binary choices, and the flip–repair walk updates one block with probability \(2/n\). Thus no skew-symmetric matrix can make the parity flip–repair walk slower than this product case; the proof of 7 spells out the sharpness example. For the sampling algorithm, however, the gap alone would only give a mixing bound with an extra factor coming from \(\log(1/\min_S\mu_A(S))\), which can be linear in \(n\) even in the flat case. The log-Sobolev part is what turns the flat \(0/1\) structure of Eulerian tours into nearly linear mixing time, up to logarithmic factors.

The proof of the mixing theorem has a useful linear-algebraic summary. For an even principal submatrix of a skew-symmetric matrix, the determinant has a standard signed square root, the Pfaffian. We put one basis vector \(e_S\) for each subset \(S\subseteq[n]\), and collect all these signed square roots in the single vector \[\Psi_A=\sum_{S\text{ even}}\pf(A_{S,S})e_S\] inside a \(2^n\)-dimensional vector space. Signed insertion and deletion operators act on the subset coordinate \(S\). Combining them gives the signed coordinate flips that model the first half-step of the chain. Applying these signed flips to the normalized vector \(\Psi_A/\norm{\Psi_A}\) gives orthonormal excitation coordinates, with \(\Psi_A/\norm{\Psi_A}\) as the degree-zero vector. We prove this from the standard \(2\times2\) block normal form for real skew-symmetric matrices and covariance of exterior powers under orthogonal changes of coordinates [21]. A row-cancellation estimate for the same coordinates follows from Knuth’s overlapping-Pfaffian identity [22]. In these excitation coordinates, the chain’s Dirichlet form dominates the excitation number divided by \(n\), giving the sharp gap \(2/n\).

For flat measures, this spectral estimate is strengthened by an entropy argument. The state basis and the excitation basis have maximum overlap \(1/\sqrt{\card{\supp(\mu_A)}}\). Maassen–Uffink entropic uncertainty [23], followed by Rothaus’s centering lemma [24], converts this overlap bound into the stated log-Sobolev inequality. The entire mixing proof is independent of Eulerian tours and is stated for all real skew-symmetric matrices.

1.0.0.3 Implementation and degree reduction.

The mixing theorem gives the number of Markov-chain steps; we also need to implement each step quickly. In degree two, represent the current tour by placing its \(M\) arc occurrences in cyclic order on a circle. Each vertex has two incoming arc occurrences in this order, and joining these two positions by a chord gives the cyclic chord diagram of the current tour. After the first flip at \(x\), the valid repair flips are \(x\) itself and the vertices whose chords cross \(x\). For a degree-two graph with \(M\) arcs, we maintain chunks of size on the order of \(\sqrt M\), pair lists for chunk pairs, and a top-level balanced sequence tree with aggregate counts. This supports uniform sampling of the repair flip and the resulting four-cut tour update in \(O(\sqrt M\,\polylog M)\) amortized time. The log-Sobolev bound gives \(O(M\polylog(M/\varepsilon))\) flip–repair steps, so this is where the \(M^{3/2}\), and ultimately \(m^{3/2}\), running time comes from.

To pass from degree two to arbitrary degrees, we first suppress degree-one vertices, whose local transition is forced. Each remaining degree-\(d\) vertex is then replaced by a degree-two switching-network gadget on \(d\) wires. This is a standard local reduction rather than the source of the new running time. Closely related gadgets appear in prior work on Eulerian-tour and A-trail reductions, and in parallel sampling reductions for Eulerian tours [25], [26]. We use it here because it lets the degree-two sampler be applied without changing the distribution by much.

The only point that needs care is the strength of the approximation. We use a sparse random network of lazy transposition switches. With high probability over the random choice of the network, the uniform distribution on switch settings induces a distribution on \(S_d\) which is pointwise \(e^{\pm\eta}\)-close to uniform. This is the multiplicative form needed for lift counting; total-variation closeness of the local permutation distribution would not by itself be enough, because the analysis conditions on the global one-cycle event. The pointwise estimate is a quenched switching-network version of the random-transposition shuffle bounds of Diaconis and Shahshahani [27]. The lift-counting argument then shows that every original tour has nearly the same number of expanded tours, point by point. Choosing local errors and gadget-failure probabilities summing to \(O(\varepsilon)\) makes the projected output distribution \(O(\varepsilon)\)-close to uniform on \(\mathrm{ET}(G)\).

1.0.0.4 Related work.

The classical exact approach to directed Eulerian tour sampling is through the BEST theorem and random arborescences [4]–[6]. Creed and Cryan studied Eulerian tours in random directed regular graphs [28]. Tetali and Vempala studied a Kotzig-transformation chain for the undirected Eulerian-tour sampling problem [29]. That problem is different from the directed problem considered here, and a general efficient sampler for undirected Euler tours remains open.

The walk studied here is on directed transition systems and does not use the undirected Kotzig chain. After reducing to degree two, the state space is a flat skew-determinantal support: it is described by principal determinants of a real skew-symmetric matrix, and those determinants are all \(0\) or \(1\). The proof proceeds by linear algebra of signed square roots of these principal determinants rather than comparison to arborescences.

Switching networks and the related Thorp shuffle have been studied as oblivious ways to generate almost-random permutations [11]–[13]. Local random permutation gadgets have also been used in reductions involving Eulerian tours and A-trails [25], and in parallel sampling work for Eulerian tours [26]. Our use is a supporting reduction: the degree-two sampler and its skew-determinantal mixing theorem do the main work, while the gadget supplies pointwise multiplicative control before conditioning on the global one-cycle event.

The measure \(\mu_A\) is a skew-symmetric principal-minor measure: its coefficients are \(\det(A_{S,S})\), where \(A\) is real skew-symmetric. These coefficients are nonnegative because \(\det(A_{S,S})=\pf(A_{S,S})^2\), and they vanish on one parity. Thus \(\mu_A\) is close in form to determinantal and strongly Rayleigh measures. Strongly Rayleigh measures, introduced by Borcea, Branden, and Liggett [30], satisfy strong negative dependence properties and have rapidly mixing basis-exchange walks in the homogeneous case [31]. Those results do not directly cover the measure here: the principal-minor formula comes from a skew-symmetric matrix, the support lies on one parity class rather than on one cardinality layer, and the natural local move is flip–repair rather than basis exchange. The generating polynomial \[\sum_S \det(A_{S,S})z^S = \det(I+A\diag(z))\] is Hurwitz stable: if \(\Re z_i>0\) for all \(i\), then \(\diag(z)^{-1}+A\) has positive definite Hermitian part and is nonsingular. We formulate conjectures in 7 suggesting that the spectral and stochastic-covering phenomena proved here for skew-determinantal measures extend to general Hurwitz-stable distributions; stochastic covering refers to local couplings between neighboring one-coordinate conditionings. This is also close to recent stability-based approaches to spectral independence and rapid mixing [32]–[34].

1.0.0.5 Provenance and AI assistance.

The author’s contribution was the high-level algorithmic plan, the transition-system and gadget reduction, the dynamic chord data structure, and the conjecture that the skew-determinantal flip–repair walk has the stated mixing behavior. The linear-algebra proof of 4 was produced by GPT 5.5 Pro Extended. Codex then organized, edited, and typeset the manuscript. See 8 for a fuller note.

1.0.0.6 Organization.

2 fixes transition-system notation. 3 identifies degree-two tours with flat skew-determinantal measures. 4 proves the general skew-determinantal mixing theorem. 5 gives the dynamic implementation of the degree-two sampler, and 6 proves the pointwise degree-reduction step. 7 records the stochastic-covering side result and the Hurwitz-stable conjectures.

2 Preliminaries↩︎

2.0.0.1 Eulerian transition systems.

Let \(G=(V,E)\) be a directed Eulerian multigraph. A transition system \(\tau\) assigns to each \(v\in V\) a bijection \[\tau_v:\delta^-(v)\to\delta^+(v).\] For a loop, its incoming and outgoing incidences are distinct local incidences, even though they belong to the same arc. It induces a permutation \(\pi_\tau\) of \(E\) by \[\pi_\tau(e)=\tau_{\operatorname{head}(e)}(e).\] The cycles of \(\pi_\tau\) are directed circuits partitioning \(E\). Thus \(\tau\) is an Eulerian tour if and only if \(\pi_\tau\) has one cycle. We write \(\mathrm{ET}(G)\) for the set of one-cycle transition systems. A rooted, linearly written tour is obtained by choosing one of the \(\card{E}\) arcs as the first arc, so this convention changes counts by a factor of \(\card{E}\).

2.0.0.2 The degree-two flip–repair chain.

Assume \(\deg^+(v)=\deg^-(v)=2\) for every vertex under consideration. Fix a reference tour \(C\). Each vertex has two possible transitions. If the two incoming incidences of \(v\) are paired by \(C\) with outgoing incidences \(o_1,o_2\), then the crossed transition swaps these two outgoing incidences. Therefore transition systems are indexed by subsets \(S\subseteq V\), where \(C^S\) denotes the system obtained by flipping exactly \(S\). The degree-two flip–repair chain on feasible \(S\)’s is: \[S \xrightarrow{\text{choose } i\in V \text{ uniformly}} Y=S\triangle\{i\} \xrightarrow{\text{choose feasible }T,\;\card{T\triangle Y}=1\text{ uniformly}} T.\] The feasible choices always include flipping \(i\) back to return to \(S\); thus the chain has a self-loop at every state.

2.0.0.3 Entropy and Dirichlet forms.

For a probability measure \(\mu\) on a finite set and a nonnegative function \(g\), \[\Ent_\mu(g)=\E_\mu{g\log g}-\E_\mu{g}\log\E_\mu{g}.\] We use the convention \(0\log0=0\). For a reversible Markov kernel \(P\) with stationary distribution \(\mu\), \[\mathcal{E}_P(f,f)=\ip{f}{(I-P)f}_\mu = \frac{1}{2}\sum_{x,y}\mu(x)P(x,y)(f(x)-f(y))^2.\]

2.0.0.4 Pfaffians.

For an even-dimensional skew-symmetric matrix \(B\) with ordered rows and columns, \(\pf(B)\) denotes the signed square root of the determinant specified by the perfect-matching expansion; equivalently, \(\pf(B)^2=\det(B)\). We use the conventions \(\pf(\varnothing)=1\) and \(\pf(B)=0\) for odd-dimensional skew-symmetric matrices. The proof only needs this determinant identity, expansion along a row or column, and Knuth’s overlapping-Pfaffian identity [22], which is cited again where it is used.

3 Degree-Two Tours as Flat Skew-Determinantal Measures↩︎

We next identify the degree-two state space with a principal-minor support. The input is a fixed reference tour \(C\). Relative to \(C\), each vertex contributes one bit, recording whether its local transition is flipped. The classical interlacement description of circuit partitions then turns the one-cycle condition into a principal-minor test [16], [17]. This is the bridge from Eulerian tours to the skew-determinantal measures analyzed in the next section.

Let \(H\) be a \(2\)-in/\(2\)-out directed Eulerian multigraph, and let \(C\) be an Eulerian tour. For each vertex \(v\), mark the two visits of \(C\) at which an incoming incidence of \(v\) is followed by an outgoing incidence of \(v\). A loop contributes distinct incoming and outgoing incidences at the same vertex, so it is treated in this incidence sense. These two marked positions form a chord on the tour circle. Two vertices \(u,v\) are interlaced if their four positions alternate around the circle.

The unsigned interlacement matrix \(I_C\) over \(\mathbb{F}_2\) has entry \(1\) when two chords cross and diagonal entries \(0\). The Cohn–Lempel equality [16], [17] says that if \(S\) is the set of vertices at which the transition is flipped relative to \(C\), then the number of circuits in the resulting circuit partition is \[1+\operatorname{nullity}_{\mathbb{F}_2}(I_C[S,S]).\] In particular, \(C^S\) is an Eulerian tour if and only if \(I_C[S,S]\) is nonsingular over \(\mathbb{F}_2\). The principal matrix \(I_C[S,S]\) is symmetric with zero diagonal. Over \(\mathbb{F}_2\), this means that the bilinear form \(x^\top I_C[S,S]y\) is alternating, i.e., \[x^\top I_C[S,S]x=0 \qquad\text{for every }x\in\mathbb{F}_2^S.\] Every alternating matrix has even rank, by the usual symplectic elimination for alternating bilinear forms. Thus, when \(\card{S}\) is odd, \(I_C[S,S]\) has rank strictly smaller than \(\card{S}\) and is singular. The feasible sets therefore lie on the even layer, matching the parity of the skew-determinantal representation.

For the mixing theorem we need a real skew-symmetric lift of this binary test. We now spell out the signing. Fix an orientation of the tour circle, and choose one endpoint \(v^-\) of every chord \(v\) as its tail; write \(v^+\) for the other endpoint. For distinct vertices \(u,v\), define \[A_C(u,v)= \begin{cases} 1, & \text{if \(u\) and \(v\) cross and \(v^-\) lies on the open arc from \(u^-\) to \(u^+\)},\\ -1, & \text{if \(u\) and \(v\) cross and \(v^+\) lies on the open arc from \(u^-\) to \(u^+\)},\\ 0, & \text{if \(u\) and \(v\) do not cross,} \end{cases}\] and set \(A_C(v,v)=0\). When \(u\) and \(v\) cross, exactly one endpoint of \(v\) lies on the open arc from \(u^-\) to \(u^+\), so the definition is unambiguous; it also gives \(A_C(v,u)=-A_C(u,v)\). Reducing entries modulo \(2\) forgets the signs and gives \(A_C\bmod2=I_C\).

Changing the chosen tail of a chord \(v\) multiplies the \(v\)-th row and column of \(A_C\) by \(-1\), so all principal determinants are independent of these auxiliary choices. Bouchet’s theorem says that this signed adjacency matrix of a circle graph is principally unimodular; the later paper of Bouchet, Cunningham, and Geelen uses essentially this formulation [18]–[20].

For this particular matrix \(A_C\), every positive weight is equal to \(1\). Consequently the normalizing constant is exactly the number of feasible degree-two tours represented relative to \(C\), and each feasible subset is counted once. This is the sense in which the distribution is flat. Thus the abstract skew-determinantal flip–repair walk has a concrete tour interpretation in degree two. After flipping one vertex \(i\), the repair step chooses uniformly among the vertices \(j\) for which flipping \(j\) gives another one-cycle transition system. The choice \(j=i\) is always available and is the self-loop. This is exactly the degree-two flip–repair chain defined in 2. The next section proves that this walk mixes rapidly, in fact for every real skew-symmetric matrix, not only for matrices arising from chord diagrams.

4 The Skew-Determinantal Flip–Repair Walk↩︎

We now prove the mixing theorem used by the sampler. The Eulerian-tour matrices from 3 are \(0/1\)-weighted examples of the following more general object, so we state the argument at that level. Let \(A\in\R^{n\times n}\) be skew-symmetric. For \(S\subseteq[n]\), write \(A_S=A_{S,S}\), and set \(\pf(A_S)=0\) when \(\card{S}\) is odd. Define \[w(S)=\det(A_S)=\pf(A_S)^2, \qquad Z=\sum_{S\subseteq[n]}w(S).\] We use the convention that the empty principal determinant is \(1\), so \(Z\ge1\). The equality \(w(S)=\pf(A_S)^2\) also explains why these weights are nonnegative. Since odd skew-symmetric matrices have determinant zero, \(w\) is supported on even sets. Let \[\Omega=\{S\subseteq[n]:w(S)>0\}, \qquad \mu(S)=w(S)/Z.\] We call \(\mu\) the skew-determinantal measure associated with \(A\).

The flip–repair walk first flips one coordinate and then applies the repair step, which is the time reversal of that flip. We write this two-step chain as \(P=KK^*\), using the following \(L^2\) convention: \(K(S,Y)\) is the forward transition probability from even sets to odd sets, while as an operator on functions \(K\) averages a function on the odd layer back to the even layer. Its adjoint \(K^*\), with respect to \(\mu\) and the intermediate measure \(\nu\), is the repair step from odd sets to even sets. The forward kernel sends an even \(S\in\Omega\) to an odd set \(Y\) by flipping a uniformly random coordinate: \[K(S,Y)=\frac{1}{n}\1_{\{\card{S\triangle Y}=1\}}.\] The intermediate measure is \[\nu(Y)=\sum_S\mu(S)K(S,Y) = \frac{1}{nZ}\sum_{i=1}^n w(Y\triangle\{i\}).\] For odd \(Y\) with \(\nu(Y)>0\), the reverse kernel is the conditional law of the previous even state given that the first flip reached \(Y\): \[K^*(Y,T) = \frac{w(T)}{\sum_i w(Y\triangle\{i\})} \qquad \text{if }T\in\Omega\text{ and }\card{T\triangle Y}=1,\] and \(K^*(Y,T)=0\) otherwise. The denominator sums the weights of all even neighbors of \(Y\); neighbors of weight zero simply contribute nothing. Thus \[P(S,T)= \frac{1}{n} \sum_{\substack{Y:\;\card{Y\triangle S}=\card{Y\triangle T}=1}} \frac{w(T)}{\sum_i w(Y\triangle\{i\})}.\] Here \(S,T\in\Omega\). Every odd \(Y\) that appears in the sum is reachable from \(S\), so the denominator is positive because it includes the term \(w(S)\). The two layers and the repair step are illustrated in 2. The chain is reversible with stationary distribution \(\mu\): with the operator convention above, \(P=KK^*\) is self-adjoint in \(L^2(\mu)\), and Markov kernels of this form preserve constants. When \(\Omega\) has one state, we use the convention that the spectral gap is \(1\) and the mixing time is \(0\).

The proof is a comparison argument after a square-root change of variables. Instead of analyzing the transition matrix directly on functions \(f:\Omega\to\R\), we multiply each coordinate by a signed square root of its weight: \[h_f=\sum_{S\in\Omega} f(S)\pf(A_S)e_S .\] The point of this normalization is that the repair step becomes an orthogonal projection. The second step is to use the basis obtained by applying signed coordinate flips to the normalized Pfaffian vector. We call the resulting basis vectors excitations, by analogy with Fourier characters on the Boolean cube. The excitation degree is measured by a diagonal operator \(\mathsf N_A\).

The central estimate compares the projection operator of the walk with this degree operator: \[\mathsf P_A\preceq I-\frac{1}{n}\mathsf N_A .\] Once this is proved, the spectral gap is almost immediate. The degree-zero excitation is the constant direction, and every other even excitation has degree at least \(2\). Thus the Dirichlet form is at least \(2/n\) times the variance.

The flat log-Sobolev bound uses the same coordinates. When all nonzero weights are \(1\), no state basis vector has a large overlap with any excitation basis vector. Entropic uncertainty turns this incoherence into an entropy bound. In this order, the rest of the section constructs \(\mathsf P_A\), constructs \(\mathsf N_A\), compares them, and then applies the same coordinates to entropy.

4.1 The Square-Root Operator↩︎

We first rewrite the walk in the square-root coordinates above. Fix an odd intermediate set \(Y\). The repair step averages over the feasible even neighbors of \(Y\), with weights \(w(S)\). After replacing \(w(S)\) by \(\pf(A_S)^2\), this weighted average becomes an orthogonal projection onto a single vector \(\Phi_Y\). Averaging over the first flip gives the operator \(\mathsf P_A\).

Let \(V=\R^n\), with standard basis \(e_1,\ldots,e_n\), and let \[\mathcal{H}=\bigwedge\nolimits^\bullet V = \bigoplus_{k=0}^n \bigwedge\nolimits^k V .\] For \(S=\{i_1<\cdots<i_k\}\), write \[e_S=e_{i_1}\wedge\cdots\wedge e_{i_k}, \qquad e_\varnothing=1.\] The vectors \(e_S\) form an orthonormal basis. We use \(\mathcal{H}^{\mathrm{even}}\) and \(\mathcal{H}^{\mathrm{odd}}\) for the spans of the even and odd basis vectors.

The Pfaffian square-root vector of \(A\) is the vector whose coordinates are the principal Pfaffians: \[\Psi=\Psi_A= \sum_{S\text{ even}} \pf(A_S)e_S .\] Equivalently, by the perfect-matching expansion of the Pfaffian [22], \[\Psi= \exp\left(\sum_{1\le i<j\le n} A_{ij}e_i\wedge e_j\right).\] Therefore \(\norm{\Psi}^2=Z\). For a function \(f:\Omega\to\R\), put \[h_f=f\Psi := \sum_{S\in\Omega} f(S)\pf(A_S)e_S .\] Then \[\label{eq:sqrt-embedding} \norm{h_f}^2=Z\E_\mu{f^2}, \qquad \ip{h_f}{\Psi}=Z\E_\mu{f}.\tag{1}\]

For an odd set \(Y\), let \[\Star(Y)=\set{S\subseteq[n]\given \card{S\triangle Y}=1\text{ and }S\text{ is even}}, \qquad C(Y)=\sum_{S\in \Star(Y)} w(S).\] Define \[\Phi_Y= \sum_{S\in \Star(Y)}\pf(A_S)e_S\in\mathcal{H}^{\mathrm{even}} .\] Thus \(\norm{\Phi_Y}^2=C(Y)\). Let \(\operatorname{Proj}_u\) denote orthogonal projection onto the line spanned by a nonzero vector \(u\). Define the square-root operator \[\mathsf P_A = \frac{1}{n} \sum_{\substack{Y\text{ odd}\\ C(Y)>0}} \operatorname{Proj}_{\Phi_Y} \qquad\text{on }\mathcal{H}^{\mathrm{even}} .\]

4.2 Excitation Coordinates↩︎

We now build the basis in which the comparison is diagonal. The analogy is with the Fourier basis on the Boolean cube. There the constant function is the degree-zero vector, and multiplying by coordinate characters produces basis vectors whose degree is the number of coordinates used. Here the normalized Pfaffian vector \(\widehat\Psi=\Psi/\sqrt Z\) plays the role of the constant vector. Applying signed coordinate flips to \(\widehat\Psi\) gives the other basis vectors, and the number of flips applied is the excitation degree.

The signed flips are the standard insertion-plus-deletion operators on subset vectors. For \(b\in\R^n\), let \[\varepsilon_b x=b\wedge x, \qquad \iota_b=\varepsilon_b^*, \qquad c_b=\varepsilon_b+\iota_b .\] Thus \(\varepsilon_b\) inserts \(b\), \(\iota_b\) deletes \(b\), and \(c_b\) is the signed coordinate flip. The exterior-algebra relations are \[\varepsilon_b\varepsilon_{b'}+\varepsilon_{b'}\varepsilon_b=0, \qquad \iota_b\iota_{b'}+\iota_{b'}\iota_b=0, \qquad \iota_b\varepsilon_{b'}+\varepsilon_{b'}\iota_b=\ip{b}{b'}I.\] Equivalently, \[c_bc_{b'}+c_{b'}c_b=2\ip{b}{b'}I .\] These are the standard finite-dimensional creation–annihilation relations [35], [36]. We write \(c_i=c_{e_i}\), and for \(T=\{i_1<\cdots<i_k\}\), \[c_T=c_{i_1}\cdots c_{i_k}.\]

Set \(\widehat\Psi=\Psi/\sqrt Z\). The excitation vectors are \[\xi_T=c_T\widehat\Psi, \qquad T\subseteq[n].\]

Define the excitation number operator by \[\mathsf N_A\xi_T=\card{T}\,\xi_T.\] For \(f:\Omega\to\R\), define its average excitation degree by \[\Deg_A(f) = \frac{1}{Z}\ip{h_f}{\mathsf N_A h_f}.\] Thus \(\mathsf N_A\) is simply the degree operator in the excitation basis. This is the usual number operator in finite fermionic Fock space after the orthogonal change of generators determined by \(\widehat\Psi\) [35], [36], but the proof uses only the displayed diagonal form.

4.3 Projection versus Number↩︎

We now prove the central inequality \(\mathsf P_A\preceq I-\mathsf N_A/n\). We need to understand each projection vector \(\Phi_Y\) in excitation coordinates.

Write an even vector \(h\in\mathcal{H}^{\mathrm{even}}\) in excitation coordinates as \[h=\sqrt Z\sum_{T\text{ even}} a_T\xi_T, \qquad a=\sum_{T\text{ even}} a_Te_T .\] For an odd set \(Y\), define its coordinate row in the excitation basis by \[R_Y= \sum_{T\text{ odd}} \ip{e_Y}{\xi_T}e_T \in\bigwedge\nolimits^{\mathrm{odd}}\R^n.\] The vectors \(R_Y\), over odd \(Y\), form an orthonormal basis of the odd coordinate space; \(R_Y\) is the row of the change-of-basis matrix indexed by the ordinary odd basis vector \(e_Y\). Let \[\beta_Y=\pi_1R_Y\in\bigwedge\nolimits^1\R^n\simeq\R^n,\] where \(\pi_1\) is orthogonal projection onto degree one. The point of \(\beta_Y\) is that this degree-one part contains exactly the information needed to express the projection at \(Y\).

The next lemma is the only cancellation needed for the comparison. It says that each row \(R_Y\) is killed by insertion in the direction of its degree-one part \(\beta_Y\). The cancellation is the following specialization of Knuth’s overlapping-Pfaffian relation [22]. We write the needed special case explicitly in the proof, after the signs have been fixed.

4.4 Flat Log-Sobolev Bound↩︎

Assume from now on that \(n\ge2\) and \(w(S)\in\{0,1\}\) for all \(S\subseteq[n]\). Then \(Z=\card{\Omega}\). The spectral proof did not use flatness. The flat assumption enters through an incoherence bound between the state basis \(\{e_S\}\) and the excitation basis \(\{\xi_T\}\). This subsection follows the standard entropy route: incoherence gives entropic uncertainty, entropic uncertainty bounds entropy by excitation-basis entropy, and a one-line Gibbs bound controls that entropy by the average excitation degree. Rothaus’s centering lemma removes the mean.

5 Implementing the Degree-Two Chain↩︎

The previous section bounds the number of flip–repair steps. We now describe how to execute those steps in sublinear time on a changing tour. Let \(H\) be a \(2\)-in/\(2\)-out Eulerian digraph with \(M\) arcs. The fixed reference tour used in 3 is needed for the mixing proof, but not for the implementation. The data structure stores only the current one-cycle transition system, written as a cyclic sequence \[\Gamma=(e_1,e_2,\ldots,e_M).\] An occurrence means one position of this cyclic sequence. Since each position is an arc whose head is some vertex, every occurrence is owned by the head of that arc; in a \(2\)-in/\(2\)-out graph each vertex owns exactly two occurrences. Flipping a coordinate of the subset representation is exactly swapping the two successors after the two occurrences owned by the same vertex in the current transition system. For a vertex \(v\), let \(a_v,b_v\) be these two incoming-arc occurrences, viewed as positions on the cyclic sequence \(\Gamma\). Thus every vertex is a chord of the current tour circle.

Thus the repair step, in the flat skew-determinantal tour measure, is exactly dynamic uniform sampling from the queried chord itself and all chords crossing it in the current tour. Sampling the queried chord gives a self-loop; sampling a crossing chord is followed by a constant number of cyclic cuts and concatenations. 3 shows both the crossing test and the resulting cyclic reassembly. The implementation therefore never needs to materialize the odd intermediate two-cycle state. It samples the first vertex \(x\), samples the repair vertex from \(\{x\}\) together with the chords crossing \(x\) in the current tour, and then either stays put or applies the combined two-flip update. The naive implementation scans all chords after the first flip, costing \(O(M)\) per flip–repair step. Since the mixing bound already has \(O(M)\) steps up to polylogarithmic factors, this would give a quadratic-time sampler. We use a chunk structure to answer the same crossing query in roughly \(\sqrt M\) time while still supporting the four-cut update to the tour.

5.1 Chunk Structure↩︎

Fix a chunk parameter \(B\), which will be set to \(\lceil\sqrt M\rceil\) at the end. Maintain the cyclic sequence in chunks of size between \(B/2\) and \(2B\), except during a local rebuild. Let \(q=O(M/B)\) be the number of chunks. Give each live chunk a stable identifier from a pool of \(Q=O(M/B)\) identifiers, with constant-factor slack for the temporary chunks created during one update. The aggregate vectors used by the data structure are indexed by this identifier pool, so splitting or merging chunks does not require resizing them.

When we rebuild a local window of chunks, we first give the new chunks fresh identifiers. Then, for every vertex with at least one occurrence in the rebuilt window, we record its old unordered pair of chunk identifiers and its new unordered pair, delete the old pair-list entry and endpoint contributions, and insert the new ones. This vertex-by-vertex update is important when both occurrences of a vertex lie in the rebuilt window: the old pair is removed once and the new pair is inserted once, so coincident identifiers cause no ambiguity. Only after all such updates have been performed do we retire the old chunk identifiers. At that point no live vertex has an occurrence in a retired identifier, and every aggregate contribution involving that identifier has been deleted, because aggregate entries are maintained as a sum of these per-vertex endpoint contributions. We then clear the \(O(Q)\) pair-list headers incident to each retired identifier, or equivalently bump a generation counter for those headers, before putting the identifier back on the free list. No global scan of the treap vectors is needed; the zero aggregate coordinates are a consequence of the deleted endpoint contributions.

For every occurrence, store its chunk, offset, and owner vertex. For every vertex, store handles to its two occurrences. For every unordered pair of chunks \(\{C,D\}\), allowing \(C=D\), maintain a dynamic array \[L[C,D] = \{v:\text{ one occurrence of }v\text{ lies in }C \text{ and the other lies in }D\}.\] When \(C\ne D\), this list is stored only once but is addressable as both \(L[C,D]\) and \(L[D,C]\); when \(C=D\), it contains the vertices whose two occurrences are both in \(C\). Each vertex stores its index in its current pair list, so moving it between lists takes \(O(1)\) time by swap-delete. The total size of all lists is \(O(M)\), and there are \(O(Q^2)=O(M^2/B^2)\) headers. The first flip of each step is sampled from a static array of the degree-two vertices, since the vertex set does not change during the walk. Thus the only nontrivial sampling problem is the repair flip: sample uniformly from the queried chord and the chords crossing it.

The cyclic order of chunks is represented by any balanced binary sequence tree; for concreteness one may use a treap [39]. Each internal node \(U\) stores a vector indexed by chunk identifiers. The invariant used by the crossing query is the following: if \(D\) is not a chunk of the subtree \(U\), then \[\mathbf{V}_U[D] = \#\{v:\text{ one occurrence of }v\text{ is in a chunk of }U \text{ and the other occurrence is in }D\}.\] It is helpful to view the vector as storing endpoint contributions. A vertex with occurrences in chunks \(C\) and \(D\) contributes one unit to coordinate \(D\) on every ancestor of \(C\), and one unit to coordinate \(C\) on every ancestor of \(D\); when \(C=D\), these two contributions are combined on the same ancestor path. For a query we only read coordinates \(D\) outside the subtree \(U\), where this contribution rule is exactly the displayed invariant. Coordinates \(D\) lying inside \(U\) are maintained by the same bottom-up summation rule so that later splits and concatenations can expose them as outside coordinates of some new node. Splitting or concatenating the treap recomputes \(O(\log q)\) internal nodes, each in \(O(Q)\) time, for \(O(Q\log q)\) time. For an affected vertex whose old chunk pair is \(\{C,D\}\) and whose new chunk pair is \(\{C',D'\}\), we update the pair lists and adjust exactly these endpoint contributions: delete one unit in coordinate \(D\) along the ancestor path of \(C\) and one unit in coordinate \(C\) along the ancestor path of \(D\), then insert the analogous contributions for \(C',D'\). If some identifiers coincide, the corresponding increments are combined. This costs \(O(\log q)\) per affected vertex.

5.2 Sampling Crossings↩︎

Given a query chord \(x\), let \(I=(a_x,b_x)\) be one of the two open intervals. Decompose \(I\) into at most two partial boundary chunks and a set \(F\) of full chunks. The set \(F\) may be empty, and the two boundary chunks may coincide. Let \(\mathcal{B}\) be the set of boundary chunks; see 4. Membership in \(I\) always means membership in this open interval, so the two endpoints of the queried chord \(x\) are not counted as lying in \(I\). The choice of which of the two intervals to call \(I\) does not affect the crossing set: replacing \(I\) by its complement simply swaps the roles of “inside” and “outside.”

Every crossing vertex other than \(x\) has exactly one endpoint in \(I\) and one endpoint outside \(I\). We split these vertices into two disjoint classes, according to whether one of the two endpoints lies in a boundary chunk of the interval decomposition. This is only a data-structural split; the flip–repair step must sample uniformly from the union of the two classes and \(x\) itself. The classes are exhaustive because every endpoint of a crossing vertex lies either in a boundary chunk or in a full inside/outside chunk, and they are disjoint by definition. Thus class A consists exactly of crossing vertices whose inside endpoint lies in a full chunk of \(F\) and whose outside endpoint lies in a full chunk outside \(F\cup\mathcal{B}\); class B is everything involving at least one boundary endpoint.

5.2.0.1 Class A.

No endpoint lies in a boundary chunk. Then one endpoint lies in a full inside chunk \(C\in F\), and the other lies in a full outside chunk \(D\notin F\cup\mathcal{B}\). Cover the contiguous set of full chunks \(F\) by the usual \(O(\log q)\) treap nodes, and let \(\mathbf{V}_F\) be the sum of their stored vectors. For every outside chunk \(D\notin F\cup\mathcal{B}\), the invariant above gives \[\mathbf{V}_F[D] = \#\{v:\text{ one endpoint of }v\text{ lies in }F,\text{ the other in }D\}.\] Because \(D\) is outside \(F\), every such vertex appears in exactly one pair list \(L[C,D]\) with \(C\in F\), and conversely every vertex in one of these lists has exactly one endpoint in the open interval \(I\). Thus \[\mathbf{V}_F[D]=\sum_{C\in F}\card{L[C,D]}.\] Let \[W_A=\sum_{D\notin F\cup\mathcal{B}}\mathbf{V}_F[D].\] If \(W_A>0\), sample class A as follows: choose \(D\) with probability \(\mathbf{V}_F[D]/W_A\), choose an inside chunk \(C\in F\) with probability \(\card{L[C,D]}/\mathbf{V}_F[D]\), and then choose a uniformly random vertex from \(L[C,D]\). The second choice can be implemented by scanning the \(O(q)\) chunk headers in \(F\), using the stored sizes of the lists \(L[C,D]\); this scan is within the per-step budget. For a fixed class-A vertex in the list \(L[C,D]\), the probability of selecting it is \[\frac{\mathbf{V}_F[D]}{W_A}\cdot \frac{\card{L[C,D]}}{\mathbf{V}_F[D]}\cdot \frac{1}{\card{L[C,D]}} = \frac{1}{W_A},\] so this procedure is uniform over class A.

5.2.0.2 Class B.

At least one endpoint lies in a boundary chunk. Enumerate all occurrences in the boundary chunks, at most \(O(B)\) occurrences. For each owner vertex \(v\), test whether exactly one of \(a_v,b_v\) lies in \(I\). The test uses the chunk ranks in the top-level sequence tree and the offsets inside the two boundary chunks; computing the needed ranks costs \(O(\log q)\) per tested vertex, or \(O(B\log q)\) total for the boundary scan. Deduplicate using timestamps, yielding an explicit list \(Q_B\) of size \(W_B\). The test removes noncrossing boundary vertices and also removes \(x\), because the endpoints of \(x\) are the open-interval endpoints and are not counted as lying in \(I\). Sampling class B means choosing a uniformly random vertex from this explicit list \(Q_B\).

Let \(W=W_A+W_B\). The valid repair flips are \(x\) itself and the \(W\) crossing vertices. Choose \(x\) with probability \(1/(W+1)\), which gives a self-loop. Equivalently, if \(W=0\) the repair flip is forced to be \(x\). If the chain does not choose \(x\), then \(W>0\); choose class A with probability \(W_A/W\) and class B with probability \(W_B/W\), and sample inside the chosen class as above. A class-A vertex has probability \((W_A/W)\cdot(1/W_A)=1/W\), and a class-B vertex has probability \((W_B/W)\cdot(1/W_B)=1/W\). Thus, conditional on not choosing the self-loop, the repair flip is uniform over all crossing vertices, and unconditionally it is uniform over all feasible repair choices adjacent to the odd intermediate state. Each such choice is a distinct coordinate flip from the odd set, so sampling a vertex is the same as sampling the corresponding feasible even neighbor of the flip–repair transition.

5.3 Tour Update↩︎

If the sampled repair flip is \(x\), the chain stays at the current tour. Otherwise, suppose the four involved occurrences have cyclic order \[a\; P\; c\; Q\; b\; R\; d\; S,\] where \(a,b\) belong to \(x\) and \(c,d\) belong to \(y\). Flipping \(x\) and \(y\) changes the cyclic order to \[a\; R\; d\; Q\; b\; P\; c\; S.\] This is a constant number of cuts and concatenations; no reversal is needed in the directed successor-swap convention. We first split chunks at the four cut positions, perform the treap update, and then rebuild the boundary chunks. Only \(O(B)\) occurrences change chunk membership during this rebuild. The pair lists depend only on the two chunk identifiers containing a vertex’s occurrences. Therefore merely reordering whole chunks during the cyclic reassembly does not change any pair-list membership; only occurrences lying in newly split or rebuilt chunks need to be moved between pair lists and reflected in the treap aggregates.

6 A Standard Degree-Reduction Gadget↩︎

It remains to connect the degree-two sampler to a graph with arbitrary Eulerian degrees. The reduction is local. If \(d=\deg^+(v)=\deg^-(v)\), then a transition system chooses a permutation from the \(d\) incoming arcs of \(v\) to the \(d\) outgoing arcs. We replace this local choice by a degree-two switching network. Vertices with \(d=1\) have a forced local transition; we contract them before the reduction and expand them again after sampling. This is a supporting reduction, not the main mixing argument. It is in the same spirit as earlier local gadget reductions for Eulerian tours and A-trails [25] and the degree-reduction step used for Eulerian tours in parallel discrete sampling via continuous walks [26]. We first check whether every vertex has degree one. In that all-forced case, strong connectivity makes the graph a directed cycle and there is nothing to randomize. Otherwise, at least one vertex has degree at least two, and suppressing a degree-one vertex does not change the degrees of any other vertex. Thus a non-forced vertex remains throughout the suppression process, and after all forced vertices have been suppressed the remaining graph has minimum degree at least two.

The gadget reduction has two separate obligations. First, contracting each gadget back to the original vertex must preserve the number of cycles in the transition system. Second, for each original local permutation, the number of expanded local settings projecting to it must be almost independent of the permutation. The next lemmas prove these two facts.

A \(D\)-wire switching network has \(D\) input ports, \(D\) output ports, and internal vertices called switches. Ports are attachment points, not vertices of the expanded graph. The arcs of the network are directed wire segments running from input ports through switches and then to output ports. Each switch has two incoming wire segments and two outgoing wire segments, so it is a \(2\)-in/\(2\)-out vertex. A switch setting is one of the two local successor pairings at that vertex: straight or crossed. Once every switch is set, every input port is routed along a unique directed path to an output port, and these paths define a permutation of \([D]\).

The networks we use are sparse random lazy-transposition networks with a short guard layer whose locations are deterministic. First insert switches between wires \[(1,2),(2,3),\ldots,(D-1,D).\] This touches every wire at least once. Then choose \[R=2\left\lceil C\,D\bigl(\log D+\log(1/(\eta\delta))\bigr)\right\rceil\] unordered pairs \(a_tb_t\) from \(\binom{[D]}2\), independently and uniformly. For each chosen pair, insert one switch between the current wire \(a_t\) and the current wire \(b_t\). Wires that are not involved in a switch continue to their next switch or output port as a single directed arc segment. Thus the network has \(D-1+R\) internal vertices and \(O(D+R)\) arc segments. A setting of the switches is exactly a product of lazy transpositions in the prescribed order. The guard layer is included only to make the graph replacement well-formed after port suppression; it does not hurt the pointwise mixing bound, because convolving an already pointwise-close distribution with any other distribution preserves pointwise closeness to uniform.

We use the following upper-bound-sum form of the Diaconis–Shahshahani analysis of random transpositions [27]. Let \(\widehat{S_D}\) be the set of irreducible representations of \(S_D\). For \(\lambda\in\widehat{S_D}\), let \(d_\lambda\) be its dimension, \(\chi_\lambda\) its character, and \[\alpha_\lambda = \frac{1}{2}\left(1+\frac{\chi_\lambda(\tau)}{d_\lambda}\right),\] where \(\tau\) is any transposition. Thus \(\alpha_\lambda\) is the scalar by which the lazy random-transposition kernel acts on the \(\lambda\)th isotypic component. In particular, \(\alpha_\lambda\in[0,1]\), since these scalars are eigenvalues of a lazy reversible Markov kernel.

Equivalently, the \(k\)-step lazy random-transposition law \(p_k\) satisfies \[\sup_{\sigma\in S_D}\abs{D!\,p_k(\sigma)-1}\le \xi\] under the same hypothesis, because Fourier inversion bounds the left-hand side by the displayed character sum. We use this character-sum form because it passes cleanly through the second-moment calculation for a fixed random switching network.

We now use this network as a graph replacement. For a degree-\(d\) vertex \(v\), apply 3 with \(D=d\). Delete \(v\). For each incoming arc \(i_j\), keep its tail and make its head the \(j\)th input port. For each outgoing arc \(o_j\), make the \(j\)th output port its tail and keep its head. The ports only splice original arcs to network wire segments. After all splices are made, suppress the ports: each maximal directed path whose internal points are ports and whose endpoints are switches is replaced by one arc. The guard layer ensures that every wire has at least one switch, so port suppression does not create a closed directed component with no switch vertex. After suppression, the only vertices left in the expanded graph are switches, and every such vertex has indegree and outdegree two. A realized network can still fail the pointwise guarantee of 3; that failure is not detected by the algorithm and is accounted for only by the bad construction event in the analysis. 5 shows this local replacement.

We can now define the projection used by the sampler. Given an expanded Eulerian tour of \(G^\star\), read off the network permutation realized inside each gadget. This is the local permutation at the corresponding vertex of the suppressed graph. Finally, undo the degree-one suppressions from 13. The result is a transition system of the original graph \(G\), and by the cycle-preservation lemma it is again one Eulerian tour. We need two estimates from this construction: projection probabilities must be nearly uniform over original tours, and the expanded graph must remain nearly linear in size.

7 Stochastic Covering and Hurwitz-Stable Conjectures↩︎

The sampler and its runtime analysis are complete after 6. We end with a structural consequence of the same subset-vector viewpoint. This result is independent of the algorithm, but it helps explain why the skew-determinantal measures in the mixing theorem behave like a parity analogue of negatively dependent measures.

The consequence is a local coupling statement in the spirit of stochastic covering. Stochastic covering was introduced to formalize the idea that two neighboring one-coordinate conditionings of a negatively dependent measure can be coupled locally [40]. Strongly Rayleigh measures, introduced by Borcea, Branden, and Liggett via real-stable generating polynomials [30], satisfy this property: after conditioning one coordinate to be \(1\) versus \(0\), the two conditional measures can be coupled by changing only one other coordinate in the monotone direction [31], [40].

Here the support has a fixed parity, so the analogous local statement has a parity shift. We couple a sample with \(i=0\) to a sample with \(i=1\) so that all but one of the remaining bits agree. Equivalently, after deleting coordinate \(i\), the problem is to transport an even subset of \(W=[n]\setminus\{i\}\) to an odd subset of \(W\) by flipping one coordinate of \(W\). Re-inserting \(i\) then gives a coupling whose two original configurations differ in exactly two coordinates.

The proof has two steps. First, we represent each conditional law as the squared coordinates of a unit vector in the subset-vector space with coordinate \(i\) removed. Second, we show that the two unit vectors are related by one signed coordinate-flip operator \(c_b\). The operator \(c_b\) is an isometry, and every nonzero matrix entry of \(c_b\) connects two subsets that differ in one remaining coordinate. Squaring coordinates turns the two vectors into the two probability distributions we want to couple. A max-flow/min-cut argument then turns this sparse isometry into an actual coupling supported on those same one-coordinate moves after deleting \(i\), hence on two-coordinate moves in the original cube. Thus the argument has the same transport shape as stochastic covering for strongly Rayleigh measures: an algebraic certificate gives local support for a transport, and max-flow/min-cut turns this support statement into an actual coupling. The difference is the parity shift. Strongly Rayleigh covering is monotone, whereas here the two conditionings live on opposite parities after deleting \(i\). The local move therefore flips one remaining coordinate, as shown in 6.

We first use a small transport lemma. It is a linear-algebraic version of the following elementary idea: if an isometry \(U\) has nonzero entries only on the edges of a bipartite graph \(H\), then the probability distribution obtained by squaring the coordinates of a vector \(x\) can be transported to the distribution obtained by squaring the coordinates of \(Ux\), using only edges of \(H\). The isometry condition says that no set of left vertices can carry more squared mass than its neighborhood carries on the right. These are exactly the weighted Hall inequalities, and max-flow/min-cut converts them into a coupling.

This theorem is the parity analogue of stochastic covering. It suggests that the right ambient class may be Hurwitz-stable measures rather than strongly Rayleigh measures. In the conjectures that follow, disconnected supports are handled in the usual way: restrict the walk to a connected component, or equivalently ask for the same bounds on every component. This caveat is necessary for any spectral-gap statement, since a disconnected support gives zero gap.

[thm:spectral-comparison,thm:flat-lsi,thm:pfaffian-covering] prove [conj:hurwitz-covering] [conj:hurwitz-mixing] for the skew-determinantal subclass, after normalizing the coefficients to make a probability distribution. For this subclass, \[g_A(z)=\sum_S\det(A_{S,S})z^S=\det(I+A\diag(z)),\] where \(A\) is real skew-symmetric. The equality with the determinant is the principal-minor expansion of \(\det(I+A\diag(z))\): choosing the nonidentity rows and columns in a set \(S\) contributes \(\det(A_{S,S})\prod_{i\in S}z_i\). This also makes the nonnegativity of the coefficients transparent, since \(\det(A_{S,S})=\pf(A_{S,S})^2\ge0\).

We now check Hurwitz stability. If \(\Re z_i>0\), then each \(z_i\) is nonzero and \[\det(I+\diag(z)A)=\det(\diag(z))\det(\diag(z)^{-1}+A).\] Moreover, the identity \(\det(I+XY)=\det(I+YX)\) gives \(\det(I+A\diag(z))=\det(I+\diag(z)A)\) [21]. The matrix \(\diag(z)^{-1}+A\) has positive definite Hermitian part: the Hermitian part is \(\diag(\Re(1/z_i))\), since \(A^*=-A\), and \(\Re(1/z_i)>0\) whenever \(\Re z_i>0\). If \((\diag(z)^{-1}+A)x=0\) for some nonzero complex vector \(x\), then \[x^*(\diag(z)^{-1}+A)x=0.\] But the real part of the left-hand side is \(\sum_i \Re(1/z_i)\abs{x_i}^2>0\), a contradiction. Thus \(\diag(z)^{-1}+A\) is nonsingular, and hence \(g_A(z)\ne0\).

Acknowledgments↩︎

We thank Thuy-Duong Vuong, Tianyu Liu, and Eric Ma for discussions about the problem.

8 Provenance↩︎

This manuscript used AI assistance in a substantive way. The author had already devised the high-level plan for the sampler, including the reduction to degree two, the transition-system walk, the switching-network gadget reduction, and the dynamic data-structure implementation. The author conjectured the stated mixing bounds for the skew-determinantal flip–repair walk, not the proof route used to prove them.

The proof of the mixing theorem, including the square-root projection formulation, the excitation-number comparison, and the flat log-Sobolev proof via entropic uncertainty and Rothaus centering, was produced by GPT 5.5 Pro Extended. Codex then assembled the paper, integrated the proof into the manuscript, added surrounding exposition and references, and typeset the draft under the author’s supervision.

References↩︎