# Covering subset with large probability

Let $$c>0$$, $$0<\lambda<1$$, and let $$k\in \mathbb{N}$$ be sufficiently large. Let $$X$$ be a uniformly random subset of $$\{1,\cdots,N\}$$. Denote by $$[N]^x$$ the collection of $$[x]$$-element subset of $$\{1,\cdots,N\}$$.

Prove that: for any sufficiently large $$N\in\mathbb{N}$$ (depending on $$c$$), any function $$f:[N]^{\frac{1}{2}N-c\sqrt{N}}\rightarrow k$$, there exists a subset $$K$$ of $$\{1,\cdots,k\}$$ with $$|K|/k\leq \lambda$$ such that $$\mathbb{P}(\exists F\in f^{-1}(K)[F\subseteq X]\ \big|\ |X|>\frac{1}{2}N-c\sqrt{N})\geq 1-\lambda$$.

• What's the use of the function $f$? – LeechLattice Sep 28 '19 at 4:39
• It's corrected. Sorry for the typo. – Jiayi Liu Sep 29 '19 at 3:20

It is true. Let $$k=\binom{N}{N/2-c\sqrt N}$$ and let $$K$$ be a randomly* selected subset of $$k$$ of size $$k\lambda$$. Then conditionally on $$|X|>N/2-c\sqrt N$$, the difference $$|X|-(N/2-c\sqrt N)$$ is unbounded as $$N\to\infty$$, so $$X$$ has an unbounded number of subsets of size $$N/2-c\sqrt N$$. So since $$f^{-1}(K)$$ contains a bounded-below (by $$\lambda$$) fraction of all such subsets, and a $$\lambda$$ fraction of an unbounded amount is another unbounded amount, almost surely (in the limit as $$N\to\infty$$) $$X$$ contains one of the sets in $$f^{-1}(K)$$.
*We take the probability of $$K$$ being chosen to be proportional to the cardinality of $$f^{-1}(K)$$.
• But $f$ is a given function. In your answer it seems you choose f to be a one-one function. – Jiayi Liu Oct 1 '19 at 2:52
• @JiayiLiu my answer is motivated by the one-one case but the general case is handled by: "We take the probability of $K$ being chosen to be proportional to the cardinality of $f^{-1}(K)$ " – Bjørn Kjos-Hanssen Oct 1 '19 at 3:01
• Right. I need to rethink about the question I'm asking. I actually want $N$ to be very large and $k$ fixed (but yet sufficiently large). – Jiayi Liu Oct 1 '19 at 3:54