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
    Commented Sep 28, 2019 at 4:39
  • 1
    $\begingroup$ It's corrected. Sorry for the typo. $\endgroup$
    – Jiayi Liu
    Commented 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
    Commented Sep 30, 2019 at 15:26
  • $\begingroup$ No worries I answered the new version now $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented 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
    Commented 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
    Commented 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
    Commented Oct 1, 2019 at 3:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .