Sets of sets: near-pencils and projective planes

Question

Suppose $n$ is a positive integer. Let ${\cal C}$ be a set of subsets of $X:=\{1,\ldots,n\}$ with the following properties:

1. all members of ${\cal C}$ contain at least $2$ elements, and $X\notin {\cal C}$;
2. $A\neq B\in {\cal C}$ implies $|A\cap B| = 1$; and
3. $|{\cal C}| = n$.

Doe this imply that at least one of the following statements is true?

(S1) All members of ${\cal C}$ have equal cardinality (in that case ${\cal C}$ is called a "projective plane");

(S2) There is $A\in{\cal C}$ such that $|A| = n-1$ (in that case ${\cal C}$ is called a "near pencil").

Answer 1

Yes, it is true and known. See Bourbaki Theory of sets, excersises to the chapter III (ordered sets), $\S 5$ (properties of integers). It is ex. 14 in English edition of 1968.

The proof goes as follows. At first, we denote $|\cal C|=m$ and do not assume for a moment that $m=n$, but prove that $m\leqslant n$. Assume that some element $y$ belongs to a unique set $A\in \cal C$. If $|A|=2$, all sets in $\cal C$ should contain $A\setminus \{y\}$ and have no other common elements, this gives even $m\leqslant n-1$. If $|A|\geqslant 3$, we may remove $y$ from $X$ and from $A$ and (say, using induction) we again get $m\leqslant n-1$. So, we may suppose that each element $y$ belongs to at least two sets from $\cal C$.

Take an element $x\in X$ and a set $A\in \cal C$, denote $f(x)$ the number of sets containing $x$. Note that if $x\notin A$, then $f(x)\leqslant |A|$, else by pigeonhole principle there exist two sets $A_1,A_2\in \cal C$ containing $x$ for which $C_1\cap A=C_2\cap A$, and hence $|C_1\cap C_2|\geqslant 2$, a contradiction. Choose a set $A$ such that $|A|:=t$ is minimal. For any $a\in A$ choose a set $B_a\in \cal C$ containing $a$ and different from $A$. If $A=\{1,2,\dots,t\}$, we have $i\notin B_{i+1}$ (indicies are taken modulo $t$). Therefore $\sum_{i=1}^t f(i)\leqslant \sum_{i=1}^t |B_i|$. If now $X=\{1,\dots,n\}$, we have $f(i)\leqslant |A|$ for $i=t+1,\dots,n$. Summing up we get $\sum_{i\in X} f(i)\leqslant \sum_{i=1}^t |B_i|+(n-t)|A|$. But $\sum_{i\in X} f(i)=\sum_{B\in \cal C} |B|$, so we get that the sum of sizes of certain $m-t$ sets from $\cal C$ does not exceed $(n-t)|A|$. By minimality of $|A|$ this is not possible when $m>n$. If $m=n$, it is possible only if all sets except $B_1,\dots,B_t$ have size equal to $t$ and each element outside $A$ is contained exactly in $t$ sets from $\cal C$. Consider two cases.

1) $t=2$, $A=\{1,2\}$. If $1$ is contained in $f(1)=k+1$ sets from $\cal C$, then 2 is contained in $n-k$ sets from $\cal C$, and for all pairs of sets $B\ni 1$, $C\ni 2$ from $\cal C\setminus \{A\}$ the intersections $B\cap C$ are different, thus $n\geqslant 2+k(n-1-k)$, $k=1$ or $k=n-2$. If, say, $k=1$, then the set containing 1 different from $A$ contains $n-1$ elements and we get a near-pencil.

2) $t>2$. Since we have equality, we get $f(1)=|B_2|\geqslant t\geqslant 3$, so we may replace $B_1$ to a different set containing 1. This gives $|B_1|=t$. Analogously, all sets have cardinality $t$.