# A combinatorial identity on even spanning subgraphs in the Erdös-Renyi random graph with relations to the Ising model

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 \}$$.

• 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"? Dec 29 '19 at 20:24
• Thanks - I have added an explaination. Jan 1 '20 at 17:34
• Ah, thank you, then I proved something different, but possibly related. Should think. Jan 1 '20 at 19:00
• Yes - I start to thnik that one should somehow invoke combinatorics like in the switching lemma. Apr 4 '20 at 9:22

(warning: below $$\{v_1 \leftrightarrow v_2 \}$$ has different meaning than in OP)
\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)$$.