Proof. Indeed, since every minimal covering $T$ of $\mathcal{F}$ has size at least $\tau ({\mathcal{F}})$ we have

\begin{equation*} \mu ^{-|T|} \leqslant \left ( \frac {\lambda }{\mu } \right )^{\tau ({\mathcal {F}})} \lambda ^{-|T|}. \end{equation*}

Summing over all $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{F}})$ gives the desired inequality.

Proof. Each minimal covering $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ contains a minimal covering $T^{\prime} \subset T$ of ${\mathcal{A}}^{\prime}$ . Moreover, by the minimality of $T$ , the set $T\setminus T^{\prime}$ is a minimal covering of the family ${\mathcal{A}}(\bar T^{\prime})$ . So each term $\lambda ^{-|T|}$ on the left-hand side of (10) corresponds to at least one term $\lambda ^{-|T^{\prime}|} \lambda ^{-|T\setminus T^{\prime}|}$ on the right-hand side of (10) (there could be more than one way to choose $T^{\prime}$ ). This proves (10).

Proof. Note that if $|{\mathcal{F}}| \leqslant 1$ then the proposition holds. If $|{\mathcal{F}}| \geqslant 2$ then choose a proper non-empty subfamily ${\mathcal{F}}^{\prime} \subset{\mathcal{F}}$ and apply the second part of Lemma 2.2. The statement now follows by induction.

Proof. By Lemma 2.2 applied to ${\mathcal{F}}^{\prime} \subset{\mathcal{F}}$ we have

\begin{equation*} c_n({\mathcal {F}}) \leqslant \sum _{T \in {\mathcal {T}}_{\leqslant n}({\mathcal {F}}^{\prime})} n^{-|T|} c({\mathcal {F}}(\bar T)) \leqslant \sum _{T \in {\mathcal {T}}_{\leqslant n}({\mathcal {F}}^{\prime})} n^{-|T|} e^{-f(\tau ({\mathcal {F}}(\bar T)))}. \end{equation*}

We have $\tau ({\mathcal{F}}(\bar T)) \geqslant \tau ({\mathcal{F}}) - |T|$ and so by convexity $f(\tau ({\mathcal{F}}(\bar T))) \geqslant f(\tau ({\mathcal{F}})) - |T| f^{\prime}(\tau ({\mathcal{F}}))$ , which leads to

\begin{equation*} c_n({\mathcal {F}}) \leqslant \sum _{T \in {\mathcal {T}}_{\leqslant n}({\mathcal {F}}^{\prime})} n^{-|T|} e^{f^{\prime}(\tau ({\mathcal {F}})) |T| - f(\tau ({\mathcal {F}}))} = c_{\lambda n}({\mathcal {F}}^{\prime}) e^{- f(\tau ({\mathcal {F}}))} \leqslant e^{- f(\tau ({\mathcal {F}}))}, \end{equation*}

completing the proof.

Proof. Let $K^{\prime} = \bigcap{\mathcal{K}}$ and $R = K \setminus K^{\prime}$ and let $u = |K^{\prime} \setminus K|$ . Note that $u \in [0, k]$ since $|F \setminus K| \leqslant k$ for all $F \in{\mathcal{K}}$ . Denote by $\mathcal{A}$ the family of all sets $F \setminus K^{\prime}$ for $F \in{\mathcal{K}}$ . By the definition of $\mathcal{A}$ we have $\tau ({\mathcal{A}}) \geqslant 2$ . Note also that for any $A \in{\mathcal{A}}$ we have $|A \setminus R| \leqslant k-u$ (since $A$ has size at most $k$ and contains the $u$ -element set $K^{\prime}\setminus K$ ).

Note that a minimal covering $T$ of the family $\mathcal{K}$ is either contained in $K^{\prime}$ and $|T| = 1$ or $T \cap K^{\prime} = \emptyset$ . In the latter case $T$ is obviously a minimal covering of $\mathcal{A}$ . Thus, we have

(11) \begin{equation} c_\lambda ({\mathcal{K}}) = \frac{|K^{\prime}|}{\lambda } + c_\lambda ({\mathcal{A}}). \end{equation}

Let ${\mathcal{T}}_1 \subset{\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ be the family of minimal coverings $T$ of $\mathcal{A}$ which are subsets of $R$ . Let ${\mathcal{T}}_2 ={\mathcal{T}}_{\leqslant n}({\mathcal{A}}) \setminus{\mathcal{T}}_1$ . We will estimate weights of ${\mathcal{T}}_1$ and ${\mathcal{T}}_2$ separately.

Note that ${\mathcal{T}}_1 \subset 2^R$ and observe that $T^{\prime} \not \subset T$ for any distinct $T, T^{\prime} \in{\mathcal{T}}_1$ (i.e. ${\mathcal{T}}_1$ is an antichain in $2^R$ ).

Proof. Note that for any $s \geqslant t$ we have $\bigg(\begin{array}{c}|R|\\[-3pt]s\end{array}\bigg) \leqslant\bigg(\begin{array}{c}|R|\\[-3pt]t\end{array}\bigg) \lambda ^{s-t}$ and so by the Lubell–Yamamoto–Meshalkin inequality [Reference Jukna9, p. 112, Theorem 8.6]:

\begin{equation*} \sum _{T \in {\mathcal {T}}} \lambda ^{-|T|} \leqslant \sum _{T \in {\mathcal {T}}} \lambda ^{-t}\bigg(\begin{array}{c}|R|\\[-3pt]t\end{array}\bigg)/ \bigg(\begin{array}{c}|R|\\[-3pt]|T|\end{array}\bigg) = \lambda ^{-t}\bigg(\begin{array}{c}|R|\\[-3pt]t\end{array}\bigg) \sum _{T \in {\mathcal {T}}} \frac {1}{\bigg(\begin{array}{c}|R|\\[-3pt]|T|\end{array}\bigg)} \leqslant \lambda ^{-t} \bigg(\begin{array}{c}|R|\\[-3pt]t\end{array}\bigg). \end{equation*}

By Lemma 2.6 for every $\lambda \geqslant |R|$ the $\lambda$ -weight of ${\mathcal{T}}_1$ is at most

(12) \begin{equation} w_\lambda ({\mathcal{T}}_1) \leqslant \lambda ^{-\tau ({\mathcal{A}})}\bigg(\begin{array}{c}|R|\\[-3pt]\tau ({\mathcal{A}})\end{array}\bigg) \leqslant \frac{(|R|/\lambda )^{\tau ({\mathcal{A}})}}{\tau ({\mathcal{A}})!}. \end{equation}

Now we estimate the weight of ${\mathcal{T}}_2$ . Let ${\mathcal{S}} \subset 2^R$ be the family of all sets $S \subset R$ such that $S$ does not cover $\mathcal{A}$ . Then the weight of ${\mathcal{T}}_2$ is bounded by the following expression:

(13) \begin{equation} w_\lambda ({\mathcal{T}}_2) \leqslant \sum _{S \in{\mathcal{S}}} \lambda ^{-|S|} c_\lambda ({\mathcal{A}}(\bar S) \setminus R). \end{equation}

Indeed, the contribution of an element $T \in{\mathcal{T}}_2$ on the left-hand side is accounted by the term corresponding to $S = T\cap R \in{\mathcal{S}}$ on the right-hand side (since $T\setminus R$ is a minimal covering of the family ${\mathcal{A}}(\bar S)\setminus R$ ). Here the family ${\mathcal{A}}(\bar S) \setminus R$ consists of all sets of the form $A \setminus R$ where $A \in{\mathcal{A}}$ does not intersect $S$ . Every element in ${\mathcal{A}}(\bar S)\setminus R$ has cardinality at most $k-u$ and so by Observation 2.1 and Corollary 2.3 applied to ${\mathcal{A}}(\bar S)\setminus R$ for every $\lambda \geqslant k-u$ we have

(14) \begin{equation} c_\lambda ({\mathcal{A}}(\bar S)\setminus R) \leqslant \left (\frac{k-u}{\lambda }\right )^{\tau ({\mathcal{A}}(\bar S)\setminus R)} c_{k-u}({\mathcal{A}}(\bar S)\setminus R) \leqslant \left (\frac{k-u}{\lambda }\right )^{\tau ({\mathcal{A}}(\bar S)\setminus R)}. \end{equation}

Let $S \in{\mathcal{S}}$ . Note that we have the following lower bound on $\tau ({\mathcal{A}}(\bar S)\setminus R)$ :

\begin{equation*} \tau ({\mathcal {A}}(\bar S)\setminus R) \geqslant \max \{ 1, \tau ({\mathcal {A}})-|S|\}. \end{equation*}

Using this lower bound, (13) and (14) we obtain an upper bound on the weight of ${\mathcal{T}}_2$ for $\lambda \geqslant k$ :

(15) \begin{align} w_\lambda ({\mathcal{T}}_2) \leqslant \sum _{s = 0}^{\tau ({\mathcal{A}})-1} \lambda ^{-s}\bigg(\begin{array}{c}|R|\\[-3pt]s\end{array}\bigg) \left (\frac{k-u}{\lambda }\right )^{\tau ({\mathcal{A}}) - s} + \sum _{s = \tau ({\mathcal{A}})}^{|R|} \lambda ^{-s}\bigg(\begin{array}{c}|R|\\[-3pt]s\end{array}\bigg)\left (\frac{k-u}{\lambda }\right ). \end{align}

Now we combine all obtained inequalities to prove Lemma 1.6. Suppose that $|K^{\prime}| = |\bigcap{\mathcal{K}}| \lt n-5k$ , we need to show that $c_{n-k}({\mathcal{K}}) \leqslant 1$ holds. We have

\begin{equation*} |K\cup K^{\prime}| = |K^{\prime}| + |K\setminus K^{\prime}|= |K| + |K^{\prime}\setminus K|, \end{equation*}

so that $|K^{\prime}| = n-k + u - r$ holds. In particular, by the assumption $|K^{\prime}|\lt n-5k$ we have $n-k \geqslant r \gt u+4k$ .

Denote $t = \tau ({\mathcal{A}}) \geqslant 2$ , $r = |R|$ , $\rho = \frac{r}{n-k}$ and $\delta = \frac{k-u}{n-k}$ . We can use (12) and (15) with $\lambda = n-k$ and get:

\begin{align*} w_{n-k}({\mathcal{T}}_1) &\leqslant \frac{\rho ^{t}}{t!},\\ w_{n-k}({\mathcal{T}}_2) &\leqslant \sum _{s=0}^{t-1} \frac{\rho ^s \delta ^{t-s}}{s!} + \sum _{s=t}^{r} \frac{\rho ^s \delta }{s!}. \end{align*}

By (11), formula $|K^{\prime}| = n-k+u-r$ and decomposition ${\mathcal{T}}_{\leqslant n}({\mathcal{K}}) ={\mathcal{T}}_1\cup{\mathcal{T}}_2$ :

\begin{align*} c_{n-k}({\mathcal{K}}) &\leqslant \frac{n-k+u-r}{n-k} + w_{n-k}({\mathcal{T}}_1) + w_{n-k}({\mathcal{T}}_2) \le \\ & \leqslant \frac{n-k+u-r}{n-k} + \frac{\rho ^t}{t!} + \sum _{s=0}^{t-1} \frac{\rho ^s \delta ^{t-s}}{s!} + \sum _{s=t}^{r} \frac{\rho ^s \delta }{s!}. \end{align*}

Both $\rho$ and $\delta$ are between 0 and 1 so it is easy to see that the second line is the largest when $t=2$ , i.e.

\begin{equation*} c_{n-k}({\mathcal {K}}) \leqslant \frac {n-k+u-r}{n-k} + \frac {\rho ^2}{2} + \delta ^2 + \frac {\delta \rho }{2} + \sum _{s=2}^{r} \frac {\rho ^s \delta }{s!} \leqslant \frac {n-k+u-r}{n-k} + \frac {\rho }{2} + 2\delta, \end{equation*}

where in the last transition we used $0\leqslant \delta, \rho \leqslant 1$ to group the last 3 terms together and replace $\rho ^2$ by $\rho$ . Recalling $\rho = \frac{r}{n-k}$ and $\delta = \frac{k-u}{n-k}$ we get

\begin{equation*} c_{n-k}({\mathcal {K}}) \leqslant \frac {n+ k - u - r/2}{n-k} \leqslant \frac {n+k - r/2}{n-k} \leqslant 1, \end{equation*}

since $r \geqslant 4k$ and $u \geqslant 0$ .

Proof of Lemma 1.8. Denote by $X$ the ground set of $\mathcal{A}$ . Put $C = 2048$ , $R=\frac{n}{2}$ and $m = \lceil \log _2{n}+10\rceil$ . Let $\delta = \frac{C}{n}$ and let ${\bf U} \subset X$ be a subset of $X$ of density $(1-\delta )^m$ . Let ${\bf T} \in{\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ be a random set with distribution

(16) \begin{equation} {\mathbb{P}}({\bf T} = T) = \frac{n^{-|T|}}{c_n({\mathcal{A}})}, \end{equation}

where $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ and such that $\bf T$ is independent from $\bf U$ .

Let us suppose that the random set $\bf T$ is not $R$ -spread. By definition, this means that there is a non-empty set $S \subset X$ such that

\begin{equation*} {\mathbb {P}}(S \subset {\bf T}) \geqslant R^{-|S|} = \left ( \frac {2}{n} \right )^{|S|}. \end{equation*}

Let ${\mathcal{A}}^{\prime} ={\mathcal{A}}(\bar S)$ be the family of $A \in{\mathcal{A}}$ such that $A \cap S = \emptyset$ . Note that $\tau ({\mathcal{A}}^{\prime})\geqslant \tau ({\mathcal{A}}) - |S|$ . Note that if a covering $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ satisfies $S \subset T$ then $T\setminus S$ is a minimal covering of the family ${\mathcal{A}}^{\prime}$ . Thus,

\begin{equation*} \sum _{T \in {\mathcal {T}}_{\leqslant n}({\mathcal {A}})\,:\, S \subset T} n^{-|T|} = n^{-|S|} \sum _{T \in {\mathcal {T}}_{\leqslant n}({\mathcal {A}})\,:\, \,S \subset T} n^{-|T \setminus S|} \leqslant n^{-|S|} c_n({\mathcal {A}}^{\prime}). \end{equation*}

By (16), the left-hand side of this inequality equals to $c_n({\mathcal{A}}){\mathbb{P}}(S \subset{\bf T})$ . We conclude

\begin{align*} c_n({\mathcal{A}}^{\prime}) n^{-|S|} \geqslant c_n({\mathcal{A}}){\mathbb{P}}(S \subset{\bf T}) \geqslant c_n({\mathcal{A}}) 2^{|S|} n^{-|S|},\\ c_n({\mathcal{A}}^{\prime}) \geqslant c_n({\mathcal{A}}) 2^{|S|} \geqslant c_n({\mathcal{A}}) 2^{\tau ({\mathcal{A}}) - \tau ({\mathcal{A}}^{\prime})}. \end{align*}

This implies the second alternative of Lemma 2.7. So we may assume that $\bf T$ is $R$ -spread.

By Corollary 2.9 (applied to ${\bf W} = X\setminus{\bf U}$ ), we have the following estimate on the probability that there is a covering $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ which does not intersect $\bf U$ :

\begin{equation*} {\mathbb {P}}(\exists T \in {\mathcal {T}}_{\leqslant n}({\mathcal {A}})\,:\, T \cap {\bf U} = \emptyset ) \geqslant 1 - \left ( \frac {5}{\log R\delta } \right )^m {\mathbb {E}} |{\bf T}| \geqslant 1 - 2^{-m} n \gt 0.9, \end{equation*}

here we used the fact that $R\delta = 1024$ , $m \gt \log _2 n + 9$ and that every element of ${\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ has size at most $n$ .Footnote ¹ We conclude that if we take a random set $\bf U$ of density $(1-\delta )^m$ then with probability at least $0.9$ there is a $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ which does not intersect $\bf U$ . Let us now show that with probability at least $0.5$ the set $\bf U$ contains an element of $\mathcal{B}$ , provided that $\mathcal{B}$ is large enough. Since by definition of ${\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ every $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ intersects every set from $\mathcal{B}$ , this will lead to a contradiction if $|{\mathcal{B}}|$ is large enough.

Note that an element $A$ of $\mathcal{B}$ is contained in $\bf U$ with probability

(17) \begin{equation} (1-\delta )^{m n} = e^{n \log _2 n (-\frac{C}{n} + O(n^{-2}))} = n^{-C/\ln 2 + o(1)}, \end{equation}

provided that $n$ is sufficiently large. Denote $\rho = (1-\delta )^{n m}$ . For $A \in{\mathcal{B}}$ denote by $\xi _A$ the indicator of the event that $A \subset \bf U$ and by $\xi$ the sum of $\xi _A$ over $\mathcal{B}$ . Hence, we have ${\mathbb{E}} \xi _A = \rho$ for every $A \in{\mathcal{B}}$ and

\begin{equation*} {\mathbb {E}} \xi = |{\mathcal {B}}| \rho . \end{equation*}

By Chebyshev’s inequality (see, for instance, [Reference Jukna9, p. 303, (21.2)]), it is enough to show that $\textrm{Var}\, \xi \lt ({\mathbb{E}} \xi )^2/ 2$ , where $\textrm{Var}\, \xi$ denotes the variance of the random variable $\xi$ . Let us estimate the correlations $({\mathbb{E}} \xi _A \xi _{A^{\prime}} - \rho ^2)$ for $A \neq A^{\prime}$ . It is clear that

\begin{equation*} {\mathbb {E}} \xi _A \xi _{A^{\prime}} = (1-\delta )^{m|A\cup A^{\prime}|} \leqslant (1-\delta )^{2 m n - m\frac {n}{10^4 \ln n} } = \rho ^{2 - \frac {1}{10^4 \ln n}}. \end{equation*}

By (17), we have

\begin{equation*} \rho ^{-\frac {1}{10^4 \ln n}} = \left (n^{\frac {C + o(1)}{\ln 2} }\right )^{- \frac {1}{10^4 \ln n}} = 2^{\frac {C}{10^4} + o(1)} \lt 1.4 \end{equation*}

provided that $n$ is large enough. We conclude that the variance of $\xi$ is at most

\begin{equation*} 0.4 \rho ^2 |{\mathcal {B}}|^2 + \rho |{\mathcal {B}}| \end{equation*}

which is less than $({\mathbb{E}}\xi )^2/2$ if $|{\mathcal{B}}| \gt 10/\rho$ . Therefore, provided, that $|{\mathcal{B}}| \geqslant n^{3000} \gt 10/\rho$ , with probability at least $0.5$ the random set $\bf U$ contains an element of $\mathcal{B}$ and with probability at least $0.9$ it does not intersect an element of ${\mathcal{T}}_{\leqslant n}({\mathcal{A}})$ . But these two events cannot happen simultaneously. This is a contradiction and Lemma 2.7 is proved.

Proof. Put $t = \tau ({\mathcal{F}}) - 1$ and let $x_1, \ldots, x_t \in X$ be a sequence of random independent elements of $X$ sampled according to distribution $f$ . Then the left-hand side of (18) is the expectation of the number of sets $F \in{\mathcal{F}}$ which are not covered by the set $\{x_1, \ldots, x_t\}$ . Since $\tau ({\mathcal{F}}) \gt t$ , this number is always positive and (18) follows.

Proof. Apply Observation 2.11 to $f(x) = \sum _{i = 1}^l \frac{f_i(x)}{f_i(X)}$ .

Proof. For $i = 1, \ldots, l$ let

(20) \begin{equation} f_i(x) = \sum _{j = 1}^{i-1}\bigg(\begin{array}{c}i\\[-3pt]j\end{array}\bigg) d_{\mathcal{F}}^j(x). \end{equation}

Apply Corollary 2.12 to functions $f_1, \ldots, f_l$ and the family ${\mathcal{A}} \setminus{\mathcal{F}}$ . Then there exists $A \in{\mathcal{A}}\setminus{\mathcal{F}}$ such that for every $i = 1, \ldots, l$ we have

(21) \begin{equation} f_i(A) \leqslant f_i(X) l \left(1 - |{\mathcal{A}} \setminus{\mathcal{F}}|^{-1/\tau ({\mathcal{A}}\setminus{\mathcal{F}})-1}\right) \leqslant f_i(X) l\left(1 - |{\mathcal{A}}|^{-1/t}\right) \leqslant f_i(X) \frac{l \log |{\mathcal{A}}|}{t}, \end{equation}

by the standard inequality $1-e^{-x} \leqslant x$ . But note that for ${\mathcal{F}}^{\prime} ={\mathcal{F}} \cup \{A\}$ by (20) we have

(22) \begin{equation} d_{{\mathcal{F}}^{\prime}}^i - d_{{\mathcal{F}}}^i = \sum _{x \in X} d_{{\mathcal{F}}^{\prime}}^i(x) - d_{\mathcal{F}}^i(x) = \sum _{x \in A} (d_{{\mathcal{F}}}(x) + 1 )^i - d_{\mathcal{F}}^i(x) = f_i(A) + n. \end{equation}

Note that $d_{\mathcal{F}}^i$ is monotone increasing in $i$ and so

\begin{equation*} f_i(X) = \sum _{j = 1}^{i-1} \bigg(\begin{array}{c}i\\[-3pt]j\end{array}\bigg) d_{\mathcal {F}}^j \leqslant 2^i d_{\mathcal {F}}^{i-1}. \end{equation*}

The bound (19) now follows from (21) and (22).

Proof of Lemma 2.10. Let $X$ denote the ground set of $\mathcal{A}$ and put $\gamma = 2l m/t$ .

Let ${\mathcal{F}} \subset{\mathcal{A}}$ be a maximal subfamily in $\mathcal{A}$ such that for every $i = 1, \ldots, l$ we have

(23) \begin{equation} d_{\mathcal{F}}^i \leqslant 2^{i^2}\gamma ^{i-1} n |{\mathcal{F}}|^i + 2^{i^2}n|{\mathcal{F}}|. \end{equation}

Note that if $|{\mathcal{F}}| = 1$ then (23) clearly holds and so $\mathcal{F}$ is well-defined. To prove Lemma 1.9 it is clearly enough to show that any such $\mathcal{F}$ satisfies $\tau ({\mathcal{A}} \setminus{\mathcal{F}}) \leqslant t/ 2$ . Indeed, in this case we have $\tau ({\mathcal{F}}) \geqslant t/2$ and, in particular, $|{\mathcal{F}}| \geqslant t/2$ . Then $\gamma |{\mathcal{F}}| \geqslant m \geqslant 1$ and, therefore, the first term in (23) dominates the second one.

Now we show that it is impossible to have $\tau ({\mathcal{A}} \setminus{\mathcal{F}}) \geqslant t/2 + 1$ . Indeed, in this case we can apply Lemma 2.14 to the pair ${\mathcal{F}} \subset{\mathcal{A}}$ and obtain a family ${\mathcal{F}}^{\prime} ={\mathcal{F}} \cup \{ A \}$ such that (19) holds for $i = 1, \ldots, l$ and with $t/2$ instead of $t$ . Note that $l \log |{\mathcal{A}}|/(t/2) \leqslant \gamma$ . On the other hand, the maximality of $\mathcal{F}$ implies that there is some $i \in \{2, \ldots, l\}$ ( $i \neq 1$ because otherwise (23) holds automatically) such that

\begin{equation*} d^i_{{\mathcal {F}}^{\prime}} \gt 2^{i^2} \gamma ^{i-1}n(|{\mathcal {F}}|+1)^i + 2^{i^2}n(|{\mathcal {F}}|+1) \geqslant 2^{i^2}\gamma ^{i-1} n|{\mathcal {F}}|^i + 2^{i^2}\gamma ^{i-1}n|{\mathcal {F}}|^{i-1} + 2^{i^2}n|{\mathcal {F}}| + 2^{i^2}n. \end{equation*}

On the other hand, from (19) we get

\begin{align*} d^i_{{\mathcal{F}}^{\prime}} \leqslant d_{\mathcal{F}}^i + \gamma 2^i d_{\mathcal{F}}^{i-1} + n \leqslant (2^{i^2}\gamma ^{i-1} n|{\mathcal{F}}|^i + 2^{i^2}n|{\mathcal{F}}|) + \gamma 2^i( 2^{(i-1)^2}\gamma ^{i-2} n|{\mathcal{F}}|^{i-1} + 2^{(i-1)^2} n |{\mathcal{F}}|) + n. \end{align*}

Combining these two inequalities and cancelling same terms we get

\begin{equation*} (2^{i^2} - 2^{i^2 - i + 1})\gamma ^{i-1}n|{\mathcal {F}}|^{i-1} - \gamma 2^{i^2 - i + 1} n|{\mathcal {F}}| + (2^{i^2} - 1)n \lt 0. \end{equation*}

So if we let $x = \gamma |{\mathcal{F}}|$ then, after dividing by $2^{i^2}n$ , we obtain

(24) \begin{equation} 2^{-i+1}x \gt (1 - 2^{-i+1})x^{i-1}+\frac{1}{2}. \end{equation}

Recall that $i \geqslant 2$ . So if $x \geqslant 1$ then the first term on the right-hand side (24) is greater than $2^{-i+1}x$ . If $x \lt 1$ then the second term is greater than $2^{-i+1}x$ . In both cases, we arrive at a contradiction. Lemma 1.9 is proved.

Proof of Lemma 2.15. In order to prove this lemma, we need to recall the classical Erős–Lovász encoding procedure which they used to obtain the bound $|{\mathcal{F}}| \leqslant n^n$ for the size of an $n$ -uniform maximal intersecting family. Denote ${\mathcal{B}} = \{F_1, \ldots, F_r\}$ .

Procedure.

Let $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{B}})$ and $S \subset T$ be a proper subset. From the pair $(T, S)$ we construct a new pair $(T, S^{\prime})$ as follows. Let $i \in [r]$ be the minimum number so that $F_i \cap S = \emptyset$ . Pick arbitrary $x \in F_i \cap T$ and let $S^{\prime} = S \cup \{x\}$ .

So if we apply this procedure to any $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{B}})$ and $S = \emptyset$ , then we will obtain a sequence of sets of the form:

(26) \begin{equation} \emptyset = S_0 \subset S_1 \subset \ldots \subset S_{|T|} = T. \end{equation}

Note that the sequence $(S_0, \ldots, S_{|T|})$ is not determined uniquely by $T$ since there may be an ambiguity in the choice of $x \in F_i \cap T$ during the procedure. Let ${\mathcal{T}}_1 \subset{\mathcal{T}}_{\leqslant n}({\mathcal{B}})$ the the family of sets $T$ such that the sequence $(S_0, \ldots, S_{|T|})$ is determined uniquely by $T$ . In other words, at each step we have an equality $|F_i \cap T| = 1$ . Let ${\mathcal{T}}_2 ={\mathcal{T}}_{\leqslant n}({\mathcal{B}}) \setminus{\mathcal{T}}_1$ .

Now we denote by $\mathcal J$ the set of all sequences $(S_0, S_1, \ldots, S_k)$ which may occur during the procedure starting from some $T \in{\mathcal{T}}_{\leqslant n}({\mathcal{B}})$ and $S = \emptyset$ . Let ${\mathcal{J}} ={\mathcal{J}}_1 \cup{\mathcal{J}}_2$ be the decomposition arising from the decomposition ${\mathcal{T}}_{\leqslant n}({\mathcal{B}}) ={\mathcal{T}}_1 \cup{\mathcal{T}}_2$ . The weight $w(\bar S)$ of a sequence $\bar S = (S_0, \ldots, S_k)$ is defined to be $n^{-|S_k|}$ . The standard Erdős–Lovász [Reference Erdős and Lovász4] argument shows that the weight $w({\mathcal{J}})$ of the family $\mathcal{J}$ is always at most $1$ . We omit the proof since it is very similar in spirit to the proof of Lemma 2.2 and Corollary 2.3.

On the other hand, we can bound weights of families ${\mathcal{T}}_1$ and ${\mathcal{T}}_2$ in terms of weights of ${\mathcal{J}}_1$ and ${\mathcal{J}}_2$ as follows:

(27) \begin{equation} c_n({\mathcal{B}}) = w_n({\mathcal{T}}_{\leqslant n}({\mathcal{B}})) = w_n({\mathcal{T}}_1) + w_n({\mathcal{T}}_2) \leqslant w({\mathcal{J}}_1) + \frac{1}{2} w({\mathcal{J}}_2) \leqslant \frac{w({\mathcal{J}}_1) + 1}{2}. \end{equation}

So it is enough to obtain a good upper bound on $w({\mathcal{J}}_1)$ . For $T \in{\mathcal{T}}_1$ we denote by $S_i(T)$ the $i$ -th element of the sequence of $T$ in the process (which is defined uniquely for elements of ${\mathcal{T}}_1$ ). We denote by $A_i(T) \in{\mathcal{B}}$ the element of $\mathcal{B}$ which was picked at step $i-1$ of the process. In particular, $S_{i-1}(T) \cap A_i(T) = \emptyset$ and $|S_{i}(T) \cap A_i(T)| = 1$ . We denote by $x_i(T)$ the unique element in the intersection $S_{i}(T) \cap A_i(T)$ .

The uniqueness of the sequence $\bar S(T)$ implies that for any $j \lt i$ we have

\begin{equation*} x_i(T) \not \in A_j(T). \end{equation*}

Indeed, otherwise at step $j$ we may have picked the element $x_i(T)$ instead of $x_j(T)$ and thus form a different sequence $(S^{\prime}_0, \ldots, S^{\prime}_{|T|})$ which corresponds to the covering $T$ . We conclude that

\begin{equation*} x_i(T) \in A_i(T) \setminus \bigcup _{j \lt i} A_j(T) \,=\!:\, Y_i(T). \end{equation*}

Since the family $\mathcal{B}$ is intersecting and does not contain $l$ -wise intersections we have the following upper bound on the size of $Y_i(T)$ :

\begin{equation*} |Y_i(T)| \leqslant n - \frac {i-1}{l}. \end{equation*}

For $q \geqslant 0$ and a given sequence $\bar S = (S_0 \subset S_1 \subset \ldots \subset S_q)$ we denote by ${\mathcal{J}}_1(\bar S)$ the family of sequences from ${\mathcal{J}}_1$ which start from $\bar S$ .

Observation 2.16. For any sequence $\bar S = (S_0, S_1, \ldots, S_{i-1})$ which is a part of the sequence of some $T\in{\mathcal{T}}_1$ such that $|T| \gt i$ we have

\begin{equation*} w({\mathcal {J}}_1(\bar S)) \leqslant \frac {1}{n} \sum _{x \in Y_i(T)} w({\mathcal {J}}_1(\bar S, S_{i-1} \cup \{x\})). \end{equation*}

For $q \geqslant 0$ let

(28) \begin{equation} f(q) = \max _{\bar S = (S_0, S_1, \ldots, S_q)} w({\mathcal{J}}_1(\bar S)). \end{equation}

The following proposition will finish the proof. Note that $\tau ({\mathcal{B}}) \geqslant r/l$ because any element $x \in X$ covers at most $l$ sets from $\mathcal{B}$ .

Proposition 2.17. For any $q \in [0, r/l]$ we have

\begin{equation*} f(q) \leqslant \prod _{i = q}^{[r/l]-1} \left (1 - \frac {i-1}{n l}\right ). \end{equation*}

Proof. The proof is by induction. The base case $q = [r/l]$ states that $f([r/l]) \leqslant 1$ which we already know by the Erdős–Lovász argument.

For the induction step, let $T \in{\mathcal{T}}_1$ be a covering on which the maximum in (28) is attained. Now apply Observation 2.16 and the induction hypothesis to conclude that

\begin{equation*} f(q) \leqslant \frac {1}{n} |Y_i(T)| f(q+1) \leqslant \left (1 - \frac {i-1}{nl} \right )f(q+1), \end{equation*}

where $T$ corresponds to a maximizer of the supremum on the left-hand side.

Substituting $q = 0$ in Proposition 2.17 we get

\begin{equation*} w({\mathcal {J}}_1) = f(0) \leqslant \prod _{i = 1}^{[r/l]-1} \left(1 - \frac {i-1}{n l}\right) \leqslant \left ( 1 - \frac {r}{2n l^2} \right )^{r/2l} \leqslant e^{ - \frac {r^2}{4l^3 n}}. \end{equation*}

Let $y = \frac{r^2}{l^3 n}$ . By assumption we have $y \leqslant 1$ and so we have the following elementary inequality: $e^{-y/4}+1 \leqslant 2 e^{-y/10}$ . By (27), the desired inequality (25) follows.

Proof. Note that any minimal covering of $\mathcal{B}$ has size at most $|{\mathcal{B}}| = r$ . So for any $\lambda \leqslant 1$ we have

\begin{equation*} c_{\lambda n}({\mathcal {B}}) \leqslant \lambda ^{-r} c_n({\mathcal {B}}). \end{equation*}

By Lemma 2.15, if we let $\lambda = e^{- \frac{r}{10 l^3 n}}$ then $c_{\lambda n}({\mathcal{B}}) \leqslant 1$ . Now if $k \leqslant \frac{r}{20 l^3}$ then

\begin{equation*} \frac {n-k}{n} \geqslant 1 - \frac {r}{20 l^3 n} \geqslant e^{-\frac {r}{10 l^3 n}}, \end{equation*}

which implies that $c_{n-k}({\mathcal{B}}) \leqslant 1$ .