Combinatorics Seminar
Gyula O.H. Katona
MTA Renyi Institute (Budapest)
Largest union-intersecting families
Abstract: Janos Korner asked the following question. Let $[n]=\{
1,2,\ldots , n\}$ and let $\mathcal{F} \subset 2^{[n]}$ be
a family of its subsets. It is called union-intersecting if
$(F_1\cup F_2)\cap (F_3\cup F_4)$ is non-empty
whenever $F_1, F_2, F_3, F_4\in\mathcal{F}$ and $F_1\not=F_2, F_3\not=
F_4$. What is the maximum size of a union-intersecting family?
This question is answered in the present paper. The optimal construction
when $n$ is odd consists of all subsets of size at least ${n-1\over 2}$
while in the case of even $n$ it consists of all sets of size at least ${n
\over 2}$ and sets of size ${n\over 2}-1$ containing a fixed element, say 1.
We also proved some extensions, variants and analogues of this statement.
The following one is an example. Suppose that $\mathcal{F}$ is a union-intersecting
family of $k$-element subsets of $[n]$. We found that the optimal construction
for this problem consists of all $k$-element subsets of size $k$ containing the
element 1, and one more additional set, for $n>n(k)$. The results were jointly achieved with Daniel T. Nagy.
Monday April 20, 2015 at 3:00 PM in SEO 427