# zbMATH — the first resource for mathematics

Random even graphs. (English) Zbl 1214.05155
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.

##### MSC:
 05C80 Random graphs (graph-theoretic aspects) 60K35 Interacting random processes; statistical mechanics type models; percolation theory
##### Keywords:
random graph; even subgraph; Ising model; random cluster model
Full Text: