Proof. Throughout this lemma, we make frequent use of the identity

\begin{equation*} \left(\substack{a-c\\[4pt] b-c}\right) /\left(\substack{a\\[4pt] b}\right)=\left(\substack{b\\[4pt] c}\right)/\left(\substack{a\\[4pt] c}\right),\end{equation*}

which follows from the simple combinatorial identity $\left(\substack{a\\[4pt] b}\right)\left(\substack{b\\[4pt] c}\right)=\left(\substack{a\\[4pt] c}\right)\left(\substack{a-c\\[4pt] b-c}\right)$ .

For $t\le r$ , define

\begin{align*}{\mathcal{B}}_{t}=\{(S,W)\;:\; S\in \mathcal{H},\ W\in{\left(\substack{v\\[4pt] pn}\right)},\ (S,W)\textrm{ is }&k\textrm{-bad},\ |S\cap W|=t\}. \end{align*}

Observe that the quantity we wish to bound is $\sum _{t} |{\mathcal{B}}_{t}|$ , so it suffices to bound each term of this sum. From now on, we fix some $t$ and define

\begin{equation*}w=pn-t.\end{equation*}

At this point, we need to count the number of elements in ${\mathcal{B}}_t$ , and there are several natural approaches that could be used. One way would be to first pick any $S\in \mathcal{H}$ and then count how many $W$ satisfy $(S,W)\in{\mathcal{B}}_{t}$ . Another approach would be to pick any set $Z$ of size $r+w$ (which will be the size of $S\cup W$ since $|S\cap W|=t$ ) and then bound how many $S,W\subseteq Z$ have $(S,W)\in{\mathcal{B}}_{t}$ . For some pairs, the first approach is more efficient, and for others the second is. In particular, the second approach will be more effective whenever $Z=S\cup W$ contains few elements of ${\mathcal{B}}_{t}$ .

With this in mind, we say that a set $Z$ is pathological if

\begin{equation*}|\{S\in \mathcal {H}\;:\; S\subseteq Z,\ (S,Z\setminus S)\textrm { is }k\textrm {-bad}\}|\gt N,\end{equation*}

where

\begin{equation*}N\;:\!=\;(C/2)^{-k/2}|\mathcal {H}|\left(\substack{n-r\\[4pt] w}\right)/\left(\substack{n\\[4pt] r+w}\right)=(C/2)^{-k/2}|\mathcal {H}|\left(\substack{r+w\\[4pt] r}\right)/\left(\substack{n\\[4pt] r}\right),\end{equation*}

and we say that $Z$ is non-pathological otherwise. We say that a pair $(S,W)$ is pathological if the set $S\cup W$ is pathological and that $(S,W)$ is non-pathological otherwise.

Proof. We identify each of the non-pathological pairs $(S,W)$ by specifying $S\cup W$ , then $S$ , then $S\cap W$ .

Observe that $S\cup W$ is a non-pathological set of size $r+w$ , and in particular there are at most $\left(\substack{n\\[4pt] r+w}\right)$ ways to make this first choice. Fix such a non-pathological set $Z$ of size $r+w$ . As noted before the statement of Lemma 2.1, if $(S,W)$ is $k$ -bad with $S\cup W= Z$ , then $(S,Z\setminus S)$ is also $k$ -bad. Because $Z$ is non-pathological, there are at most $N$ choices for $S$ such that $(S,Z\setminus S)$ is $k$ -bad. Given $S$ , there are at most $\left(\substack{r\\[4pt] t}\right)$ choices for $S\cap W$ . Multiplying the number of choices at each step gives the stated result.

Proof. We identify these pairs by first specifying $S\in \mathcal{H}$ , then $S\cap W$ , then $W\setminus S$ .

Note that $S$ and $S\cap W$ can be specified in at most $|\mathcal{H}|\cdot\left(\substack{r\\[4pt] t}\right)$ ways, and from now on we fix such a choice of $S$ and $S\cap W$ . It remains to specify $W\setminus S$ , which will be some element of $\left(\substack{V \setminus S\\[4pt] w}\right)$ . Thus it suffices to count the number of $W'\in{\left(\substack{V \setminus S\\[4pt] w}\right)}$ such that $(S,W')$ is both $k$ -bad and pathological.

For $W'\in{\left(\substack{V\setminus S\\[4pt] w}\right)}$ , define

\begin{equation*}{\mathcal {S}}(W')=|\{S'\in \mathcal {H}\;:\;S'\subseteq S\cup W',\ |S'\cap S|\ge k\}|.\end{equation*}

Observe that if $(S,W')$ is $k$ -bad, then every edge $S'\subseteq S\cup W'$ has $|S'\cap S|\ge k$ (since $|S'\cap S|\ge |S'\setminus W'|$ ), so the $W'$ we wish to count satisfy

\begin{equation*}{\mathcal {S}}(W')=|\{S'\in \mathcal {H}\;:\; S'\subseteq S\cup W'\}|.\end{equation*}

If $(S,W')$ is pathological, then this latter set has size at least $N$ . In total, if ${\textbf{W}}'$ is chosen uniformly at random from $\left(\substack{V \setminus S\\[4pt] w}\right)$ , then

(1) \begin{equation}{\mathbb{P}}[(S,{\textbf{W}}')\textrm{ is }k\textrm{-bad and pathological}]\le{\mathbb{P}}[{\mathcal{S}}({\textbf{W}}')\ge N]\le \frac{{\mathbb{E}}[{\mathcal{S}}({\textbf{W}}')]}{N}, \end{equation}

where this last step used Markov’s inequality. It remains to upper bound ${\mathbb{E}}[{\mathcal{S}}({\textbf{W}}')]$ .

Let

\begin{equation*}m_j(S)=|\{S'\in \mathcal {H}\;:\; |S\cap S'|=j\}|,\end{equation*}

and observe that for any $S'$ with $|S\cap S'|=j$ , the number of $W'\in{\left(\substack{V \setminus S\\[4pt] w}\right)}$ with $S'\subseteq S\cup W'$ is exactly $\left(\substack{n-2r+j\\[4pt] w-r+j}\right)$ . With this we see that

(2) \begin{align}{\mathbb{E}}[{\mathcal{S}}({\textbf{W}}')]=\sum _{j\ge k} m_j(S) \frac{\left(\substack{n-2r+j\\[4pt] w-r+j}\right)}{{\left(\substack{n-r\\[4pt] w}\right)}}&=\sum _{j\ge k} m_j(S) \frac{\left(\substack{w\\[4pt] r-j}\right)}{{\left(\substack{n-r\\[4pt] r-j}\right)}}=\frac{{\left(\substack{r+w\\[4pt] r}\right)}}{{\left(\substack{n\\[4pt] r}\right)}}\sum _{j\ge k} m_j(S) \frac{{\left(\substack{w\\[4pt] r-j}\right)}}{{\left(\substack{n-r\\[4pt] r-j}\right)}}\cdot \frac{{\left(\substack{n\\[4pt] r+w}\right)}}{{\left(\substack{n-r\\[4pt] w}\right)}}. \end{align}

Because $\mathcal{H}$ is $(q;\;r,k)$ -spread, we have for each $j\ge k$ in the sum that

(3) \begin{equation} m_j(S)\le M_j(S)\le q^j |\mathcal{H}|. \end{equation}

For integers $x,y$ , define the falling factorial $(x)_y\;:\!=\;x(x-1)\cdots (x-y+1)$ . With this we have

(4) \begin{align} \frac{{\left(\substack{w\\[4pt] r-j}\right)}}{{\left(\substack{n-r\\[4pt] r-j}\right)}}\cdot \frac{{\left(\substack{n\\[4pt] r+w}\right)}}{{\left(\substack{n-r\\[4pt] w}\right)}}&=\frac{(w)_{r-j}}{(n-r)_{r-j}}\cdot \frac{(n)_{r}}{(r+w)_r}\le \left (\frac{w}{n-r}\right )^{r-j}\cdot \left (\frac{n-r}{w}\right )^r=\left (\frac{w}{n-r}\right )^{-j}\le (Cq/2)^{-j}, \end{align}

where the first inequality used $w\le pn\le \frac{1}{2} n\le n-r$ , and the second inequality used

\begin{equation*}w=pn-t\ge pn-r\ge pn/2=Cqn/2.\end{equation*}

Combining (2), (3), and (4) shows that

\begin{equation*}{\mathbb {E}}[{\mathcal {S}}({\textbf {W}}')]\le \frac {{\left(\substack{r+w\\[4pt] r}\right)}}{{\left(\substack{n\\[4pt] r}\right)}} |\mathcal {H}|(C/2)^{-k}\cdot \sum _{j\ge k} (C/2)^{k-j}\le \frac {{\left(\substack{r+w\\[4pt] r}\right)}}{{\left(\substack{n\\[4pt] r}\right)}} |\mathcal {H}|(C/2)^{-k}\cdot 2,\end{equation*}

where this last step used $C\ge 4$ . Plugging this into (1) shows that the number of $W'\in{\left(\substack{V \setminus S\\[4pt] w}\right)}$ such that $(S,W')$ is $k$ -bad and pathological is at most

\begin{equation*} 2(C/2)^{-k} |\mathcal {H}|\frac {{\left(\substack{r+w\\[4pt] r}\right)}}{{\left(\substack{n\\[4pt] r}\right)} N}\cdot {\left(\substack{n-r\\[4pt] w}\right)}= 2(C/2)^{-k/2}\cdot {\left(\substack{n-r\\[4pt] w}\right)}.\end{equation*}

Combining this with the fact that there were $|\mathcal{H}|\cdot{\left(\substack{r\\[4pt] t}\right)}$ ways of choosing $S$ and $S\cap W$ gives the claim.

Proof. Let $W'$ be a random set of $V$ obtained by including each vertex independently and with probability $\alpha/2$ . Let $X=|\{S\in \mathcal{H}\;:\; S\subseteq W'\}|$ and define $m_j(S)$ to be the number of $S'\in \mathcal{H}$ with $|S\cap S'|=j$ . Note that ${\mathbb{E}}[X]=(\alpha/2)^r|\mathcal{H}|$ and that

\begin{align*} \text{Var}(X)&\le (\alpha/2)^{2r}\sum _{S,S'\in \mathcal{H},\ S\cap S'\ne \emptyset } (\alpha/2)^{-|S\cap S'|} =(\alpha/2)^{2r}\sum _{S\in \mathcal{H}}\sum _{j=1}^r (\alpha/2)^{-j} \cdot m_j(S)\\ &\le (\alpha/2)^{2r}\sum _{S\in \mathcal{H}}\sum _{j=1}^r (\alpha/2)^{-j} \cdot q^j |\mathcal{H}| =(\alpha/2)^{2r}\sum _{j=1}^r (\alpha/2q)^{-j} |\mathcal{H}|^2\\&={\mathbb{E}}[X]^2 (\alpha/2q)^{-1} \sum _{j=1}^{r} (\alpha/2q)^{1-j}\le 4{\mathbb{E}}[X]^2 q\alpha ^{-1}, \end{align*}

where the second inequality used that $\mathcal{H}$ being $(q;\;r,1)$ -spread implies $m_j(S)\le q^j |\mathcal{H}|$ for all $S\in \mathcal{H}$ and $j\ge 1$ , and the last inequality used $\alpha/2q\ge 2$ . By Chebyshev’s inequality we have

\begin{equation*}{\mathbb {P}}[X=0]\le \text {Var}(X)/{\mathbb {E}}[X]^2\le 4q\alpha ^{-1}.\end{equation*}

Lastly, observe that

\begin{align*}{\mathbb{P}}[W\textrm{ contains an edge of }\mathcal{H}]&\ge{\mathbb{P}}[W'\textrm{ contains an edge of }\mathcal{H}\big | |W'|\le \alpha |V|]\\ &\ge{\mathbb{P}}[W'\textrm{ contains an edge of }\mathcal{H}]-{\mathbb{P}}[W'\gt \alpha |V|]. \end{align*}

By the Chernoff bound (see for example [Reference Alon and Spencer1]) we have ${\mathbb{P}}[|W'|\gt \alpha |V|]\le 2e^{-\alpha |V|/4}$ . Note that $W'$ contains an edge of $\mathcal{H}$ precisely when $X\gt 0$ , so the result follows from our analysis above.

Proof. Let $m=\max _{S\in \mathcal{H}} d(S)$ , i.e. this is the maximum multiplicity of any edge in $\mathcal{H}$ . Then for any $S\in \mathcal{H}$ with $d(S)=m$ , we have

\begin{equation*}m=M_{r_1}(S)\le q^{r_1}|\mathcal {H}|\le q^{r_1}\cdot m{ \left(\substack{|V|\\[4pt] r_1}\right)}\le m(eq|V|/r_1)^{r_1},\end{equation*}

proving the result.

Proof. Define $p\;:\!=\;Cq$ and $n\;:\!=\;|V|$ . We can assume $p\le \frac{1}{2}$ , as otherwise the result is trivial (since the set $W$ in the hypothesis of the theorem has size at least $|V|$ ). Let $W_1,\ldots W_{\ell -1}$ be chosen independently and uniformly at random from $\left(\substack{V\\[4pt] pn}\right)$ . Throughout this proof we let $r_{\ell +1}=1$ .

Let $\mathcal{H}_1=\mathcal{H}$ and let $\phi _1 \;:\; \mathcal{H}_1\to \mathcal{H}$ be the identity map. Inductively assume we have defined $\mathcal{H}_i$ and $\phi _i \;:\; \mathcal{H}_i\to \mathcal{H}$ for some $1\le i\lt \ell$ . Let $\mathcal{H'}_{\!\!i}\subseteq \mathcal{H}_i$ be all the edges $S\in \mathcal{H}_i$ such that $(S,W_{i})$ is $r_{i+1}$ -good with respect to $\mathcal{H}_{i}$ . Thus for each $S\in \mathcal{H'}_{\!\!i}$ , there exists an $S'\in \mathcal{H}_i$ such that $S'\subseteq S\cup W_i$ and $|S'\setminus W_i|\le r_{i+1}$ . Choose such an $S'$ for each $S\in \mathcal{H'}_{\!\!i}$ and let $A_S$ be any subset of $S$ of size exactly $r_{i+1}$ that contains $S'\setminus W_i$ (noting that $S'\setminus W_i\subseteq S$ since $S'\subseteq S\cup W_i$ ). Finally, define $\mathcal{H}_{i+1}=\{A_S\;:\; S\in \mathcal{H'}_{\!\!i}\}$ and $\phi _{i+1}\;:\;\mathcal{H}_{i+1}\to \mathcal{H}$ by $\phi _{i+1}(A_S)=\phi _i(S)$ .

Intuitively, $\phi _i(A)$ is meant to correspond to the “original” edge $S\in \mathcal{H}$ which generated $A$ . More precisely, we have the following.

Proof. This claim trivially holds for $i=1$ . Inductively assume the result has been proved for $1,\ldots,i$ . Observe that in the process of generating ${\mathcal{H}}_{i+1}$ , we have implicitly defined a bijection $\psi \;:\;\mathcal{H'}_{\!\!i}\to \mathcal{H}_{i+1}$ through the correspondence $\psi (S)=A_S$ .

By construction of $\phi _{i+1}$ , we have $\phi _{i+1}(A)=\phi _i(\psi ^{-1}(A))$ , so $\phi _{i+1}$ is injective since $\phi _i$ was inductively assumed to be injective and $\psi$ is a bijection. Also by construction we have $A\subseteq \psi ^{-1}(A)$ , and by the inductive hypothesis we have $\psi ^{-1}(A)\subseteq \phi _i(\psi ^{-1}(A))=\phi _{i+1}(A)$ . This completes the proof.

Proof. For a hypergraph $\mathcal{H}'$ , we let $M_j(A;\;\mathcal{H}')$ denote the number of edges of $\mathcal{H}'$ intersecting $A$ in at least $j$ vertices. By Claim 2.8, if $\{A_1,\ldots,A_t\}$ are the set of edges of $\mathcal{H}_i$ which intersect some set $A$ in at least $j$ vertices, then $\{\phi _i(A_1),\ldots,\phi _i(A_t)\}$ is a set of $t$ distinct edges of $\mathcal{H}$ intersecting $A$ in at least $j$ vertices. Thus for all sets $A$ and integers $j$ we have $M_j(A;\;\mathcal{H}_i)\le M_j(A;\;\mathcal{H})$ .

If $A$ is contained in an edge $A'$ of $\mathcal{H}_i$ , then by Claim 2.8 $A$ is contained in the edge $\phi _i(A')$ of $\mathcal{H}$ . Thus $d_{{\mathcal{H}}_i}(A)\gt 0$ implies $d_{{\mathcal{H}}}(A)\gt 0$ . By assumption of $\mathcal{H}$ being $(q;\;r_1,\ldots,r_\ell,1)$ -spread, if $A$ is a set with $r_{i'}\ge |A|\ge r_{i'+1}$ for some integer $i'$ such that $d_{\mathcal{H}_i}(A)\gt 0$ , and if $j$ is an integer satisfying $j\ge r_{i'+1}$ , then our previous observations imply

(7) \begin{equation} M_j(A;\;\mathcal{H}_i)\le M_j(A;\;\mathcal{H}) \le q^j |\mathcal{H}|. \end{equation}

Because each of $W_1,\ldots,W_{i-1}$ were successful, we have

\begin{equation*}|\mathcal {H}_i|\ge \left (1-\frac {1}{2\ell }\right )^i |\mathcal {H}|\ge \left (1-\frac {1}{2\ell }\right )^\ell |\mathcal {H}|\ge \frac {1}{2} |\mathcal {H}|,\end{equation*}

where in this last step we used that $(1-1/(2x))^x$ is an increasing function for $x\ge 1$ . Plugging $|\mathcal{H}|\le 2|\mathcal{H}_i|$ into (7) shows that $\mathcal{H}_i$ is $(2q;\;r_i,\ldots,r_{\ell },1)$ -spread as desired.

Proof. By construction $\mathcal{H}_i$ is $r_i$ -uniform. Conditional on $W_1,\ldots,W_{i-1}$ being successful, Claim 2.9 implies that $\mathcal{H}_{i}$ is in particular $(2q;\;r_{i},r_{i+1})$ -spread. By hypothesis we have $p\le \frac{1}{2}$ and $C/2\ge 4$ , and by Lemma 2.6 applied to $\mathcal{H}$ we have $2r_i\le pn$ since $C\ge 2e$ . Thus we can apply Lemma 2.1 to $\mathcal{H}_i$ (using $C/2$ instead of $C$ ), which shows that the expected number of $r_{i+1}$ -bad pairs $(S,W_i)$ is at most $3(C/4)^{-r_{i+1}/2}|\mathcal{H}_i|$ . By Markov’s inequality, the probability of there being more than $\frac{1}{2\ell } |\mathcal{H}_i|$ total $r_{i+1}$ -bad pairs is at most $6\ell (C/4)^{-r_{i+1}/2}$ , giving the result.

Proof of Theorem 1.4. There exists a large constant $K'$ such that ifFootnote ² $r_\ell \ge K' \log (\ell +1)$ , then the result follows from (5). If this does not hold and if $r_1\gt K'\log (\ell +1)$ , then there exists some $I\ge 2$ such that $r_{I-1}\gt K'\log (\ell +1)\ge r_I$ . If $r_I=K'\log (\ell +1)$ , then the result follows from (6) with $i=I$ provided $C$ is sufficiently large in terms of $K'$ . Otherwise we define a new sequence of integers $r'_1,\ldots,r'_{\ell +1}$ with $r'_i=r_i$ for $i\lt I$ , $r'_I=K'\log (\ell +1)$ , and $r'_i=r_{i-1}$ for $i\gt I$ . It is not hard to see that $\mathcal{H}$ is $(q;\;r_1',\ldots,r'_{\ell +1},1)$ -spread, so the result followsFootnote ³ from (6) with $i=I$ .

It remains to deal with the case $r_1\le K'\log (\ell +1)$ . Because $\ell \le r_1$ , this can only hold if $r_1\le K''$ for some large constant $K''$ . In this case we can apply Lemma 2.4 to give the desired result by choosing $K_0$ sufficiently large in terms of $K''$ .