[proofplan] Choose $r$ vertices of $Y$ independently and uniformly at random, allowing repetitions, and let $S \subset X$ be their common neighbourhood. The expected size of $S$ is large because the average degree from $X$ into $Y$ is at least $\delta N$, while the expected number of ordered pairs in $S^2$ with fewer than $L$ common neighbours is small. We combine these two estimates by an averaging argument that selects one outcome for which $S$ is large and the bad-pair count is controlled relative to $|S|$. Finally, we take $X'=S$ and rewrite the bound using $|S|\geq \delta^rM/2$, which gives the corrected quadratic estimate with the tracked constants. [/proofplan] [step:Define the random common neighbourhood] For each $x \in X$, define the neighbourhood of $x$ in $Y$ by \begin{align*} N_\Gamma(x) := \{y \in Y : (x,y) \in \Gamma\}. \end{align*} Define the degree of $x$ by \begin{align*} d(x) := |N_\Gamma(x)|. \end{align*} Let \begin{align*} Y_1,\dots,Y_r : \Omega \to Y \end{align*} be independent random variables, each uniformly distributed on $Y$, on some finite probability space $(\Omega,\mathcal F,\mathbb P)$. Define the random subset \begin{align*} S: \Omega &\to \mathcal P(X) \\ \omega &\mapsto \{x \in X : Y_i(\omega) \in N_\Gamma(x) \text{ for every } i \in \{1,\dots,r\}\}. \end{align*} Equivalently, $S(\omega)$ is the common neighbourhood in $X$ of the sampled ordered $r$-tuple $(Y_1(\omega),\dots,Y_r(\omega))$. For each $x \in X$, define the indicator random variable \begin{align*} I_x: \Omega &\to \{0,1\} \\ \omega &\mapsto \mathbb{1}_{\{x \in S(\omega)\}}. \end{align*} Since the $Y_i$ are independent and uniform on $Y$, \begin{align*} \mathbb E[I_x] = \mathbb P(x \in S) = \prod_{i=1}^r \mathbb P(Y_i \in N_\Gamma(x)) = \left(\frac{d(x)}{N}\right)^r. \end{align*} Therefore, by linearity of expectation, \begin{align*} \mathbb E[|S|] = \sum_{x \in X} \mathbb E[I_x] = \sum_{x \in X}\left(\frac{d(x)}{N}\right)^r. \end{align*} [/step] [step:Lower bound the expected size of the random set] The edge-count hypothesis gives \begin{align*} \sum_{x \in X} d(x) = |\Gamma| \geq \delta MN. \end{align*} Hence the average of the nonnegative numbers \begin{align*} \frac{d(x)}{N}, \qquad x \in X, \end{align*} is at least $\delta$: \begin{align*} \frac{1}{M}\sum_{x \in X}\frac{d(x)}{N} \geq \delta. \end{align*} Since the function $t \mapsto t^r$ is convex on $[0,\infty)$ for every integer $r \geq 1$, [Jensen's inequality](/theorems/1977) for the uniform probability measure on the finite set $X$ gives \begin{align*} \frac{1}{M}\sum_{x \in X}\left(\frac{d(x)}{N}\right)^r \geq \left(\frac{1}{M}\sum_{x \in X}\frac{d(x)}{N}\right)^r \geq \delta^r. \end{align*} Thus \begin{align*} \mathbb E[|S|] \geq \delta^r M. \end{align*} [guided] We now convert the density assumption into a lower bound for the expected size of $S$. The degree $d(x)$ counts how many vertices of $Y$ are adjacent to $x$, so summing $d(x)$ over all $x \in X$ counts each edge of $\Gamma$ exactly once. Therefore \begin{align*} \sum_{x \in X} d(x) = |\Gamma| \geq \delta MN. \end{align*} After dividing by $MN$, this says that the average value of the normalized degrees \begin{align*} \frac{d(x)}{N}, \qquad x \in X, \end{align*} is at least $\delta$: \begin{align*} \frac{1}{M}\sum_{x \in X}\frac{d(x)}{N} \geq \delta. \end{align*} The expected size of $S$ is the sum of the $r$-th powers of these normalized degrees. Since $r \geq 1$, the map $t \mapsto t^r$ is convex on $[0,\infty)$. We apply [Jensen's inequality](/theorems/9) with respect to the uniform probability measure on the finite set $X$, which assigns mass $1/M$ to each point of $X$. Applied to the nonnegative numbers $d(x)/N$, indexed by $x \in X$, Jensen's inequality gives \begin{align*} \frac{1}{M}\sum_{x \in X}\left(\frac{d(x)}{N}\right)^r \geq \left(\frac{1}{M}\sum_{x \in X}\frac{d(x)}{N}\right)^r. \end{align*} Using the lower bound on the average degree, \begin{align*} \left(\frac{1}{M}\sum_{x \in X}\frac{d(x)}{N}\right)^r \geq \delta^r. \end{align*} Multiplying by $M$ yields \begin{align*} \mathbb E[|S|] = \sum_{x \in X}\left(\frac{d(x)}{N}\right)^r \geq \delta^r M. \end{align*} [/guided] [/step] [step:Estimate the expected number of bad ordered pairs in $S^2$] Define the set of bad ordered pairs \begin{align*} \mathcal B := \{(x_1,x_2) \in X \times X : |N_\Gamma(x_1) \cap N_\Gamma(x_2)| < L\}. \end{align*} For each $(x_1,x_2) \in \mathcal B$, define \begin{align*} J_{x_1,x_2}: \Omega &\to \{0,1\} \\ \omega &\mapsto \mathbb{1}_{\{x_1 \in S(\omega)\}}\mathbb{1}_{\{x_2 \in S(\omega)\}}. \end{align*} Then $J_{x_1,x_2}=1$ exactly when every sampled vertex $Y_i$ lies in $N_\Gamma(x_1)\cap N_\Gamma(x_2)$. Therefore independence and uniformity give \begin{align*} \mathbb E[J_{x_1,x_2}] = \left(\frac{|N_\Gamma(x_1)\cap N_\Gamma(x_2)|}{N}\right)^r < \left(\frac{L}{N}\right)^r. \end{align*} Let \begin{align*} Z: \Omega &\to \mathbb N \cup \{0\} \\ \omega &\mapsto |\mathcal B \cap (S(\omega)\times S(\omega))| \end{align*} be the number of bad ordered pairs lying in $S(\omega)^2$. Since $|\mathcal B| \leq M^2$, linearity of expectation gives \begin{align*} \mathbb E[Z] = \sum_{(x_1,x_2)\in \mathcal B}\mathbb E[J_{x_1,x_2}] \leq M^2\left(\frac{L}{N}\right)^r. \end{align*} [guided] A pair $(x_1,x_2)$ is bad if the two vertices have fewer than $L$ common neighbours in $Y$. We collect all such ordered pairs into \begin{align*} \mathcal B := \{(x_1,x_2) \in X \times X : |N_\Gamma(x_1) \cap N_\Gamma(x_2)| < L\}. \end{align*} The word “ordered” matters: $(x_1,x_2)$ and $(x_2,x_1)$ are counted separately unless $x_1=x_2$. For a fixed bad ordered pair $(x_1,x_2) \in \mathcal B$, both vertices lie in $S$ precisely when every sampled vertex $Y_i$ is adjacent to both $x_1$ and $x_2$. That is, each $Y_i$ must lie in the common neighbourhood $N_\Gamma(x_1)\cap N_\Gamma(x_2)$. Define \begin{align*} J_{x_1,x_2}: \Omega &\to \{0,1\} \\ \omega &\mapsto \mathbb{1}_{\{x_1 \in S(\omega)\}}\mathbb{1}_{\{x_2 \in S(\omega)\}}. \end{align*} Then, using independence of $Y_1,\dots,Y_r$ and uniformity on $Y$, \begin{align*} \mathbb E[J_{x_1,x_2}] = \mathbb P(x_1 \in S \text{ and } x_2 \in S) = \left(\frac{|N_\Gamma(x_1)\cap N_\Gamma(x_2)|}{N}\right)^r. \end{align*} Because $(x_1,x_2)$ is bad, the numerator is strictly less than $L$, so \begin{align*} \mathbb E[J_{x_1,x_2}] < \left(\frac{L}{N}\right)^r. \end{align*} Now define the random variable \begin{align*} Z: \Omega &\to \mathbb N \cup \{0\} \\ \omega &\mapsto |\mathcal B \cap (S(\omega)\times S(\omega))|. \end{align*} This counts exactly the bad ordered pairs that survive inside $S(\omega)^2$. Since \begin{align*} Z = \sum_{(x_1,x_2)\in \mathcal B} J_{x_1,x_2}, \end{align*} linearity of expectation gives \begin{align*} \mathbb E[Z] = \sum_{(x_1,x_2)\in \mathcal B}\mathbb E[J_{x_1,x_2}] \leq |\mathcal B|\left(\frac{L}{N}\right)^r. \end{align*} Finally, $\mathcal B \subset X\times X$, so $|\mathcal B|\leq M^2$. Hence \begin{align*} \mathbb E[Z] \leq M^2\left(\frac{L}{N}\right)^r. \end{align*} [/guided] [/step] [step:Choose one random outcome with large size and controlled bad pairs] Set \begin{align*} A := \delta^r M, \qquad B := M^2\left(\frac{L}{N}\right)^r. \end{align*} From the preceding steps, $\mathbb E[|S|]\geq A$ and $\mathbb E[Z]\leq B$. Therefore \begin{align*} \mathbb E\left[|S|-\frac{A}{2B}Z\right] = \mathbb E[|S|]-\frac{A}{2B}\mathbb E[Z] \geq A-\frac{A}{2} = \frac{A}{2}. \end{align*} Thus there exists an outcome $\omega_0 \in \Omega$ such that \begin{align*} |S(\omega_0)|-\frac{A}{2B}Z(\omega_0)\geq \frac{A}{2}. \end{align*} Define \begin{align*} X' := S(\omega_0). \end{align*} The displayed inequality first gives \begin{align*} |X'| = |S(\omega_0)| \geq \frac{A}{2}=\frac{\delta^r M}{2}. \end{align*} It also gives \begin{align*} Z(\omega_0) \leq \frac{2B}{A}|S(\omega_0)| = 2\frac{M^2(L/N)^r}{\delta^r M}|X'| = 2M\left(\frac{L}{\delta N}\right)^r |X'|. \end{align*} [guided] We need one sample for which two things happen at once: the set $S$ is large, and the bad-pair count $Z$ is not too large. Instead of applying two separate averaging arguments, we average a single linear combination that rewards large $|S|$ and penalizes large $Z$. Define \begin{align*} A := \delta^r M, \qquad B := M^2\left(\frac{L}{N}\right)^r. \end{align*} The previous two steps proved \begin{align*} \mathbb E[|S|]\geq A, \qquad \mathbb E[Z]\leq B. \end{align*} Consider the random variable \begin{align*} |S|-\frac{A}{2B}Z : \Omega \to \mathbb R. \end{align*} Linearity of expectation gives \begin{align*} \mathbb E\left[|S|-\frac{A}{2B}Z\right] = \mathbb E[|S|]-\frac{A}{2B}\mathbb E[Z]. \end{align*} Using $\mathbb E[|S|]\geq A$ and $\mathbb E[Z]\leq B$, we obtain \begin{align*} \mathbb E\left[|S|-\frac{A}{2B}Z\right] \geq A-\frac{A}{2B}B = \frac{A}{2}. \end{align*} Since the average value of this random variable is at least $A/2$, at least one outcome $\omega_0 \in \Omega$ satisfies \begin{align*} |S(\omega_0)|-\frac{A}{2B}Z(\omega_0)\geq \frac{A}{2}. \end{align*} Now set \begin{align*} X' := S(\omega_0). \end{align*} Because $Z(\omega_0)\geq 0$, the same inequality implies \begin{align*} |X'|=|S(\omega_0)|\geq \frac{A}{2}=\frac{\delta^rM}{2}. \end{align*} Also, rearranging the inequality gives \begin{align*} \frac{A}{2B}Z(\omega_0) \leq |S(\omega_0)|-\frac{A}{2} \leq |S(\omega_0)|, \end{align*} and hence \begin{align*} Z(\omega_0) \leq \frac{2B}{A}|S(\omega_0)|. \end{align*} Substituting the definitions of $A$ and $B$ gives \begin{align*} Z(\omega_0) \leq 2\frac{M^2(L/N)^r}{\delta^r M}|X'| = 2M\left(\frac{L}{\delta N}\right)^r |X'|. \end{align*} [/guided] [/step] [step:Rewrite the bad-pair estimate in terms of $|X'|^2$] The estimate obtained in the previous step is \begin{align*} Z(\omega_0) \leq 2M\left(\frac{L}{\delta N}\right)^r |X'|. \end{align*} The size lower bound from the previous step gives \begin{align*} |X'|\geq \frac{\delta^rM}{2}. \end{align*} Rearranging this inequality gives \begin{align*} M \leq \frac{2|X'|}{\delta^r}. \end{align*} Substituting this upper bound for $M$ into the previous estimate yields \begin{align*} Z(\omega_0) &\leq 2\left(\frac{2|X'|}{\delta^r}\right)\left(\frac{L}{\delta N}\right)^r |X'| \\ &= 4\frac{L^r}{\delta^{2r}N^r}|X'|^2 \\ &= 4\left(\frac{L}{\delta^2 N}\right)^r |X'|^2. \end{align*} Since $Z(\omega_0)$ is exactly the number of ordered pairs $(x_1,x_2)\in X'\times X'$ with fewer than $L$ common neighbours in $Y$, this proves the corrected bad-pair estimate. Together with $|X'|\geq \delta^rM/2$, this completes the proof. [guided] The previous step produced the set $X'=S(\omega_0)$ and proved two estimates. First, \begin{align*} Z(\omega_0) \leq 2M\left(\frac{L}{\delta N}\right)^r |X'|. \end{align*} Second, \begin{align*} |X'|\geq \frac{\delta^rM}{2}. \end{align*} The goal is to convert the remaining factor $M$ in the first estimate into another factor of $|X'|$, because the theorem bounds the number of bad pairs by a constant times $|X'|^2$. Rearranging the size lower bound gives \begin{align*} M \leq \frac{2|X'|}{\delta^r}. \end{align*} No additional weakening is needed here: this inequality follows directly by multiplying $|X'|\geq \delta^rM/2$ by $2/\delta^r$, and $\delta^r>0$ because $0<\delta\leq 1$ and $r\geq 1$. Now substitute this bound for $M$ into the estimate for $Z(\omega_0)$: \begin{align*} Z(\omega_0) &\leq 2M\left(\frac{L}{\delta N}\right)^r |X'| \\ &\leq 2\left(\frac{2|X'|}{\delta^r}\right)\left(\frac{L}{\delta N}\right)^r |X'| \\ &= 4\frac{L^r}{\delta^{2r}N^r}|X'|^2 \\ &= 4\left(\frac{L}{\delta^2 N}\right)^r |X'|^2. \end{align*} By the definition of $Z$, the value $Z(\omega_0)$ counts exactly the ordered pairs $(x_1,x_2)\in X'\times X'$ such that $|N_\Gamma(x_1)\cap N_\Gamma(x_2)|<L$. Therefore the number of ordered bad pairs in $X'^2$ is at most \begin{align*} 4\left(\frac{L}{\delta^2 N}\right)^r |X'|^2. \end{align*} Together with the already proved lower bound \begin{align*} |X'|\geq \frac{\delta^rM}{2}, \end{align*} this proves the corrected theorem statement. [/guided] [/step]