If we take a small subset of a sparse/uniform set system, how uniform can we arrange for the subset to be?

Question

Fix a positive integer $N$ and a real $\epsilon>0$. I'll write $[N]$ for the set $\{1,\dots,N-1,N\}$, $\mathcal{P}X$ to denote the power set of a set $X$, and $\#X$ to denote the number of elements of a finite set $X$.

Suppose $\mathcal{S}\subset \mathcal{P}[N]$ is a set-system which satisfies the following 'sparseness/uniformity' property: for every $j\in[N]$, we have that

$$\#\{X\in\mathcal{S}|j\in X\} \leq \epsilon\,\#\mathcal{S}$$

We could paraphrase this property as: for each $j$ in $[N]$, if we pick an element of $\mathcal{S}$ at random, the chance that it contains $j$ is at most $\epsilon$. Very roughly: "$\mathcal{S}$ is not concentrated anywhere".

As an example, we could take $\mathcal{S}$ to be all the subsets of $[N]$ containing exactly $\lfloor \epsilon N \rfloor$ elements.

Now fix an integer $k$. We'd like to pick a $k$-element subset $\mathcal{A}\subset\mathcal{S}$ which is 'still not particularly concentrated anywhere', in the sense that there exists some $R$ such that for each $j$ in $[N]$, $$\#\{X\in\mathcal{A}|j\in X\} \leq R$$

What's the smallest $R$ (in terms of $N$, $\epsilon$ and $k$) for which this will always be possible, however $\mathcal{S}$ was chosen?

Obviously, $R=k$ is possible; the question is how much better than this one can do! Heuristically, it looks like for $k$ smaller than about $\log N/(-\log\epsilon)$ you need to take $R=k$, but for $k$ larger than this but smaller than $1/\epsilon$ (if there are any such $k$) you can take something like $R=\log N/(-\log k\epsilon)$ and still be OK. But this is based on very rough heuristics, so is quite possibly completely unreliable.

It seems like this must be a routine or at least well-studied problem, but I don't know what search terms to use to find the literature that would tell me how to solve it, since I'm not an extremal combinatorialist by trade.

I'd be very happy with just an asymptotic solution. In the applications I have in mind, $N$ should be 'large' (say: growing like $10^n$ for some parameter $n$), while $\epsilon$ should be small (going to zero like say $2^{-n}$), and I'm interested in cases where $k$ is something roughly polynomial in $n$.

Answer 1

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