Random even graphs
Geoffrey Grimmett
Statistical Laboratory, Centre for Mathematical Sciences,
University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, U.K.
g.r.grimmett@statslab.cam.ac.uk
http://www.statslab.cam.ac.uk/∼grg/
Svante Janson
Department of Mathematics, Uppsala University,
PO Box 480, SE-751 06 Uppsala, Sweden
svante@math.uu.se
http://www.math.uu.se/∼svante/
Submitted: Oct 8, 2008; Accepted: Mar 28, 2009; Published: Apr 3, 2009
Mathematics Subject Classification: 05C80, 60K35
Abstract
We study a random even subgraph of a finite graph Gwith a general edge-weight
p∈(0,1). We demonstrate how it may be obtained from a certain random-cluster
measure on G, and we propose a sampling algorithm based on coupling from the
past. A random even subgraph of a planar lattice undergoes a phase transition at
the parameter-value 1
2pc, where pcis the critical point of the q= 2 random-cluster
model on the dual lattice. The properties of such a graph are discussed, and are
related to Schramm–L¨owner evolutions (SLE).
1 Introduction
Our purpose in this paper is to study a random even subgraph of a finite graph G= (V, E),
and to show how to sample such a subgraph. A subset Fof Eis called even if, for all
x∈V,xis incident to an even number of elements of F. We call the subgraph (V, F )
even if Fis even, and we write Efor the set of all even subsets Fof E. It is standard that
every even set Fmay be decomposed as an edge-disjoint union of cycles. Let p∈[0,1).
The random even subgraph of Gwith parameter pis that with law
ρp(F) = 1
ZEp|F|(1 −p)|E\F|, F ∈ E,(1.1)
where ZE=ZE
G(p) is the appropriate normalizing constant.
the electronic journal of combinatorics 16 (2009), #R46 1
We may express ρpas follows in terms of product measure on E. Let φpbe product
measure with density pon the configuration space Ω = {0,1}E. For ω∈Ω and e∈E,
we call e ω-open if ω(e) = 1, and ω-closed otherwise. Let ∂ω denote the set of vertices
x∈Vthat are incident to an odd number of ω-open edges. Then
ρp(F) = φp(ωF)
φp(∂ω =∅), F ∈ E,(1.2)
where ωFis the edge-configuration whose open edge-set is F. In other words, φpdescribes
the random subgraph of Gobtained by randomly and independently deleting each edge
with probability 1 −p, and ρpis the law of this random subgraph conditioned on being
even.
Random even graphs are closely related to the Ising model and the random-cluster
model on G, and we review these models briefly. Let β∈(0,∞) and
p= 1 −e−2β=2 tanh β
1 + tanh β.(1.3)
The Ising model on Ghas configuration space Σ = {−1,+1}V, and probability measure
πβ(σ) = 1
ZIexpβX
e∈E
σxσy, σ ∈Σ,(1.4)
where ZI=ZI
G(β) is the partition function that makes πβa probability measure, and
e=hx, yidenotes an edge with endpoints x,y. A spin-cluster of a configuration σ∈Σ
is a maximal connected subgraph of Geach of whose vertices vhas the same spin-value
σv. A spin-cluster is termed a kcluster if σv=kfor all vbelonging to the cluster. An
important quantity associated with the Ising model is the ‘two-point correlation function’
τβ(x, y) = πβ(σx=σy)−1
2=1
2πβ(σxσy), x, y ∈V, (1.5)
where P(f) denotes the expectation of a random variable funder the probability measure
P.
The random-cluster measure on Gwith parameters p∈(0,1) and q= 2 is given as
follows [it may be defined for general q > 0 but we are concerned here only with the case
q= 2]. Let
φp,2(ω) = 1
ZRC Y
e∈E
pω(e)(1 −p)1−ω(e)2k(ω)
=1
ZRC p|η(ω)|(1 −p)|E\η(ω)|2k(ω), ω ∈Ω,(1.6)
where k(ω) denotes the number of ω-open components on the vertex-set V,η(ω) = {e∈
E:ω(e) = 1}is the set of open edges, and ZRC =ZRC
G(p) is the appropriate normalizing
factor.
the electronic journal of combinatorics 16 (2009), #R46 2
The relationship between the Ising and random-cluster models on Gis well established,
and hinges on the fact that, in the notation introduced above,
τβ(x, y) = 1
2φp,2(x↔y),
where {x↔y}is the event that xand yare connected by an open path. See [12] for
an account of the random-cluster model. There is a relationship between the Ising model
and the random even graph also, known misleadingly as the ‘high-temperature expansion’.
This may be stated as follows. For completeness, we include a proof of this standard fact
at the end of the section, see also [3].
Theorem 1.7. Let 2p= 1 −e−2βwhere p∈(0,1
2), and consider the Ising model with
inverse temperature β. Then
πβ,2(σxσy) = φp(∂ω ={x, y})
φp(∂ω =∅), x, y ∈V, x 6=y.
A corresponding conclusion is valid for the product of σxiover any even family of
distinct xi∈V.
This note is laid out in the following way. In Section 2 we define a random even
subgraph of a finite or infinite graph, and we explain how to sample a uniform even
subgraph. In Section 3 we explain how to sample a non-uniform random even graph,
starting with a sample from a random-cluster measure. An algorithm for exact sampling
is presented in Section 4 based on the method of coupling from the past. The structure
of random even subgraphs of the square and hexagonal lattices is summarized in Section
5.
In a second paper [14], we study the asymptotic properties of a random even subgraph
of the complete graph Kn. Whereas the special relationship with the random-cluster and
Ising models is the main feature of the current work, the analysis of [14] is more analytic,
and extends to random graphs whose vertex degrees are constrained to lie in any given
subsequence of the non-negative integers.
Remark 1.8. The definition (1.1) may be generalized by replacing the single parameter
pby a family p= (pe:e∈E), just as sometimes is done for the random-cluster measure
(1.6), see for example [26]; we let
ρp(F) = 1
ZY
e∈F
peY
e/∈F
(1 −pe).(1.9)
For simplicity we will mostly consider the case of a single p.
Proof of Theorem 1.7. For σ∈Σ, ω∈Ω, let
Zp(σ, ω) = Y
e=hv,win(1 −p)δω(e),0+pσvσwδω(e),1o
=p|η(ω)|(1 −p)|E\η(ω)|Y
v∈V
σdeg(v,ω)
v,(1.10)
the electronic journal of combinatorics 16 (2009), #R46 3
where deg(v, ω) is the degree of vin the ‘open’ graph (V, η(ω)). Then
X
ω∈Ω
Zp(σ, ω) = Y
e=hv,wi
(1 −p+pσvσw) = Y
e=hv,wi
eβ(σvσw−1)
=e−β|E|exp
βX
e=hv,wi
σvσw
, σ ∈Σ.(1.11)
Similarly,
X
σ∈Σ
Zp(σ, ω) = 2|V|p|η(ω)|(1 −p)|E\η(ω)|1{∂ω=∅}, ω ∈Ω,(1.12)
and
X
σ∈Σ
σxσyZp(σ, ω) = 2|V|p|η(ω)|(1 −p)|E\η(ω)|1{∂ω={x,y}}, ω ∈Ω.(1.13)
By (1.11),
πβ,2(σxσy) = Pσ,ω σxσyZp(σ, ω)
Pσ,ω Zp(σ, ω),
and the claim follows by (1.12)–(1.13).
2 Uniform random even subgraphs
2.1 Finite graphs
In the case p=1
2in (1.1), every even subgraph has the same probability, so ρ1
2describes
a uniform random even subgraph of G. Such a random subgraph can be obtained as
follows.
We identify the family of all spanning subgraphs of G= (V, E) with the family 2E
of all subsets of E. This family can further be identified with {0,1}E=ZE
2, and is
thus a vector space over Z2; the addition is componentwise addition modulo 2 in {0,1}E,
which translates into taking the symmetric difference of edge-sets: F1+F2=F1△F2for
F1, F2⊆E.
The family of even subgraphs of Gforms a subspace Eof this vector space {0,1}E,
since F1+F2=F1△F2is even if F1and F2are even. (In fact, Eis the cycle space
Z1in the Z2-homology of Gas a simplicial complex.) In particular, the number of even
subgraphs of Gequals 2c(G)where c(G) = dim(E); c(G) is thus the number of independent
cycles in G, and, as is well known,
c(G) = |E| − |V|+k(G).(2.1)
the electronic journal of combinatorics 16 (2009), #R46 4
Proposition 2.2. Let C1,...,Ccbe a maximal set of independent cycles in G. Let
ξ1, . . . , ξcbe independent Be(1
2)random variables (i.e., the results of fair coin tosses).
Then PiξiCiis a uniform random even subgraph of G.
Proof. C1,...,Ccis a basis of the vector space Eover Z2.
One standard way of choosing C1,...,Ccis exploited in the next proposition. Another,
for planar graphs, is given by the boundaries of the finite faces; this will be used in Section
5. In the following proposition, we use the term spanning subforest of Gto mean a maximal
forest of G, that is, the union of a spanning tree from each component of G.
Proposition 2.3. Let (V, F )be a spanning subforest of G. Each subset Xof E\Fcan be
completed by a unique Y⊆Fto an even edge-set EX=X∪Y∈ E. Choosing a uniform
random subset X⊆E\Fthus gives a uniform random even subgraph EXof G.
Proof. It is easy to see, and well known, that each edge ei∈E\Fcan be completed by
edges in Fto a unique cycle Ci; these cycles form a basis of Eand the result follows by
Proposition 2.2. (It is also easy to give a direct proof.)
2.2 Infinite graphs
Here, and only here, we consider even subgraphs of infinite graphs. Let G= (V, E) be
a locally finite, infinite graph. We call a set F ⊂ 2Efinitary if each edge in Ebelongs
to only a finite number of elements in F. If Gis countable (for example, if Gis locally
finite and connected), then any finitary Fis necessarily countable. If F ⊂ 2Eis finitary,
then the (generally infinite) sum Px∈F xis a well-defined element of 2E, by considering
one coordinate (edge) at a time; if, for simplicity, F={xi:i∈I}, then Pi∈Ixiincludes
a given edge eif and only if elies in an odd number of the xi.
We can define the even subspace Eof 2Eas before. (Note that we need Gto be locally
finite in order to do so.) If Fis a finitary subset of E, then Px∈F x∈ E.
Afinitary basis of Eis a finitary subset F ⊂ E such that every element of Eis the sum
of a unique subset F′⊆ F; in other words, if the linear (over Z2) map 2F→ E defined by
summation is an isomorphism. (A finitary basis is not a vector-space basis in the usual
algebraic sense since the summations are generally infinite.)
We define an infinite cycle in Gto be a subgraph isomorphic to Z, i.e., a doubly infinite
path. (It is natural to regard such a path as a cycle passing through infinity.) Note that,
if Fis an even subgraph of G, then every edge e∈Fbelongs to some finite or infinite
cycle in F: if no finite cycle contains e, removal of ewould disconnect the component of
Fthat contains einto two parts; since Fis even both parts have to be infinite, so there
exist infinite rays from the endpoints of e, which together with eform an infinite cycle.
Proposition 2.4. The space Ehas a finitary basis. We may choose such a finitary basis
containing only finite or infinite cycles.
the electronic journal of combinatorics 16 (2009), #R46 5