De Bruyne - Erdos theorem

A beam at seven points

The de Bruyne – Erdös theorem , one of the important results in the geometry of incidence , establishes an exact lower bound for the number of lines defined $n$ ${\ displaystyle n}$ $n$ points on the projective plane . By duality, this theorem implies a restriction on the number of intersections of the configuration of lines.

Content

1 History
2 Wording
3 Proof
4 Literature

History

Established by Nicholas de Bruyne and Pal Erdös in 1948 .

Wording

Let a set be given $P$ ${\ displaystyle P}$ of $n$ ${\ displaystyle n}$ points on the projective plane, of which not all lie on the same line. Let be $t$ ${\ displaystyle t}$ this is the number of all lines passing through pairs of points from $P$ ${\ displaystyle P}$ : Then $t\geqslant n$ ${\ displaystyle t \ geqslant n}$ . Moreover, if $t=n$ ${\ displaystyle t = n}$ , then any two lines intersect at a point from $P$ ${\ displaystyle P}$ .

Proof

The standard proof is by induction . The theorem is definitely true for three points that do not lie on the same line. Let be $n>3$ ${\ displaystyle n> 3}$ , the statement is true for $n-1$ ${\ displaystyle n-1}$ and $P$ ${\ displaystyle P}$ - many of $n$ ${\ displaystyle n}$ points, not all of which lie on one straight line. By Sylvester’s theorem, one of these lines passes exactly through two points from $P$ ${\ displaystyle P}$ . Denote these two points $a$ ${\ displaystyle a}$ and $b$ ${\ displaystyle b}$ .

If when deleting a point $a$ ${\ displaystyle a}$ all remaining points will be on one straight line, then $P$ ${\ displaystyle P}$ forms a bundle of $P$ ${\ displaystyle P}$ direct ( $n-1$ ${\ displaystyle n-1}$ simple straight lines go through $P$ ${\ displaystyle P}$ , plus one straight line passing through the remaining points). Otherwise delete $a$ ${\ displaystyle a}$ forms many $P$ ${\ displaystyle P}$ of $n-1$ ${\ displaystyle n-1}$ noncollinear points. By the assumption of induction, through $P$ ${\ displaystyle P}$ pass $n-1$ ${\ displaystyle n-1}$ lines that are at least one less than the number of lines passing through the points of the set $P$ ${\ displaystyle P}$ .

Literature

NG de Bruijn, P. Erdős. A combinatioral [sic] problem // Indagationes Mathematicae. - 1948 .-- T. 10 . - S. 421-423 .
Lynn Margaret Batten. Combinatorics of finite geometries. - Cambridge University Press, 1997. - S. 25–27. - ISBN 0-521-59014-0 .