A collection of sets that cover all edges in Kn?

Question

The problem is the following:

Let $\mathcal{F}$ be a family of distinct proper subsets of {1,2,...,n}. Suppose that for every $1\leq i\neq j\leq n$ there is a unique member of $\mathcal{F}$ that contains both $i$ and $j$. Prove that $\mathcal{F}$ has at least $n$ elements.

I realized that each member $A_i$ in $\mathcal{F}$ can be regarded as a collection of edges in a clique induced by the element in $A_i$, and at the end all the members in $\mathcal{F}$ exactly cover all the edges in $K_n$ and every edge must live in exactly one member in $\mathcal{F}$. So if we write $\mathcal{F}=\{A_1,...,A_m\}$ with sizes $a_1,...,a_m$, respectively, then we obtain the following equation:

$a_1\choose 2$+...+$a_m\choose 2$ = $n\choose 2$ =$\frac{n(n-1)}{2}$.

I got stuck from here. Even if I assumed $m<n$, I cannot obtain a contradiction. Is my approach correct at all? If so, how should I continue? I appreciate any help and insights.

Answer 1

This result is known as the de Bruijn–Erdős theorem. It is usually stated in terms of incidence geometries. An incidence geometry has:

• A set of objects called points.
• A collection of sets of points called lines. If a line $\ell$ contains a point $P$, we also say that $P$ lies on $\ell$, or $\ell$ passes through $P$.

We require that for any two points, there is a unique line passing through both.

We also make some nontriviality assumptions. Each line contains two points (though this doesn't matter for this question, since single-point lines only help us). There is not a line containing all the points (which does matter for your question: the subsets in $\mathcal F$ must be proper subsets, or the conclusion is false).

In your case, $\{1,2,\dots,n\}$ is the set of points and $\mathcal F$ is the set of lines.

---

The de Bruijn–Erdős theorem simply says that in any incidence geometry, there are at least as many lines as points.

If you've gone ahead and read the Wikipedia article I linked to earlier, then you've seen the proof there, which assumes a Euclidean incidence geometry: one in which the points are some finite set of points in the plane, and the lines are actual lines drawn through those points. This is not the proof that de Bruijn and Erdős gave, for which you can read their original paper; their proof applies to any abstract incidence geometry, and so it solves your problem.

A few years ago, I also wrote an alternative writeup of their proof, which you can find here.

Answer 2

A parital solution:

Let $n \in \mathbb{N}$ and let $\mathcal{F}$ such that $\forall i,j \in [n]\exists S\in \mathcal{F}:i,j\in S$ and that $S$ is unique.
Denote by $t$ the size of the biggest set in $\mathcal{F}$ and assume WLOG that the set is $S=\{1,...,t\}$.

Case 1: $t\ge \frac{n}{2}$:
For each $i \in S$, we must have a set containing the pair $(t+1,i)$, and as we can't have $2$ elements from $S$ together in another set, we must have $t$ new sets.
As $t+2$ can be in at most $1$ of the above sets, we need at least $t-1$ new sets for $t+2$ (to have the edges $(t+2,i): i\in S$). We can continue similarly until $n=t+(n-t)$ intoduces $t-(n-t-1)$ new sets.
We got a total of $$1+t(n-t)-(0+1+...+n-t-1)=1+t(n-t)-\frac{(n-t)(n-t-1)}{2}=$$ $$ 1+\frac{n-t}{2}(3t-n+1)$$ sets.
Treating $t$ as a variable and $n$ fixed, we can see that the function has a global maxima at $t \sim \frac{2}{3}n$ so it is enough to check for $t=n-1, \frac{n}{2}$.
For $t=n-1$ we get $n$ subsets, which is exactly enough.
For $t=\frac{n}{2}$ we get $\ge \frac{n}{4}(\frac{n}{2}+1)$. We want it to be $\ge n$ so we need $\frac{n}{2} + 1 \ge 4$ or $n\ge 6$.
So we solved for this case for every $n$ above $5$, and for $n=2,3,4,5$ it can be verified manually.

Case 2: $t < \frac{n}{2}$
First we can observe that if there are less than $n$ subsets in $\mathcal{F}$, then $t\ge \sqrt n$:
Each set contributes at most $t \choose 2$ pairs and we have at most $n-1$ subsets, and so at most $(n-1)\binom{t}{2}$. On the other hand, we know there are exactly $n \choose 2$ pairs. So, we got that $$\binom{n}{2}\le (n-1)\binom{t}{2}\rightarrow n\le t(t-1)\le t^2 \rightarrow t\ge \sqrt n$$
We can use a similar method to the previous case to deduce that there are at least $1+2+...+t$ other subsets, so there are at least $\binom{\sqrt{n} + 1}{2}\ge \frac{n}{2}$ subsets.
I was not able to improve the bound in this case.

Hope it gives you an idea that can generalize it to a complete solution.