A question on exchangeable variables in Erdős-Rényi graphs

56 Views Asked by At

Let $H$ be a subgraph of the complete graph on $n$ vertices without isolated vertices, and let $\Gamma$ be the set of isomorphic copies of $H$. For any $\alpha\in \Gamma$, let $X_\alpha$ be the indicatrix of the event $\alpha\in G(n,p)$.

I am told that $\{X_\alpha\}$ is a sequence of exchangeable random variables, but I do not see how to prove it (apart from the fact that is suffices to prove exchangeability for permutations of type $(a,b)$).

Actually, I am not even sure this is true: it could be the case, for example, that $\{X_1=1,\dots, X_k=1\}$ implies $X_{k+1}=1$, while it does not necessarily imply $X_n=1$ (for example, if $H$ is a triangle, it could be the case that the existence of a certain number of triangles in $G$ implies the existence of another one without implying the existence of all the remaining ones). Am I right, or am I missing something?

1

There are 1 best solutions below

0
On

You are right that this is false, and in particular you are right that it is false for triangles.

Say the vertices of $G(n,p)$ are $1, 2, 3, 4, 5, \dots$ and we write $X_{abc}$ for the random variable which is $1$ if the subgraph induced by vertices $\{a,b,c\}$ is a triangle. Then $X_{123} = X_{124} = X_{134} = 1$ implies $X_{234}=1$, but does not imply $X_{345} = 1$, so the random variables are not exchangeable.

If we don't take the full set $\Gamma$, then we may be able to achieve an exchangeable set of random variables: for example, if we take a bunch of edge-disjoint copies of $H$. That's sufficient but not necessary: in the triangle example, the random variables $\{X_{123}, X_{124}, X_{125}, \dots, X_{12n}\}$ are exchangeable. But most ways that the copies of $H$ could share edges will immediately ruin exchangeability.