In incidence geometry, the De Bruijn–Erdős theorem, originally published by Nicolaas Govert de Bruijn and Paul Erdős in 1948, [1] 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. [2]
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. [1]
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. [2]
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. [3]
References
- ^ a b De Bruijn, N. G.; Erdős, P. (1948), "On a combinatioral [sic] problem" (PDF), Indagationes Mathematicae, 10: 421–423
- ^ a b 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.
In incidence geometry, the De Bruijn–Erdős theorem, originally published by Nicolaas Govert de Bruijn and Paul Erdős in 1948, [1] 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. [2]
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. [1]
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. [2]
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. [3]
References
- ^ a b De Bruijn, N. G.; Erdős, P. (1948), "On a combinatioral [sic] problem" (PDF), Indagationes Mathematicae, 10: 421–423
- ^ a b 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.