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

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

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
5
  • 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, 2019 at 15:26
  • $\begingroup$ No worries I answered the new version now $\endgroup$
    – Bjørn Kjos-Hanssen
    Sep 30, 2019 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, 2019 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, 2019 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, 2019 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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