Random even graphs (Q1028823)

One 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.