incidence geometry In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An ''incide ...

, the De Bruijn–Erdős theorem, originally published by

Nicolaas Govert de Bruijn Nicolaas Govert "Dick" de Bruijn (; 9 July 1918 – 17 February 2012) was a Dutch mathematician, noted for his many contributions in the fields of analysis, number theory, combinatorics and logic.

and

Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...

in 1948, states a lower bound on the number of lines determined by ''n'' points in a

projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane (geometry), plane. In the ordinary Euclidean plane, two lines typically intersect at a single point, but there are some pairs of lines (namely, paral ...

. 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 Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

, 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 In geometry, collinearity of a set of Point (geometry), points is the property of their lying on a single Line (geometry), line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, t ...

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 John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician. He was active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many b ...

has a purely combinatorial proof which consequently also holds for points and lines over the

complex numbers In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form a ...

quaternions In mathematics, the quaternion number system extends the complex numbers. Quaternions were first described by the Irish mathematician William Rowan Hamilton in 1843 and applied to mechanics in three-dimensional space. The algebra of quaternion ...

and octonions.Stasys Jukna, ''Extremal Combinatorics'', Second edition, Springer Verlag, 2011, pages 167 - 168.

References

{{DEFAULTSORT:De Bruijn-Erdos theorem (incidence geometry) Theorems in projective geometry Euclidean plane geometry Theorems in discrete geometry Incidence geometry Paul Erdős