De Bruijn–Erdős theorem
De Bruijn–Erdős theorem
Let $S$ be a set of $n\ne 0$ ‘points’, say $\{{L}_{1},{L}_{2},\mathrm{\dots}{L}_{n}\}$, and let ${\mathrm{\Lambda}}_{1}$, ${\mathrm{\Lambda}}_{2}$, … ${\mathrm{\Lambda}}_{\nu}$ be $\nu $ different subsets of $S$ of which any two have exactly one point in common. Now the De Bruijn–Erdős theorem says that $\nu \u2a7dn$, and that if $\nu =n$ then (up to renumbering) at least one of the following three must be true:

•
${\mathrm{\Lambda}}_{i}=\{{L}_{i},{L}_{n}\}$ for $i\ne n$, and ${\mathrm{\Lambda}}_{n}=\{{L}_{n}\}$

•
${\mathrm{\Lambda}}_{i}=\{{L}_{i},{L}_{n}\}$ for $i\ne n$, and ${\mathrm{\Lambda}}_{n}=\{{L}_{1},{L}_{2},\mathrm{\dots}{L}_{n1}\}$

•
$n$ is of the form ${q}^{2}+q+1$, each ${\mathrm{\Lambda}}_{i}$ contains $q+1$ points, and each point is contained in $q+1$ of the ${\mathrm{\Lambda}}_{i}$
and we recognise the last case as http://planetmath.org/node/6943finite projective planes of order $q$. For $n=1$ ($q=0$) the first and last case overlap, and for $n=3$ ($q=1$) the last two cases do. The second case is also known as a nearpencil. The last two cases together are examples of linear spaces.
To exclude the first two cases one usually defines projective planes^{} to satisfy some nontriviality conditions; unfortunately that also excludes projective planes of order 0 and 1.
The formulation above was found in the literature [Cam94]. Naturally, if the ${L}_{i}$ are points we tend to interpret the subsets ${\mathrm{\Lambda}}_{\iota}$ as lines. However, interpreted in this way the condition that every two $\mathrm{\Lambda}$ share an $L$ says rather more than is needed for the structure to be a finite plane (http://planetmath.org/node/3509linear space) as it insists that no two lines are parallel^{}. The absence of the dual condition, for two $L$ to share a $\mathrm{\Lambda}$, actually means we have too little for the structure to be a finite plane (linear space), as for two points we may not have a line through them. And indeed, while the second and third cases are finite planes without parallel lines, the first case is not a plane.
Erdős–De Bruijn theorem
A dual formulation (which we could whimsically call the Erdős–De Bruijn Theorem) remedies both under and overspecification for a plane. Indeed, the conditions are now exactly tailored to make the structure a finite plane (with some parallel lines in the first of the three cases).
Let $\mathrm{\Sigma}$ be a set of $\nu \ne 0$ ‘points’, say $\{{\mathrm{\Lambda}}_{1},{\mathrm{\Lambda}}_{2},\mathrm{\dots}{\mathrm{\Lambda}}_{\nu}\}$, and let ${L}_{1}$, ${L}_{2}$, … ${L}_{n}$ be $n$ subsets of $\mathrm{\Sigma}$ (‘lines’) such that for any two points there is a unique ${L}_{i}$ that contains them both. We must now be careful about the points (the former lines) being “different” (this was easier to formulate in the previous version, in which form it was a simple incidence structure): this condition now takes the form that no two points must have the same collection of lines that are incident^{} with them. Then $n\u2a7e\nu $, and if $n=\nu $ then (up to renumbering) at least one of the following three must be true:

•
${L}_{i}=\{{\mathrm{\Lambda}}_{i}\}$ for $i\ne n$, and ${L}_{n}=\{{\mathrm{\Lambda}}_{1},{\mathrm{\Lambda}}_{2},\mathrm{\dots}{\mathrm{\Lambda}}_{n}\}$

•
${L}_{i}=\{{\mathrm{\Lambda}}_{i},{\mathrm{\Lambda}}_{n}\}$ for $i\ne n$, and ${L}_{n}=\{{\mathrm{\Lambda}}_{1},{\mathrm{\Lambda}}_{2}{\mathrm{\Lambda}}_{n1}\}$

•
$n$ is of the form ${q}^{2}+q+1$, each ${L}_{i}$ contains $q+1$ points, and each point is contained in $q+1$ of the ${L}_{i}$
For a proof of the theorem (in the former version) see e.g. Cameron [Cam94].
References
 1

Cam94
Peter J. Cameron,
Combinatorics: topics, techniques, algorithms,
Camb. Univ. Pr. 1994, ISBN 0 521 45761 0
http://www.maths.qmul.ac.uk/ pjc/comb/http://www.maths.qmul.ac.uk/ pjc/comb/ (solutions, errata &c.)
Title  De Bruijn–Erdős theorem 

Canonical name  DeBruijnErdHosTheorem 
Date of creation  20130322 15:11:21 
Last modified on  20130322 15:11:21 
Owner  marijke (8873) 
Last modified by  marijke (8873) 
Numerical id  7 
Author  marijke (8873) 
Entry type  Theorem 
Classification  msc 05B25 
Related topic  FiniteProjectivePlane4 
Related topic  IncidenceStructures 
Related topic  Geometry^{} 
Related topic  LinearSpace2 