2
$\begingroup$

Is there $n\in\mathbb{N}$ and a collection ${\cal C}$ of subsets of $\{1,\ldots,n\}$ with the following properties?

  1. $|{\cal C}| = n$,
  2. $|c| > 1$ for all $c\in {\cal C}$,
  3. $c\neq d \in {\cal C} \implies |c\cap d|=1$, and
  4. $\big|\{|c|: c\in {\cal C}\}\big| > 2$.
$\endgroup$

1 Answer 1

7
$\begingroup$

No, there isn't. This is essentially the dual version of the De Bruijn-Erdos theorem if the elements of $\mathcal C$ are the points, and the elements from $\{1,\ldots,n\}$ are the lines. The original proof is here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .