What is the largest possible number of subsets of the set $\{1, 2, \dots , 2n+1\}$ such that the intersection of any two subsets consists of one or several consecutive integers?
Problem
Source:
Tags: floor function, graph theory
21.04.2013 14:25
the answer is n(n+1) because if we have subsets with the problem conditions we can add same elements to all of them so its better that we divide numbers to two groups and choose one from each side and the set will conclude all the numbers between so by AM-GM we know the maximum is n(n+1) so we are done
04.01.2014 23:32
There is a flaw in the above attempt, so I will restate the problem, and offer a proper and detailed solution. Let $m\geq 2$ be an integer. Let us call interval a subset $A \subseteq \{1,2,\ldots,m\}$ for which integers $1\leq a \leq b\leq m$ 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,m\}$, 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 a (non-empty) interval. Prove that $\displaystyle N \leq \left \lfloor (m+1)^2/4 \right \rfloor$, and that this bound is sharp. This was Proposition 2 in the article [R. Graham, M. Simonovits and V. Sós - A Note on the Intersection Properties of Subsets of Integers, Journal of Combinatorial Theory, Series A, 1980]. Solution. Let $A_i \subseteq B_i = [\min A_i, \max A_i] \cap \{1,2,\ldots,m\}$ for $1\leq i \leq N$, thus $B_i$ are intervals. Then if $B_i = B_j$ for some $i\neq j$, we also have $A_i = A_j$, since $A_i \cap A_j$ is an interval. From $A_i \cap A_j \subseteq B_i \cap B_j$ follows that $|B_i \cap B_j| \geq |A_i \cap A_j| \geq 1$, so the family $\mathcal{B}$ of the subsets $B_i$ also has the mentioned property. But obviously $\displaystyle \bigcap_{i=1}^N B_i \neq \emptyset$, so it must contain some element $a \in \{1,2,\ldots,m\}$. Then the lower endpoint of $B_i$ may be chosen in $a$ ways, while the upper endpoint of $B_i$ may be chosen in $m-a+1$ ways, therefore $N\leq a(m-a+1) \leq \left \lfloor (m+1)^2/4 \right \rfloor$. An example of such a maximal family is the family of all intervals containing the element $a = \left \lfloor (m+1)/2 \right \rfloor$, and so the bound is sharp. In our case, with $m=2n+1$, the number of sets is at most $(n+1)^2$, with a model given by all the intervals containing the element $n+1$.
04.01.2014 23:50
In 2011, I asked a more difficult question in the Stars of Mathematics contest, where in the definition of an interval we take $a<b$ rather than $a\leq b$, i.e. we ask the interval not to be degenerate to a single element. It was asked to prove the maximum number of such sets to be $\left \lfloor m^2/4\right \rfloor$. Solution. Let $A_i \subseteq B_i = [\min A_i, \max A_i] \cap \{1,2,\ldots,m\}$ for $1\leq i \leq N$, thus $B_i$ are intervals. Then if $B_i = B_j$ for some $i\neq j$, we also have $A_i = A_j$, since $A_i \cap A_j$ is an interval. From $A_i \cap A_j \subseteq B_i \cap B_j$ follows that $|B_i \cap B_j| \geq |A_i \cap A_j| \geq 2$, so the family $\mathcal{B}$ of the subsets $B_i$ also has the mentioned property. But $\displaystyle \bigcap_{i=1}^N B_i$ contains an interval of length (at least) $1$; let that be $[a+1,a+2]$. Then there are at most \[(a+1)(n-a-1) = \Bigg (\frac {m} {2} \Bigg )^2 - \left (a-\frac {m-2} {2} \right )^2\] possibilities, so $\displaystyle N \leq \left \lfloor m^2/4 \right \rfloor$. An example of such a maximal family is thus the family of all intervals containing the interval $\left [ \left \lfloor m/2 \right \rfloor, \left \lfloor m/2 \right \rfloor + 1\right ]$, and so the bound is sharp. Alternative Solution. Build the graph $G = (V,E)$, with $V=\{1,2,\ldots,m\}$ and \makebox{$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 m\}$, since then there will exist two members of $\mathcal{A}$ intersecting in one point only. Thus, by Mantel's theorem (in fact a special case of Turán's theorem), $N\leq \left \lfloor m^2/4 \right \rfloor$ and the only model is a quasi-balanced 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. Remark. This can be pushed even further. If we take $1\leq k\leq m$, and ask that for any $1\leq i < j \leq N$ we have $|A_i \cap A_j| \geq k$, with $A_i \cap A_j$ being an interval, it follows that $\displaystyle N \leq \left \lfloor \left (\frac {m-k+2} {2} \right )^2 \right \rfloor$. The solution is almost verbatim the first one used above. An example of such a maximal family is then the family of all intervals containing the interval $\left [ \left \lfloor \frac {m-k} {2} \right \rfloor + 1, \left \lfloor \frac {m-k} {2} \right \rfloor + k \right ]$, and so the bound is sharp.