Skip to main content
MathOverflow

Return to Answer

fix typo
Source Link
blt
blt
  • 1.2k
  • 1
  • 10
  • 13

It does turn out to be possible to take $R$ as roughly $\log N/(-\log k\epsilon)$. More precisely, if you choose $R$ such that $N\epsilon^R {k \choose R}<1$, then you can always find $\mathcal{A}\subset \mathcal{S}$ of size $R$ satisfying the requirements in the question. The conclusion follows quickly from the following claim, which we establish by induction on $m$:

Claim: We can find sets $A_1,\dots, A_m \in \mathcal{S}$ such that $$\sum_{J\subset\{1,...,m\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$

Note that in this claim we adopt the ad-hoc notational convention that if $J$ is empty, $\bigcap_{j\in J} A_j$ should be taken to mean $[N]$. We also adopt the common convention that $a \choose b$ is 0 for $b<0$ or $b>a$.

Proof of claim: by induction on $m$. The case $m=0$ is trivially true. For $m>0$, we may by inductive hypothesis suppose that we have chosen $A_1,\dots, A_m \in \mathcal{S}$$A_1,\dots, A_{m-1} \in \mathcal{S}$ so that $$\sum_{J\subset\{1,...,m-1\}} {k-m+1 \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$

Now imagine choosing $A_m$ uniformly at random from $\mathcal{S}$. We can evaluate the expected value of the LHS of the displayed equation in the claim as

\begin{align*} \mathbb{E}\sum_{J\subset\{1,...,m\}} &{k-m \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right) \\ =& \mathbb{E}\sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \left(\# \bigcap_{j\in J} A_j\right) \\ &\quad+ \mathbb{E}\sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J-1} \epsilon^{R-\#J-1} \left(\# \left(A_m\cap \bigcap_{j\in J} A_j\right)\right)\\ \leq& \sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \left(\# \bigcap_{j\in J} A_j\right) \\ &\quad+ \sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J-1} \epsilon^{R-\#J-1} \times \epsilon\times \left(\# \bigcap_{j\in J} A_j\right) \\ =& \sum_{J\subset\{1,...,m-1\}} \left[{k-m\choose R - \#J}+ {k-m\choose R - \#J-1}\right] \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\\ =& \sum_{J\subset\{1,...,m-1\}} {k-m+1 \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right) \end{align*} which is $\leq N\epsilon^R {k \choose R}$ by the inequality that we got from the fact that $A_1,\dots,A_m$$A_1,\dots,A_{m-1}$ were chosen via the inductive hypothesis. Since the expected value of the LHS of the displayed equation in the claim when we choose $A_m$ at random is at most $N\epsilon^R {k \choose R}$, we must be able to choose some specific $A_m$ for which the LHS satisfies the required inequality. QED.

Once the claim is proved, the $m=k$ case tells us that we can choose $A_1,\dots,A_k\in \mathcal{S}$ with $$\sum_{J\subset\{1,...,k\}, \#J=R} \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$ and so if we did chose $R$ such that $N\epsilon^R {k \choose R}<1$, this implies that $\sum_{J\subset\{1,...,k\}, \#J=R} \left(\# \bigcap_{j\in J} A_j\right) < 1$. But then since each summand in the LHS is a non-negative integer, it follows that they are in fact all zero, so for all $J\subset\{1,\dots,k\}$ with $\#J=R$, we have that $\bigcap_{j\in J} A_j=\emptyset$. This is equivalent to the statement that for each $i\in [N]$, $\#\{X\in\{A_1,\dots,A_k\}|i\in X\} \leq R$. So we are done, taking $\mathcal{A}=\{A_1,\dots,A_k\}$.

It does turn out to be possible to take $R$ as roughly $\log N/(-\log k\epsilon)$. More precisely, if you choose $R$ such that $N\epsilon^R {k \choose R}<1$, then you can always find $\mathcal{A}\subset \mathcal{S}$ of size $R$ satisfying the requirements in the question. The conclusion follows quickly from the following claim, which we establish by induction on $m$:

Claim: We can find sets $A_1,\dots, A_m \in \mathcal{S}$ such that $$\sum_{J\subset\{1,...,m\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$

Note that in this claim we adopt the ad-hoc notational convention that if $J$ is empty, $\bigcap_{j\in J} A_j$ should be taken to mean $[N]$. We also adopt the common convention that $a \choose b$ is 0 for $b<0$ or $b>a$.

Proof of claim: by induction on $m$. The case $m=0$ is trivially true. For $m>0$, we may by inductive hypothesis suppose that we have chosen $A_1,\dots, A_m \in \mathcal{S}$ so that $$\sum_{J\subset\{1,...,m-1\}} {k-m+1 \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$

Now imagine choosing $A_m$ uniformly at random from $\mathcal{S}$. We can evaluate the expected value of the LHS of the displayed equation in the claim as

\begin{align*} \mathbb{E}\sum_{J\subset\{1,...,m\}} &{k-m \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right) \\ =& \mathbb{E}\sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \left(\# \bigcap_{j\in J} A_j\right) \\ &\quad+ \mathbb{E}\sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J-1} \epsilon^{R-\#J-1} \left(\# \left(A_m\cap \bigcap_{j\in J} A_j\right)\right)\\ \leq& \sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \left(\# \bigcap_{j\in J} A_j\right) \\ &\quad+ \sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J-1} \epsilon^{R-\#J-1} \times \epsilon\times \left(\# \bigcap_{j\in J} A_j\right) \\ =& \sum_{J\subset\{1,...,m-1\}} \left[{k-m\choose R - \#J}+ {k-m\choose R - \#J-1}\right] \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\\ =& \sum_{J\subset\{1,...,m-1\}} {k-m+1 \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right) \end{align*} which is $\leq N\epsilon^R {k \choose R}$ by the inequality that we got from the fact that $A_1,\dots,A_m$ were chosen via the inductive hypothesis. Since the expected value of the LHS of the displayed equation in the claim when we choose $A_m$ at random is at most $N\epsilon^R {k \choose R}$, we must be able to choose some specific $A_m$ for which the LHS satisfies the required inequality. QED.

Once the claim is proved, the $m=k$ case tells us that we can choose $A_1,\dots,A_k\in \mathcal{S}$ with $$\sum_{J\subset\{1,...,k\}, \#J=R} \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$ and so if we did chose $R$ such that $N\epsilon^R {k \choose R}<1$, this implies that $\sum_{J\subset\{1,...,k\}, \#J=R} \left(\# \bigcap_{j\in J} A_j\right) < 1$. But then since each summand in the LHS is a non-negative integer, it follows that they are in fact all zero, so for all $J\subset\{1,\dots,k\}$ with $\#J=R$, we have that $\bigcap_{j\in J} A_j=\emptyset$. This is equivalent to the statement that for each $i\in [N]$, $\#\{X\in\{A_1,\dots,A_k\}|i\in X\} \leq R$. So we are done, taking $\mathcal{A}=\{A_1,\dots,A_k\}$.

It does turn out to be possible to take $R$ as roughly $\log N/(-\log k\epsilon)$. More precisely, if you choose $R$ such that $N\epsilon^R {k \choose R}<1$, then you can always find $\mathcal{A}\subset \mathcal{S}$ of size $R$ satisfying the requirements in the question. The conclusion follows quickly from the following claim, which we establish by induction on $m$:

Claim: We can find sets $A_1,\dots, A_m \in \mathcal{S}$ such that $$\sum_{J\subset\{1,...,m\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$

Note that in this claim we adopt the ad-hoc notational convention that if $J$ is empty, $\bigcap_{j\in J} A_j$ should be taken to mean $[N]$. We also adopt the common convention that $a \choose b$ is 0 for $b<0$ or $b>a$.

Proof of claim: by induction on $m$. The case $m=0$ is trivially true. For $m>0$, we may by inductive hypothesis suppose that we have chosen $A_1,\dots, A_{m-1} \in \mathcal{S}$ so that $$\sum_{J\subset\{1,...,m-1\}} {k-m+1 \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$

Now imagine choosing $A_m$ uniformly at random from $\mathcal{S}$. We can evaluate the expected value of the LHS of the displayed equation in the claim as

\begin{align*} \mathbb{E}\sum_{J\subset\{1,...,m\}} &{k-m \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right) \\ =& \mathbb{E}\sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \left(\# \bigcap_{j\in J} A_j\right) \\ &\quad+ \mathbb{E}\sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J-1} \epsilon^{R-\#J-1} \left(\# \left(A_m\cap \bigcap_{j\in J} A_j\right)\right)\\ \leq& \sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \left(\# \bigcap_{j\in J} A_j\right) \\ &\quad+ \sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J-1} \epsilon^{R-\#J-1} \times \epsilon\times \left(\# \bigcap_{j\in J} A_j\right) \\ =& \sum_{J\subset\{1,...,m-1\}} \left[{k-m\choose R - \#J}+ {k-m\choose R - \#J-1}\right] \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\\ =& \sum_{J\subset\{1,...,m-1\}} {k-m+1 \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right) \end{align*} which is $\leq N\epsilon^R {k \choose R}$ by the inequality that we got from the fact that $A_1,\dots,A_{m-1}$ were chosen via the inductive hypothesis. Since the expected value of the LHS of the displayed equation in the claim when we choose $A_m$ at random is at most $N\epsilon^R {k \choose R}$, we must be able to choose some specific $A_m$ for which the LHS satisfies the required inequality. QED.

Once the claim is proved, the $m=k$ case tells us that we can choose $A_1,\dots,A_k\in \mathcal{S}$ with $$\sum_{J\subset\{1,...,k\}, \#J=R} \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$ and so if we did chose $R$ such that $N\epsilon^R {k \choose R}<1$, this implies that $\sum_{J\subset\{1,...,k\}, \#J=R} \left(\# \bigcap_{j\in J} A_j\right) < 1$. But then since each summand in the LHS is a non-negative integer, it follows that they are in fact all zero, so for all $J\subset\{1,\dots,k\}$ with $\#J=R$, we have that $\bigcap_{j\in J} A_j=\emptyset$. This is equivalent to the statement that for each $i\in [N]$, $\#\{X\in\{A_1,\dots,A_k\}|i\in X\} \leq R$. So we are done, taking $\mathcal{A}=\{A_1,\dots,A_k\}$.

Source Link
blt
blt
  • 1.2k
  • 1
  • 10
  • 13

It does turn out to be possible to take $R$ as roughly $\log N/(-\log k\epsilon)$. More precisely, if you choose $R$ such that $N\epsilon^R {k \choose R}<1$, then you can always find $\mathcal{A}\subset \mathcal{S}$ of size $R$ satisfying the requirements in the question. The conclusion follows quickly from the following claim, which we establish by induction on $m$:

Claim: We can find sets $A_1,\dots, A_m \in \mathcal{S}$ such that $$\sum_{J\subset\{1,...,m\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$

Note that in this claim we adopt the ad-hoc notational convention that if $J$ is empty, $\bigcap_{j\in J} A_j$ should be taken to mean $[N]$. We also adopt the common convention that $a \choose b$ is 0 for $b<0$ or $b>a$.

Proof of claim: by induction on $m$. The case $m=0$ is trivially true. For $m>0$, we may by inductive hypothesis suppose that we have chosen $A_1,\dots, A_m \in \mathcal{S}$ so that $$\sum_{J\subset\{1,...,m-1\}} {k-m+1 \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$

Now imagine choosing $A_m$ uniformly at random from $\mathcal{S}$. We can evaluate the expected value of the LHS of the displayed equation in the claim as

\begin{align*} \mathbb{E}\sum_{J\subset\{1,...,m\}} &{k-m \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right) \\ =& \mathbb{E}\sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \left(\# \bigcap_{j\in J} A_j\right) \\ &\quad+ \mathbb{E}\sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J-1} \epsilon^{R-\#J-1} \left(\# \left(A_m\cap \bigcap_{j\in J} A_j\right)\right)\\ \leq& \sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J} \epsilon^{R-\#J} \left(\# \bigcap_{j\in J} A_j\right) \\ &\quad+ \sum_{J\subset\{1,...,m-1\}} {k-m \choose R - \#J-1} \epsilon^{R-\#J-1} \times \epsilon\times \left(\# \bigcap_{j\in J} A_j\right) \\ =& \sum_{J\subset\{1,...,m-1\}} \left[{k-m\choose R - \#J}+ {k-m\choose R - \#J-1}\right] \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right)\\ =& \sum_{J\subset\{1,...,m-1\}} {k-m+1 \choose R - \#J} \epsilon^{R-\#J} \times \left(\# \bigcap_{j\in J} A_j\right) \end{align*} which is $\leq N\epsilon^R {k \choose R}$ by the inequality that we got from the fact that $A_1,\dots,A_m$ were chosen via the inductive hypothesis. Since the expected value of the LHS of the displayed equation in the claim when we choose $A_m$ at random is at most $N\epsilon^R {k \choose R}$, we must be able to choose some specific $A_m$ for which the LHS satisfies the required inequality. QED.

Once the claim is proved, the $m=k$ case tells us that we can choose $A_1,\dots,A_k\in \mathcal{S}$ with $$\sum_{J\subset\{1,...,k\}, \#J=R} \left(\# \bigcap_{j\in J} A_j\right)\leq N\epsilon^R {k \choose R}$$ and so if we did chose $R$ such that $N\epsilon^R {k \choose R}<1$, this implies that $\sum_{J\subset\{1,...,k\}, \#J=R} \left(\# \bigcap_{j\in J} A_j\right) < 1$. But then since each summand in the LHS is a non-negative integer, it follows that they are in fact all zero, so for all $J\subset\{1,\dots,k\}$ with $\#J=R$, we have that $\bigcap_{j\in J} A_j=\emptyset$. This is equivalent to the statement that for each $i\in [N]$, $\#\{X\in\{A_1,\dots,A_k\}|i\in X\} \leq R$. So we are done, taking $\mathcal{A}=\{A_1,\dots,A_k\}$.