Random even graphs.

*(English)*Zbl 1214.05155One aim of the paper under review is to study a random even (spanning) subgraph \(H=(V,F)\) of a finite graph \(G=(V,E)\), where a graph is even if all its vertices have even degree. We use as probability measure the measure on possible edge sets where, given \(p\in [0,1)\)
\[
\rho_{p}(F)=\frac{1}{Z_{E}}p^{| F|}(1-p)^{| E| - | F|}
\]
where \(Z_{E}\) is the normalising constant to ensure that the total mass is one. Such graphs have links with the Ising model (depending on a parameter \(\beta\)), and the random-cluster model on \(G\) when one of its parameters \(q\) is 2: the link is established via the (misleadingly titled) ‘high-temperature expansion’ which is proved in the paper.

We note that the family of even subgraphs can be identified with a vector subspace \({\mathcal E}\) of \(\{0,1\}^{| E|}\), with two subgraphs having sum the symmetric difference of their two edge sets. This also suggests the definition of \({\mathcal E}\) for the case where \(G\) is locally finite but infinite. One then shows that \({\mathcal E}\) has a basis which is finitary (a subset \({\mathcal F}\) of \(2^{E}\) is finitary if and only if each \(e\in E\) is in only finitely many elements of \({\mathcal F}\)), which contains only finite or infinite cycles (the latter here include infinite two-way paths). Given such a basis \({\mathcal F}=C_{1},C_{2},\dots\), let \(Z_{i}\) be i.i.d. Bernoulli random variables with mean \(1/2\) and form \(\sum Z_{i}C_{i}\), this is a uniform random even subgraph.

Returning to the finite case, we can couple the \(q=2\) random cluster model with the random even subgraph of \(G\): more precisely, if we have a realisation of the random-cluster model on \(G\) with parameters \(2p\in [0,1]\) and \(q=2\), a uniform random even subgraph of \(V\) with those edges is a random even subgraph of the original \(G\) with parameter \(p\). A slightly more involved algorithm deals with cases with \(p\in [1/2,1]\). This of course allows simulation of such graphs, for \(p\leq 1/2\): one samples from the random-cluster measure for \(q=2\) and probability \(2p\), using ‘coupling-from the-past’ and then flip a fair coin for each member of some maximal independent set of cycles in \(G\). Section 4 of the paper shows how to modify this idea to the case where \(p>1/2\).

Section 5 deals with even subgraphs of planar lattices, the headline result being that if \(G\) is a finite planar graph with dual \(G_{d}\) then a random even subgraph of \(G\) with parameter \(p\in (0,1/2]\) is dual to the set of edges of the Ising model whose endpoints have opposite spins to each other, on \(G_{d}\), for a certain \(\beta\) related to \(p\) by \(1-e^{-2\beta}=(1-2p)/(1-p)\). This allows the authors to analyze, via standard facts about the Ising model, the nature of the random even graphs.

We note that the family of even subgraphs can be identified with a vector subspace \({\mathcal E}\) of \(\{0,1\}^{| E|}\), with two subgraphs having sum the symmetric difference of their two edge sets. This also suggests the definition of \({\mathcal E}\) for the case where \(G\) is locally finite but infinite. One then shows that \({\mathcal E}\) has a basis which is finitary (a subset \({\mathcal F}\) of \(2^{E}\) is finitary if and only if each \(e\in E\) is in only finitely many elements of \({\mathcal F}\)), which contains only finite or infinite cycles (the latter here include infinite two-way paths). Given such a basis \({\mathcal F}=C_{1},C_{2},\dots\), let \(Z_{i}\) be i.i.d. Bernoulli random variables with mean \(1/2\) and form \(\sum Z_{i}C_{i}\), this is a uniform random even subgraph.

Returning to the finite case, we can couple the \(q=2\) random cluster model with the random even subgraph of \(G\): more precisely, if we have a realisation of the random-cluster model on \(G\) with parameters \(2p\in [0,1]\) and \(q=2\), a uniform random even subgraph of \(V\) with those edges is a random even subgraph of the original \(G\) with parameter \(p\). A slightly more involved algorithm deals with cases with \(p\in [1/2,1]\). This of course allows simulation of such graphs, for \(p\leq 1/2\): one samples from the random-cluster measure for \(q=2\) and probability \(2p\), using ‘coupling-from the-past’ and then flip a fair coin for each member of some maximal independent set of cycles in \(G\). Section 4 of the paper shows how to modify this idea to the case where \(p>1/2\).

Section 5 deals with even subgraphs of planar lattices, the headline result being that if \(G\) is a finite planar graph with dual \(G_{d}\) then a random even subgraph of \(G\) with parameter \(p\in (0,1/2]\) is dual to the set of edges of the Ising model whose endpoints have opposite spins to each other, on \(G_{d}\), for a certain \(\beta\) related to \(p\) by \(1-e^{-2\beta}=(1-2p)/(1-p)\). This allows the authors to analyze, via standard facts about the Ising model, the nature of the random even graphs.

Reviewer: David B. Penman (Colchester)