PlanetMath: De Bruijn--Erdős theorem

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (34)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

De Bruijn--Erdős theorem

(Theorem)

De Bruijn-Erdős theorem

Let 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 of which any two have exactly one point in common. Now the De Bruijn-Erdős 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}\}$
is of the form , each $\Lambda_i$ contains points, and each point is contained in of the $\Lambda_i$

and we recognise the last case as finite projective planes of order . For () the first and last case overlap, and for () 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.

$\begin{picture}(200,78)(-100,0) \par \put(-122,+30){\begin{picture}(100,48)(0,0)... ...cases of De\,Bruijn--Erd\H{o}s drawn for $n=\nu=7$\ ($q=2$)}} \par \end{picture}$

The formulation above was found in the literature [Cam94]. Naturally, if the are points we tend to interpret the subsets $\Lambda_\iota$ as lines. However, interpreted in this way the condition that every two $\Lambda$ 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 $\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 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).

$\begin{picture}(200,78)(-100,-90) \par \put(-122,-30){\begin{picture}(100,48)(0,... ...cases of Erd\H{o}s--De\,Bruijn drawn for $\nu=n=7$\ ($q=2$)}} \par \end{picture}$

Let $\Sigma$ be a set of $\nu\ne0$ `points', say $\{\Lambda_1,\Lambda_2,\dots \Lambda_\nu\}$ , and let , , ... be subsets of $\Sigma$ (`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 $n\ge\nu$ , and if $n=\nu$ then (up to renumbering) at least one of the following three must be true:

$L_i=\{\Lambda_i\}$ for $i\ne n$ , and $L_n=\{\Lambda_1,\Lambda_2,\dots \Lambda_n\}$
$L_i=\{\Lambda_i,\Lambda_n\}$ for $i\ne n$ , and $L_n=\{\Lambda_1,\Lambda_2 \Lambda_{n-1}\}$
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].

Bibliography

Cam94: PETER J.CAMERON, Combinatorics: topics, techniques, algorithms,
Camb. Univ. Pr. 1994, ISBN0521457610
http://www.maths.qmul.ac.uk/˜pjc/comb/ (solutions, errata &c.)

"De Bruijn--Erdős theorem" is owned by marijke.

(view preamble)

Keywords:

incidence, finite geometry

Log in to rate this entry.
(view current ratings)

Cross-references: incidence structure, plane, parallel lines, finite planes, linear space, parallel, lines, projective planes, contained, contains, subsets, points
There is 1 reference to this entry.

This is version 3 of De Bruijn--Erdős theorem, born on 2005-04-11, modified 2005-08-27.
Object id is 6945, canonical name is DeBruijnErdHosTheorem.
Accessed 2160 times total.

Classification:

AMS MSC:

05B25 (Combinatorics :: Designs and configurations :: Finite geometries)

Pending Errata and Addenda

None.[ View all 3 ]

Discussion

forum policy

No messages.

Interact