De Bruijn–Erdős theorem


\PMlinkescapephrase

finite plane

De Bruijn–Erdős theorem

Let S be a set of n0 ‘points’, say {L1,L2,Ln}, and let Λ1, Λ2, … Λν be ν different subsets of S of which any two have exactly one point in common. Now the De Bruijn–Erdős theorem says that νn, and that if ν=n then (up to renumbering) at least one of the following three must be true:

  • Λi={Li,Ln} for in, and Λn={Ln}

  • Λi={Li,Ln} for in, and Λn={L1,L2,Ln-1}

  • n is of the form q2+q+1, each Λi contains q+1 points, and each point is contained in q+1 of the Λ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 planesMathworldPlanetmath to satisfy some non-triviality conditions; unfortunately that also excludes projective planes of order 0 and 1.





The three cases of De Bruijn–Erdős drawn for n=ν=7 (q=2)

The formulation above was found in the literature [Cam94]. Naturally, if the Li are points we tend to interpret the subsets Λι as lines. However, interpreted in this way the condition that every two Λ 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 parallelMathworldPlanetmathPlanetmath. The absence of the dual condition, for two L 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.

Erdős–De Bruijn theorem

A dual formulation (which we could whimsically call the Erdős–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).




The three cases of Erdős–De Bruijn drawn for ν=n=7 (q=2)

Let Σ be a set of ν0 ‘points’, say {Λ1,Λ2,Λν}, and let L1, L2, … Ln be n subsets of Σ (‘lines’) such that for any two points there is a unique Li 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 incidentMathworldPlanetmathPlanetmath with them. Then nν, and if n=ν then (up to renumbering) at least one of the following three must be true:

  • Li={Λi} for in, and Ln={Λ1,Λ2,Λn}

  • Li={Λi,Λn} for in, and Ln={Λ1,Λ2Λn-1}

  • n is of the form q2+q+1, each Li contains q+1 points, and each point is contained in q+1 of the Li

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 2013-03-22 15:11:21
Last modified on 2013-03-22 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 GeometryMathworldPlanetmath
Related topic LinearSpace2