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

(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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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