AoPS - Problem

Source: Stars of Mathematics 2011 - Juniors - Problem 4

Tags: floor function, graph theory, combinatorics proposed, combinatorics

mavropnevma

11.10.2012 00:36

Let $n\geq 2$ be an integer. Let us call interval a subset $A \subseteq \{1,2,\ldots,n\}$ for which integers $1\leq a < b\leq n$ do exist, such that $A = \{a,a+1,\ldots,b-1,b\}$. Let a family $\mathcal{A}$ of subsets $A_i \subseteq \{1,2,\ldots,n\}$, with $1\leq i \leq N$, be such that for any $1\leq i < j \leq N$ we have $A_i \cap A_j$ being an interval. Prove that $\displaystyle N \leq \left \lfloor n^2/4 \right \rfloor$, and that this bound is sharp. (Dan Schwarz - after an idea by Ron Graham)

In the contest I gave a solution using Helly Theorem, but meanwhile I found a more beautiful one. Build the graph $G = (V,E)$, with $V=\{1,2,\ldots,n\}$ and {$E = \{ \{\min A,\max A\} \mid A\in \mathcal{A} \}$} (notice $\{\min A,\max A\} = \{\min A',\max A'\}$ implies $A=A'$, since $A\cap A'$ is an interval for $A\neq A'$), so $|E| = |\mathcal{A}| = N$. But $G$ can contain no triangle $\{1\leq i<j<k\leq n\}$, since then there will exist two members of $\mathcal{A}$ intersecting in one point only. Thus, by Turan's Theorem, $N\leq \left \lfloor n^2/4 \right \rfloor$ and the only model is a complete bipartite graph, with its shores being $\{\min A \mid A\in \mathcal{A}\}$ and $\{\max A \mid A\in \mathcal{A}\}$, this being such that $\displaystyle \max_{A\in \mathcal{A}} \ \min A < \min_{A\in \mathcal{A}} \ \max A$, corresponding to the construction shown above.