# Minimum size of an indexed intersection of unions of k-subsets

Let $S=\{1,...,n\}$, and let $k\leqslant n$ be some chosen number. Let $S_i\subseteq S$ be an arbitrary subset for each $i\in S$ with $|S_i|=k$, and let $f:S\times\{1,...,k\}\to S$ be a function which is injective on its second input (i.e., $f$ assigns to each element of $S$ exactly $k$ distinct elements in $S$). For which values of $k$ does there exist a nontrivial lower bound on the size of the set

$$T=\bigcap_{i\leqslant n} \bigcup_{j\leqslant k}S_{f(i,j)}?$$

By distributing, it's easy to see that the problem is equivalent to finding which values of $k$ guarantee the existence of a function $g:S\to\{1,...,k\}$ such that $\bigcap_{i\leqslant n} S_{f(i,g(i))}\neq\emptyset$.

Clearly for $k=1$ and $n>1$ this does not hold, and for $k=n$ it always holds. Trying to figure out the other values seems very difficult to me though.

As a related question, do there exist any values of $k<n$ for which we can always bound $|T|\geqslant k$?

We transform this hard formulated problem into an easy graph theory exercise. Fix $n$ and $k$. Given the sequence $\mathcal S=\{S_i\}$ consider the following bipartite graph, whose parts are $S$ and $\mathcal S$ and vertices $x\in S$ and $S_i\in\mathcal S$ are adjacent iff $s\not\in S_i$. Then degree of each $S_i$ is $n-k$ and degree of each vertex $x\in S\setminus T$ is at least $k$. So there are at most $\lfloor n(n-k)/k\rfloor =t’$ such vertices. On the other hand, given disjoint sets $S$ and $S’$ of size $n$ each, select some $\min\{t’,n\}$ vertices in $S$ and on steps from $1$ to $n$ add in total $n-k$ edges to some of them in such a way that temporary degree of each two selected vertices differs by at most one. Since $n-k\le \min\{t’,n\}$ this always can be done. Since $n(n-k)\ge t’k$, finally all selected vertices will have degree at least $k$. Now for each selected vertex $i$ we can choose distinct indices $f(i,1),\dots, f(i,k)$ such that $i\not\in\bigcup_{j\leqslant k}S_{f(i,j)}$, so $i$ will not belong to $T$. Thus the biggest lower bound on the size of the set $T$ is $\max\{n-t’,0\}=\max\{\lceil 2n-n^2/k\rceil,0\}$.