In the calculation on pages 82-83 of the book on Random Graphs by Janson et al they calculate the threshold for matchings in the random bipartite graph $\mathbb{G}(n,n,p)$.
They say that if $\mathbb{G}(n,n,p)$ does not contain a matching then some set $S$ must violate Halls theorem, that is $|S|>N(S)$. They point out that a minimal set $S$ which violates Halls theorem satisfies the following three conditions
(1) $|S|=|N(S)|+1$
(2) $|S| \leq \lceil n/2 \rceil $
(3) every vertex in $N(S)$ is adjacent to at least two vertices of $S$.
it then proceeds to say that if $s=|S|$ where $S$ is a minimal such set then w.h.p $s \geq 3$. The calculation for this is fairly simple.
Finally it says "let $\mathcal{A}$ denote the event that there is a minimal set $S$ of size $s \geq 3$ which violates Hall's condition. Then using $(1)-(3)$ and bounding by $\binom{s}{2}^{s-1}$ the number of choices is to realize $(3)$ we obtain"
$\mathbb{P}(\mathcal{A}) \leq \sum_{s=3}^{\lceil n/2 \rceil} \binom{n}{s}\binom{n}{s-1}\binom{s}{2}^{s-1}p^{2s-2}(1-p)^{s(n-s+1)}.$
Now i'm slightly confused regarding this calculation,
It's easy to see we consider every choice of $s$ vertices in one vertex class and every choice of $s-1$ vertices in the other vertex class giving us $\binom{n}{s}\binom{n}{s-1}$. Now given an instance of $s$ vertices in one vertex class and $s-1$ vertices in another we need to consider how many graphs there are between the sets of size $s$ and $s-1$.
It seems $\binom{s}{2}^{s-1}$ is an upper bound on the number of graphs in which each vertex in the neighborhood has degree 2, however surley this avoids so many edges between the two sets? Can anyone clarify this? I appreciate any help.
Here is my understanding of the term $${s\choose 2}^{s-1}p^{2s-2}(1-p)^{s(n-s+1)}.$$
Fix $s$ vertices $U$ from the left partition and $s-1$ vertices $V$ from the right partition. We want to bound the probability that $V = N(U)$ and each vertex in $V$ has at least two neighbors in $U$. Now, for each vertex in $V$, pick two vertices in $U$ to be two of its neighbors. For each such choice, the probability is bounded by $p^{2s-2}(1-p)^{s(n-s+1)}$. There are ${s\choose 2}^{s-1}$ many such choices. The term in consideration is the result of application of the union bound.