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 ''incidenc ...

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

lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an ele ...

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. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that ...

. 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 an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many app ...

, De Bruijn and Erdős noted in their paper that the analogous ( Euclidean) result is a consequence of the

Sylvester–Gallai theorem The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, ...

, 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 points is the property of their lying on a single line. A set of points with this property is said to be collinear (sometimes spelled as colinear). In greater generality, the term has been used for aligned ...

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

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 active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches o ...

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. Hamilton defined a quate ...

and

octonions In mathematics, the octonions are a normed division algebra over the real numbers, a kind of hypercomplex number system. The octonions are usually represented by the capital letter O, using boldface or blackboard bold \mathbb O. Octonions have ...

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

References

Sources

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