Let $x \in \lbrack 0,1 \rbrack$. Then for any finite graph $G$ consider the Erdös-Renyi random graph where we independently keep each of the edges with probability $x$. Denote the corresponding probability measure $P_x$. An even spanning subgraph of $G$ is a subgraph where all the vertices are kept and some of the edges such that each vertex has even degree. Denote the set of even spanning subgraphs of G by $\text{ess}(G)$. For an even spanning subgraph $g$ let $O(g)$ be the event that all the edges are kept. By some knowledge about geometric representations of the Ising model I happen to know that for every pair of vertices $v_1,v_2 \in G$ we have \begin{align*} \sum_{g_1, g_2 \in \text{ess}(G)} \frac{ P_{x^2} \left( \{v_1 \leftrightarrow v_2 \}, O(g_1), O(g_2) \right)}{P_x(O(g_1))} = \sum_{g_1, g_2 \in \text{ess}(G)} P_x( \{v_1 \leftrightarrow v_2 \}, O(g_1)) P_x( \{v_1 \leftrightarrow v_2 \}, O(g_2)) \end{align*} Here $\{v_1 \leftrightarrow v_2 \}$ is the event that there is a path of kept edges in $G$ connecting $v_1$ and $v_2$. However, this is a problem purely on Erdös-Renyi random graphs, but I can't find a combinatorial proof of this which could maybe give some insights on how the relation generalizes beyond the class of events $\{ v_1 \leftrightarrow v_2 \}$.

  • $\begingroup$ The bracket in the denominator is not closed, and in the numerator too. Also am I correct that the event in the numerator read as "the edge $\{ v_1 \leftrightarrow v_2 \}$ is kept and either all edges of $g_1$ are kept or all edges of $g_2$ are kept or both"? $\endgroup$ Commented Dec 29, 2019 at 20:24
  • $\begingroup$ Thanks - I have added an explaination. $\endgroup$ Commented Jan 1, 2020 at 17:34
  • $\begingroup$ Ah, thank you, then I proved something different, but possibly related. Should think. $\endgroup$ Commented Jan 1, 2020 at 19:00
  • $\begingroup$ Yes - I start to thnik that one should somehow invoke combinatorics like in the switching lemma. $\endgroup$ Commented Apr 4, 2020 at 9:22

1 Answer 1


(warning: below $\{v_1 \leftrightarrow v_2 \}$ has different meaning than in OP)

Let me prove a slightly different identity

\begin{align*} x\sum_{g_1, g_2 \in \text{ess}(G)} \frac{ P_{x^2} \left( \{v_1 \leftrightarrow v_2 \}, O(g_1), O(g_2) \right)}{P_x(\{v_1 \leftrightarrow v_2 \},O(g_1))} = \\\sum_{g_1, g_2 \in \text{ess}(G)} P_x( \{v_1 \leftrightarrow v_2 \}, O(g_1)) P_x( \{v_1 \leftrightarrow v_2 \}, O(g_2)). \end{align*}

If $E_i$ denotes edge set of $g_i$ and $e=\{ v_1 \leftrightarrow v_2 \}$, then LHS may be written as $$\sum_{g_1,g_2} x^{2|E_1\cup E_2\cup e|-|E_1\cup e|+1}=\sum_{g_1,g_2} x^{|E_2\cup e|+|(E_1\Delta E_2)\cup e|},$$ where we apply the general identity $2|A\cup B|-|A|=|B|+|A\Delta B|$ for $A=E_1\cup e$, $B=E_2\cup e$, and $|(E_1\Delta E_2)\cup e|=1+|A\Delta B|$. It remains to change the pair $(g_1,g_2)$ in RHS of my identity onto pairs $(g_1\Delta g_2,g_2)$.

I am still not sure what exactly do you mean (there are several typos at least), but possibly something provable along these lines.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.