Value $p$ that makes the random hypergraph $H^{(k)}(n,p)$ a good cover?

Question

I need help understanding the following argument.

Definition. A $(k, t)$-covering of $[n]$ is a family of $k$-sets $\mathcal{F} \subseteq\left(\begin{array}{c}{[n]} \\ k\end{array}\right)$ such that every $t$-set $T \in\left(\begin{array}{c}{[n]} \\ t\end{array}\right)$ is contained in at least one set $F \in \mathcal{F}$.

Argument:

• In $H^{(k)}(n,p)$, a fixed $t$-set $T \in\left(\begin{array}{c}{[n]} \\ t\end{array}\right)$ is contained in at most $\left(\begin{array}{c}n-t \\ k-t\end{array}\right)$ sets of size $k$
• $\Rightarrow \mathbb{P}\left(T \text { uncovered by } H^{(k)}(n, p)\right)=(1-p)^{\left(\begin{array}{c} n-t \\ k-t \end{array}\right)} \geq \exp \left(-2 p\left(\begin{array}{c} n-t \\ k-t \end{array}\right)\right)$
• $\Rightarrow \mathbb{E}[\# \text { uncovered } t-\text{sets }] \geq\left(\begin{array}{l}n \\ t\end{array}\right) \exp \left(-2 p\left(\begin{array}{l}n-t \\ k-t\end{array}\right)\right)$
• $\Rightarrow$ to cover all $t$ -sets, need $p=\Omega\left(\frac{\log \left(\begin{array}{l}n \\ c\end{array}\right)}{\left(\begin{array}{l}n-t \\ k-t\end{array}\right)}\right)$

1. The second bullet point is a variation of the inequality $1 - p \leq e^{-p}$. I assume the exponent ${n-t} \choose {k-t}$ has to be of certain size for the statement to be valid? It doesn't seem to play nice with small values like $4,5,6,...$.
2. For the third bullet point, how does having a lower bound for $\mathbb{E}[\# \text { uncovered } t-\text{sets }]$ help? My understanding is that, to have all $t$-sets covered, we'd need $$\mathbb{E}[\# \text { uncovered } t-\text{sets }] = 0.$$ So shouldn't the inequality we're concerned with be $$\mathbb{E}[\# \text { uncovered } t-\text{sets }] \leq X(p)$$ for some quantity $X$ depending on $p$, which we'd force to be 0?

Answer 1

For the first question, the inequality $1-x\leq e^{-2x}$ is valid whenever $x\leq \frac{1}{10}$. When $x$ is a small probability, like in this setting, you can use this inequality without issue. The point is that $1-x\sim e^{-x}$ whenever $x$ is some quantity tending to $0$.

For the second, I believe the argument you are referring to is claiming the "necessariness" of a condition, i.e. it tries to address a question of how large would $p$ have to be, at least, to have a random sample of edges to be a cover. I suspect that the argument is trying to justify that it is not easy to find optimal covers just by the probabilistic method, justifying the need for the trickier "nibble" approach.