Some probabilistic reasoning in graphs.

Question

I’m reading the following scenario:

$\bullet$ Let $G$ be an $n$-vertex graph.
$\bullet$ Sample $s$ vertices from $V(G)$ independently, with repetition. Let $S$ be the set of vertices selected.
$\bullet$ Let $B = \{v \in V(G): \forall s \in S, \{v,s\} \in E(G)\}$
$\bullet$ Let $T$ be a set of $t$ vertices with at most $m$ common neighbours.
$\bullet$ To have $T \subset B$, need to select $S$ from these common neighbours.
$\bullet \Rightarrow \mathbb{P}(T \subset B) \leq \left( \frac{m}{n} \right)^s$

The way the last statement comes about, from my understanding, is that, given the set of common neighbours of size $m$, any vertex in the graph has at most $\frac{m}{n}$ a chance of being in this set. $S$ has $s$ members, hence the number $\left( \frac{m}{n} \right)^s$.

But how about this line of reasoning? We have $\mathbb{P}(T \subset B) = \mathbb{P}(\text{ the $m$ given vertices} \in S)$. Each of those $m$ vertices has at most $\frac{s}{n}$ a chance to be in $S$. The set has $m$ members, hence $\left(\frac{s}{n}\right)^m$. Is this equivalent to the above? If not, why?

Also please correct me if any of the above sentences doesn’t make sense.

Answer 1

The flaw in your reasoning is the claim that $\mathbb{P}(T \subset B) = \mathbb{P}(\text{ the $m$ given vertices} \in S)$, which is false.

In order for $T \subseteq B$, we need to make sure that every vertex of $S$ is one of the common neighbors of $T$. That has probability $(\frac mn)^s$. The probability $(\frac sn)^m$ is an upper bound on the probability that every common neighbor of $T$ was chosen to be a vertex of $S$ which is a different event, for two reasons:

• Even if every common neighbor of $T$ gets chosen to be a vertex of $S$, as soon as we choose a single other vertex to be in $S$, then $B$ will no longer contain $T$.
• To have $T \subseteq B$, we don't have to pick all $m$ common neighbors of $T$ to put in $S$. To take an extreme example, since $S$ is chosen with replacement, maybe we just pick the same vertex $v$, which is a common neighbor of $T$, $s$ times. In that case, $B$ will just be $N(v)$, which contains $T$.

---

Maybe it helps understanding to describe dependent random choice in a different way. Instead of choosing the set $S$, we'll choose a sequence of sets $B_1, B_2, \dots, B_s$ as follows: each $B_i$ is $N(v)$ for some $v \in V$ chosen independently and uniformly at random. Then, we take $B = \bigcap_{i=1}^s B_i$.

In order to have $T \subseteq B$, we must have $T \subseteq B_i$ for every $i=1, 2, \dots, s$. For each $i$, we have $T \subseteq B_i$ with probability at most $\frac mn$ - because we are given that there are at most $m$ vertices $v \in V$ such that $T \subseteq N(v)$. Therefore $T \subseteq B$ with probability $(\frac mn)^s$: the probability that $T \subseteq B_i$ happens for every $i=1, \dots, s$.