De Bruijn–Erdős theorem

finite plane

De Bruijn–Erdős theorem

Let $S$ be a set of $n\ne 0$ ‘points’, say $\{L_1,L_2,\mathrm{\dots }{L}_n\}$, andlet ${\mathrm{\Lambda }}_1$, ${\mathrm{\Lambda }}_2$, … ${\mathrm{\Lambda }}_{\nu }$ be $\nu$ different subsetsof $S$ of which any two have exactly one point in common. Now the De Bruijn–Erdős theorem says that $\nu ⩽n$, 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}_{n-1}\}$

• $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 near-pencil. The last two cases together are examples of linear spaces.

To exclude the first two cases one usually defines projective planes to satisfy some non-triviality conditions; unfortunately that also excludes projective planes of order 0 and 1.

The formulation above was found in the literature [Cam94]. Naturally, ifthe $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 tobe 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–DeBruijn Theorem) remedies both under- and over-specification for a plane.Indeed, the conditions are now exactly tailored to make the structure a finiteplane (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 containsthem both. We must now be careful about the points (the former lines) being“different” (this was easier to formulate in the previous version, in whichform it was a simple incidence structure): this condition now takes theform that no two points must have the same collection of lines that areincident with them. Then $n⩾\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 }}_{n-1}\}$

• $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].