|
Let $S$ be a set of $n\ne0$ `points', say $\{L_1,L_2,\dots L_n\}$ , and let $\Lambda_1$ , $\Lambda_2$ , ... $\Lambda_\nu$ be $\nu$ different subsets of $S$ of which any two have exactly one point in common. Now the De Bruijn-Erdos theorem says that $\nu\le n$ , and that if $\nu=n$ then (up to renumbering) at least one of the following three must be true:
- $\Lambda_i=\{L_i,L_n\}$ for $i\ne n$ , and $\Lambda_n=\{L_n\}$
- $\Lambda_i=\{L_i,L_n\}$ for $i\ne n$ , and $\Lambda_n=\{L_1,L_2,\dots L_{n-1}\}$
- $n$ is of the form $q^2+q+1$ , each $\Lambda_i$ contains $q+1$ points, and each point is contained in $q+1$ of the $\Lambda_i$
and we recognise the last case as finite 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. 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, if the  are points we tend to interpret the subsets  as lines. However, interpreted in this way the condition that every two  share an  says rather more than is needed for the structure to be a finite plane (linear space) as it insists that no two lines are
parallel. The absence of the dual condition, for two  to share a  , 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.
A dual formulation (which we could whimsically call the Erdos-De Bruijn Theorem) remedies both under- and over-specification 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  be a set of  `points', say
 , and let  ,  , ...  be  subsets of  (`lines') such that for any two points there is a unique  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  , and if  then (up to renumbering) at least one of the following three must be true:
-
 for  , and
-
 for  , and
 is of the form  , each  contains  points, and each point is contained in  of the 
For a proof of the theorem (in the former version) see e.g. Cameron [Cam94].
- Cam94
- PETER J.CAMERON, Combinatorics: topics, techniques, algorithms,
Camb. Univ. Pr. 1994, ISBN0521457610
http://www.maths.qmul.ac.uk/~pjc/comb/ (solutions, errata &c.)
|
