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)[1]. Ils concernent principalement des minorants du nombre de droites « déterminées » par un ensemble fini 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[2] 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[3].

Elekes et Tóth on remarqué que ce théorème ne s'étend pas facilement aux dimensions supérieures[4]. Soient par exemple 2n points de ℝ^3, disposés sur deux droites non coplanaires, n points par droite. Une telle configuration n'engendre que 2n plans. Ainsi, étendre trivialement l'hypothèse à des ensembles de points de ℝ^d ne suffit pas à obtenir le résultat souhaité.

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

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

Le théorème de Beck établit qu'un ensemble fini de points du plan tombe toujours dans l'un des deux cas extrêmes suivants : le cas où une grande partie des points sont sur une même droite, et le cas où il faut beaucoup de droites pour relier tous les points.

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^2/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.

Démonstration

Soient P un ensemble de n points du plan et j un entier strictement positif. Deux points A et B de P seront dits j-connectés si la droite qui les joint contient entre 2^j et 2^j + 1 – 1 points de P (en comptant A et B).

Déduisons du théorème de Szemerédi-Trotter que le nombre de droites de ce type est un O(n^2/2^3j + n/2^j). Considérons pour cela l'ensemble L des droites contenant au moins 2^j points de P. On remarque que

${\displaystyle |L|{2^{j} \choose 2}\leq {n \choose 2},}$

puisqu'une paire de points ne peut être incluse dans deux droites distinctes. D'après le théorème de Szemerédi-Trotter, il en résulte que le nombre d'incidences entre P et L est un O(n^2/2^2j + n). Les droites qui relient des points j-connectés appartiennent à L et chacune d'entre elles contribue au total par au moins 2^j incidences. Le nombre de ces droites est donc un O(n^2/2^3j + n/2^j).

Comme chacune d'elles relie Ω(2^2j) paires de points, on en déduit que le nombre de paires de points j-connectés est un O(n^2/2^j + 2^jn).

Soit C > 0 une constante arbitraire. En faisant la somme, sur les j tels que C ≤ 2^j ≤ n/C, de la série géométrique, on voit alors que le nombre de paires qui sont j-connectées pour l'un de ces j est un O(n^2/C).

D'autre part, le nombre total de paires est n(n – 1)/2. Donc si l'on choisit C assez grand, on peut trouver (par exemple) n^2/4 paires qui ne sont j-connectées pour aucun des j tels que C ≤ 2^j ≤ n/C. Les droites qui connectent ces paires passent soit par moins de 2C points, soit par plus de n/C points. Si au moins l'une des droites est dans ce second cas, on obtient la conclusion 1 du théorème de Beck. On peut donc se placer dans le cas où les n^2/4 paires sont toutes connectées par des droites passant par moins de 2C points. Mais chacune de ces droites ne peut connecter qu'au plus C(2C – 1) paires de points. Il y en a donc au moins n^2/4C(2C – 1) qui connectent au moins deux points, et la conclusion 2 du théorème s'ensuit en prenant K = 4C(2C – 1).

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).

1. (en) József Beck, « On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry », Combinatorica, vol. 3,‎ 1983, p. 281-297 (DOI 10.1007/BF02579184)
2. (en) « William O. J. Moser », Université McGill
3. (en) L. M. Kelly et W. O. J. Moser, « On the number of ordinary lines determined by n points », Canad. J. Math., vol. 10,‎ 1958, p. 210-219 (lire en ligne)
4. (en) György Elekes (en) et Csaba D. Tóth, « Incidences of not-too-degenerate hyperplanes », dans SCG '05, ACM Press, coll. « Annual Symposium on Computational Geometry », 2005 (ISBN 978-1-58113-991-4), p. 16-21
5. Beck 1983, Theorem 5.2