2
$\begingroup$

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$.

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

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)$.

$\endgroup$
  • 1
    $\begingroup$ Ops. There is a mistake in the statement~ The probability is conditional on: the size of X is larger than N/2-c\sqrt{N}. The question is related to an open question in your paper whether there is a set covers REC but not RE. $\endgroup$ – Jiayi Liu Sep 30 '19 at 15:26
  • $\begingroup$ No worries I answered the new version now $\endgroup$ – Bjørn Kjos-Hanssen Sep 30 '19 at 18:48
  • $\begingroup$ But $f$ is a given function. In your answer it seems you choose f to be a one-one function. $\endgroup$ – Jiayi Liu Oct 1 '19 at 2:52
  • $\begingroup$ @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)$ " $\endgroup$ – Bjørn Kjos-Hanssen Oct 1 '19 at 3:01
  • 1
    $\begingroup$ 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). $\endgroup$ – Jiayi Liu Oct 1 '19 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.