1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.