De Bruijn–Erdős theorem (incidence geometry)

Gives a lower bound on the number of lines determined by n points in a projective plane This article is about the number of lines determined by a finite set of points. For coloring infinite graphs, see De Bruijn–Erdős theorem (graph theory).

In incidence geometry, the De Bruijn–Erdős theorem, originally published by Nicolaas Govert de Bruijn and Paul Erdős in 1948, states a lower bound on the number of lines determined by n points in a projective plane. By duality, this is also a bound on the number of intersection points determined by a configuration of lines.

Although the proof given by De Bruijn and Erdős is combinatorial, De Bruijn and Erdős noted in their paper that the analogous (Euclidean) result is a consequence of the Sylvester–Gallai theorem, by an induction on the number of points.

Statement of the theorem

Let P be a configuration of n points in a projective plane, not all on a line. Let t be the number of lines determined by P. Then,

t ≥ n, and
if t = n, any two lines have exactly one point of P in common. In this case, P is either a projective plane or P is a near pencil, meaning that exactly n - 1 of the points are collinear.

Euclidean proof

The theorem is clearly true for three non-collinear points. We proceed by induction.

Assume n > 3 and the theorem is true for n − 1. Let P be a set of n points not all collinear. The Sylvester–Gallai theorem states that there is a line containing exactly two points of P. Such two point lines are called ordinary lines. Let a and b be the two points of P on an ordinary line.

If the removal of point a produces a set of collinear points then P generates a near pencil of n lines (the n - 1 ordinary lines through a plus the one line containing the other n - 1 points).

Otherwise, the removal of a produces a set, P' , of n − 1 points that are not all collinear. By the induction hypothesis, P' determines at least n − 1 lines. The ordinary line determined by a and b is not among these, so P determines at least n lines.

J. H. Conway's proof

John Horton Conway has a purely combinatorial proof which consequently also holds for points and lines over the complex numbers, quaternions and octonions.

References

^ De Bruijn, N. G.; Erdős, P. (1948), "On a combinatioral [sic] problem" (PDF), Indagationes Mathematicae, 10: 421–423
^ Batten, Lynn Margaret (1997), "2.2 The De Bruijn–Erdős theorem", Combinatorics of Finite Geometries (2nd ed.), Cambridge University Press, pp. 25–27, ISBN 0-521-59014-0
Stasys Jukna, Extremal Combinatorics, Second edition, Springer Verlag, 2011, pages 167 - 168.

v t e Incidence structures
Representation	Incidence matrix Incidence graph
Fields	Combinatorics Block design Steiner system Geometry Incidence Projective plane Graph theory Hypergraph Statistics Blocking
Configurations	Complete quadrangle Fano plane Möbius–Kantor configuration Pappus configuration Hesse configuration Desargues configuration Reye configuration Pasch configuration Schläfli double six Cremona–Richmond configuration Kummer configuration Grünbaum–Rigby configuration Klein configuration Dual
Theorems	Sylvester–Gallai theorem De Bruijn–Erdős theorem Szemerédi–Trotter theorem Beck's theorem Bruck–Ryser–Chowla theorem
Applications	Design of experiments Kirkman's schoolgirl problem

Categories: