Return to Question

Let $c>0$, $0<\lambda<1$, and let $N\in \mathbb{N}$ be sufficiently large (depending on $c$). 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: there exists a $k\in \mathbb{N}$ such that for 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$.

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

Let $c>0$, $0<\lambda<1$, and let $N\in \mathbb{N}$ be sufficiently large (depending on $c$). 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: there exists a $k\in \mathbb{N}$ such that for 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])\geq 1-\lambda$.

Let $c>0$, $0<\lambda<1$, and let $N\in \mathbb{N}$ be sufficiently large (depending on $c$). 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: there exists a $k\in \mathbb{N}$ such that for 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$.

Let $c>0$, $0<\lambda<1$, and let $N\in \mathbb{N}$ be sufficiently large (depending on $c$). 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: there exists a $k\in \mathbb{N}$ such that for 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 K[F\subseteq X])\geq 1-\lambda$.

Let $c>0$, $0<\lambda<1$, and let $N\in \mathbb{N}$ be sufficiently large (depending on $c$). 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: there exists a $k\in \mathbb{N}$ such that for 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])\geq 1-\lambda$.