For $G \sim G(n, 0.5)$, $I$ a $k$-set of vertices, and event $E_I = \{G[I] \cong K_k \text{ or } K_k^c \}$, how many events does $E_I$ depend on?

33 Views Asked by At

The note in my lecture says that $E_I$ is independent of all events with disjoint edge-sets, and so it depends on at most ${k \choose 2}\left({{n-2}\choose {k-2}}-1\right)$ other events.

I don't get this formula. Let $S$ be a set of $k$ vertices in $G$. I'd construct the events that $E_S$ depends on as follows: for a set $S'$ of $j$ vertices in $S$, with $j=2,...,k-1$, there are ${n-k} \choose {k-j}$ of $(k-j)$-sets in $G \setminus S$ which, together with $S'$, form some $k$-sets whose distinct events $E_S$ depends on. It seems to me the formular only takes into account the case $j = 2$ (with that extra bit of "$-1$" that I don't get).

1

There are 1 best solutions below

2
On BEST ANSWER

The formula is an overestimate.

There are $\binom k2$ ways to pick two vertices in $I$. For each one of them, there are $\binom{n-2}{k-2}$ sets of size $k$ containing those two vertices and possibly other vertices in $I$. One of those sets of size $k$ is $I$ itself; if we don't count it, there are $\binom{n-2}{k-2} -1$ other sets. Multiplying, we get that formula.

A set $J \ne I$ that shares $j>2$ vertices with $I$ will be counted multiple times; for each of the $\binom j2$ ways to pick two vertices in the overlap, $J$ will be one of the $\binom{n-2}{k-2}-1$ sets distinct from $I$ that shares those two vertices with $I$, so it will be counted $\binom j2$ times in total.

In your formula, on the other hand, we'd take $\binom k2 \binom{n-k}{k-2}$ to find the number of sets of size $k$ with overlap exactly $2$. Note the $n-k$ in the binomial coefficient rather than the $n-2$; that's how you make sure you don't pick any more vertices of $I$. If we did that, then you are right that we would have to consider overlaps of size $3, 4, \dots, k-1$ as well - but then the resulting sum $$ \sum_{j=2}^{k-1} \binom kj \binom{n-k}{k-j} $$ would be exact and not an overestimate.

It's not worth doing this, because the $j=2$ term dominates for small $k$, and so the overestimate is a simpler expression that's still very close to the truth.

The only thing I don't understand is this: if we're taking an overestimate anyway, why include the $-1$ when $\binom k2 \binom{n-2}{k-2}$ is simpler to work with?