Théorème de De Bruijn-Erdős (géométrie d'incidence)

En géométrie d'incidence (en), le théorème de De Bruijn-ErdÅ‘s, dû à Nicolaas Govert de Bruijn et Paul ErdÅ‘s[1], fournit un minorant (égal à ${\displaystyle n}$) du nombre de droites déterminées par ${\displaystyle n}$ points, dans un plan projectif. Par dualité, ${\displaystyle n}$ est aussi un minorant du nombre de points d'intersections déterminés par une configuration de ${\displaystyle n}$ droites non concourantes.

Bien que leur preuve fût combinatoire, De Bruijn et Erdős remarquaient dans leur article que le résultat analogue en géométrie affine est une conséquence du théorème de Sylvester-Gallai, par récurrence sur le nombre de points.

Cas où ${\displaystyle n-1}$ points sont alignés. Les ${\displaystyle n}$ points déterminent alors ${\displaystyle n}$ droites.

Énoncé

Si ${\displaystyle n\geqslant 3}$ points non alignés du plan projectif déterminent ${\displaystyle N}$ droites, alors

• ${\displaystyle N\geqslant n}$,
• si ${\displaystyle N=n}$, deux quelconques des ${\displaystyle N}$ droites ont l'un des ${\displaystyle n}$ points en commun.

${\displaystyle n}$ points cocycliques déterminent ${\displaystyle {\binom {n}{2}}}$ droites

Notons qu'à l'opposé ${\displaystyle N}$ est inférieur ou égal à ${\displaystyle {\binom {n}{2}}}$ puisque deux points déterminent une droite et une seule.

Ce majorant est atteint par exemple pour des points cocycliques.

Démonstration

On raisonne par récurrence. Le résultat est clair pour n = 3.

Supposons que n > 3 et que le théorème est vrai pour n − 1, et soit P un ensemble de n points non alignés. Le théorème de Sylvester-Gallai assure que P détermine au moins une droite ordinaire, c'est-à-dire contenant exactement deux de ces points. Soient a et b deux tels points.

• Si les n − 1 (> 2) points distincts de a sont alignés, leur droite contient b et pas a. Dans ce cas, les points distincts de b forment un ensemble P' de n − 1 points non alignés. D'après notre hypothèse, P' détermine n − 1 droites, ce qui est exactement une de moins que le nombre de droites déterminées par P (puisque la droite joignant a et b est absente).
• Sinon, les points distincts de a forment un ensemble P' de n − 1 points non alignés. À nouveau, d'après notre hypothèse, P' détermine n − 1 droites, ce qui est au moins une de moins que le nombre de droites déterminées par P

Notes et références

1. (en) N. G. de Bruijn et P. ErdÅ‘s, « On a combinatioral problem Â», Indagationes Mathematicae, vol. 10,‎ 1948, p. 421-423 (lire en ligne)

• (en) Lynn Margaret Batten, Combinatorics of finite geometries, CUP, 1997, 2^e Ã©d., 208 p. (ISBN 978-0-521-59014-3), chap. 2.2 (« The de Bruijn–ErdÅ‘s theorem Â»), p. 25-27

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « De Bruijn–ErdÅ‘s theorem (incidence geometry) Â» (voir la liste des auteurs).

Article connexe

Inégalité de Fisher