Théorème de Beck

En géométrie discrète, le théorème de Beck peut faire référence à plusieurs résultats différents, dont deux sont donnés ci-dessous. Tous deux ont été publiés, avec d'autres théorèmes importants, dans un article fameux de József Beck (en). Ils concernent principalement des minorants du nombre de droites « déterminées » par un ensemble de points du plan, c'est-à-dire contenant au moins deux points de cet ensemble.

Théorème d'Erdős-Beck

Le théorème d'Erdős-Beck est une variante d'un résultat classique de Leroy Milton Kelly (en) et William O. J. Moser sur les configurations de n points dont au plus n – k sont alignés, pour un certain k tel que 0 < k < O(√n). Ils avaient montré que pour n assez grand par rapport à k, la configuration engendre au moins kn – (1/2)(3k + 2)(k – 1) droites.

Le résultat suivant, conjecturé par Erdős, a été démontré par Beck.

Théorème — Soit S un ensemble de n points du plan, dont au plus n – k sont alignés, pour un certain k tel que 0 ≤ k < n – 2. Alors, le nombre de droites déterminées par les points de S est un Ω(nk).

Théorème de Beck

Bien que cela ne soit pas mentionné dans l'article de Beck, son résultat peut se déduire du théorème d'Erdős-Beck (en posant k = n(1 – 1/C)).

Énoncé

Il existe des constantes positives C et K telles que pour n points quelconques du plan, au moins l'un des deux énoncés suivants soit vrai :

1. Il y a une droite qui contient au moins n/C des points.
2. Il y a au moins n²/K droites dont chacune contient au moins deux des points.

Dans l'énoncé originel de Beck, C est égal à 100 et K n'est pas précisé ; on ne sait pas quelles sont les valeurs optimales pour C et K.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Beck's theorem » (voir la liste des auteurs).