Random Even Graphs

  • Geoffrey Grimmett
  • Svante Janson


We study a random even subgraph of a finite graph $G$ with a general edge-weight $p\in(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\over2} p_{\rm c}$, where $p_{\rm c}$ is 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öwner evolutions (SLE).

Article Number