Théorème de De Bruijn-Erdős (géométrie d'incidence)
En géométrie d'incidence , le théorème de De Bruijn-Erdős, dû à Nicolaas Govert de Bruijn et Paul Erdős[1], fournit un minorant du nombre de droites déterminées par n points, dans un plan projectif. Par dualité, c'est aussi un majorant du nombre de points d'intersections déterminés par une configuration de droites.
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.
Énoncé
Si n points non alignés du plan projectif déterminent t droites, alors
- t ≥ n,
- si t = n, deux quelconques des t droites ont l'un des n points en commun.
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
- (en) N. G. de Bruijn et P. Erdős, « On a combinatioral problem », Indagationes Mathematicae, vol. 10, , p. 421-423 (lire en ligne)
- (en) Lynn Margaret Batten, Combinatorics of finite geometries, CUP, , 2e é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).
