Random even graphs
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.
- Random currents expansion of the Ising model
- Random cluster dynamics for the Ising model is rapidly mixing
- Spins, percolation and height functions
- Emergent planarity in two-dimensional Ising models with finite-range interactions
- Critical surface of the hexagonal polygon model
- The 1-2 model
- Does Eulerian percolation on \(\mathbb Z^2\) percolate?
- On monotonicity and couplings of random currents and the loop-\(\mathrm{O}(1)\)-model
- Conformal invariance in random cluster models. I: Holomorphic fermions in the Ising model
- Sampling from the low temperature Potts model through a Markov chain on flows
- Uniform even subgraphs and graphical representations of Ising as factors of i.i.d.
- Long-range order for critical Book-Ising and Book-percolation
- Spectral independence via stability and applications to Holant-type problems
- On invariant generating sets for the cycle space
- A near-optimal zero-free disk for the Ising model
- Finite-size scaling of the high-dimensional Ising model in geometric representations
- Non-uniqueness of phase transitions for graphical representations of the Ising model on tree-like graphs
- The uniform even subgraph and its connection to phase transitions of graphical representations of the Ising model
- A general coupling for Ising models and beyond
- The high temperature Ising model on the triangular lattice is a critical Bernoulli percolation model
This page was built for publication: Random even graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028823)
