Suppose that $ \mathcal F$ is a family of subsets of $ X$. $ A,B$ are two subsets of $ X$ s.t. each element of $ \mathcal{F}$ has non-empty intersection with $ A, B$. We know that no subset of $ X$ with $ n - 1$ elements has this property. Prove that there is a representation $ A,B$ in the form $ A = \{a_1,\dots,a_n\}$ and $ B = \{b_1,\dots,b_n\}$, such that for each $ 1\leq i\leq n$, there is an element of $ \mathcal F$ containing both $ a_i, b_i$.
Problem
Source: Iranian National Olympiad (3rd Round) 2004
Tags: graph theory, combinatorics proposed, combinatorics
01.10.2014 19:34
There is a lot of lacking clarity. What does "We know that no subset of $ X$ with $ n - 1$ elements has this property" mean? Taking $\mathcal{F}$ some family of subsets of $X$, all containing some element $x\in X$, and $A,B$ some subsets of $X$ also containing $x$. What given condition does this construction contradict?
02.10.2014 18:26
I think, there is no other way of interpretation and the problem should be read as: Suppose that $ \mathcal F$ is a family of subsets of $ X$. For a subset $X_1\subset X$ we say $X_1$ has the property $P$ if each element of $ \mathcal{F}$ has non-empty intersection with $X_1$. We know that no subset of $ X$ with $ n - 1$ elements has this property. Let $ A,B$ be two subsets of $ X$, with $n$ elements each, such that they both have property $P$. Prove that $ A,B$ can be represented in the form $ A = \{a_1,\dots,a_n\}$ and $ B = \{b_1,\dots,b_n\}$, such that for each $ 1\leq i\leq n$ there is an element of $ \mathcal F$ containing both $ a_i, b_i$. This is a good exercise on the Hall's marriage theorem. Let $ A =\{a_1,\dots,a_n\} ,\, B =\{b_1,\dots,b_n\} $. Imagine a bipartite graph $G$ which parts are the vertices in $A$ and $B$, where $a_i$ and $b_j$ are connected iff there exists a set in $ \mathcal{F}$ containing both $ a_i, b_j$. Now prove that $G$ satisfies the marriage condition. It's easy, since otherwise (omitting some elements of $A$ and adding some elements of $B$) there will exist a set with fewer than $n$ elements also with property $P$. Thus, there is a perfect matching in $G$ and we are done.