Trois protagonistes, Esther Klein, Paul Erdös et George Szekeres apparaissent dans le happy end problem, les voici sur la photo en logo, en Australie, plus précisément à Newcastle, en 1984.

L’observation d’Esther Klein

Commençons par un élégant énoncé
dû à une jeune mathématicienne hongroise du début des années 30, Esther Klein :

Parmi cinq points du plan en position générale,
il en existe quatre qui sont les sommets d’un quadrilatère convexe.

Avant de justifier cet énoncé, rappelons quelques notions de géométrie plane.
Un ensemble de points du plan est en position générale
lorsque trois d’entre eux ne sont jamais alignés.
Une région du plan est convexe si,
chaque fois qu’elle contient deux points distincts, elle contient aussi le segment qui les joint.
Par exemple, les trois régions que voici

Trois régions convexes

sont convexes, et les trois que voilà

Trois régions non convexes

On observe que le segment reliant les deux points bleus de la région de gauche n’est pas contenu dans la région.

ne le sont pas.
Rappelons aussi que toute partie du plan est contenue dans des régions convexes,
et en particulier dans une région convexe bien particulière qui est la plus petite d’entre elles,
et qu’on appelle son enveloppe convexe.
Par exemple, la partie du plan formée des points rouges de la figure suivante
est contenue dans son enveloppe convexe qui est le polygone à bord bleu.

Enveloppe convexe bleue d’une partie formée de points rouges

Voici la démonstration, élémentaire, de l’énoncé d’Esther Klein.

On se donne $5$ points du plan en position générale. Leur enveloppe convexe est un polygone dont on note $k$ le nombre des sommets.
Si $k=4$, il n’y a plus rien à montrer.
Si $k = 5$, tout choix de $4$ de ces sommets fournit un quadrilatère convexe.
Le seul cas qui mérite encore un argument est donc celui où l’enveloppe convexe
des $5$ points donnés est un triangle ($k=3$), ce que nous supposons désormais.
Notons $A, B, C$ les sommets de ce triangle, et $D, E$ les deux autres points donnés,
qui sont à l’intérieur du triangle.
Notons encore $\ell$ la droite passant par $D$ et $E$.
Vu l’hypothèse de position générale,
la droite $\ell$ ne passe par aucun des sommets $A, B, C$.
Comme elle ne peut pas couper les trois côtés du triangle,
il existe deux sommets situés du même côté de $\ell$ ;
supposons les notations telles que ce soient $B$ et $C$.
Alors $B, C, D, E$ sont les sommets d’un quadrilatère convexe. La démonstration est ainsi achevée.

Illustration de la démonstration

Le premier article : Paul Erdös et George Szekeres

La Budapest des années 30 foisonnait de jeunes mathématiciens brillants.
Celui qui est devenu le plus célèbre est Paul Erdös (1913—1996).
Il y avait aussi Paul Turan (1910—1976), Esther Klein (1910—2005),
George Szekeres (1911—2005), et bien d’autres.
L’observation d’Esther eut plusieurs suites :
en 1935 un article marquant d’Erdös et Szekeres,
et peut-être aussi en 1937 le mariage d’Esther et George,
ou Eszter et György ;
d’où la terminologie du « happy end problem », due à Erdös.

Leurs carrières ne furent pas banales.
Bien que passionnés de mathématiques,
George Szekeres fit des études de chimie
(son père espérait qu’il contribue à l’affaire de la famille, dans le cuir),
et Esther Klein de physique
(Esther ayant le double handicap d’être femme et juive, elle dut laisser
« la » place d’étudiante en mathématique à son amie Marta Sved).

Après avoir échappé in extremis aux persécutions nazies à Budapest
et aux bombes japonaises sur Shanghai, les Szekeres s’établirent en Australie en 1948, où ils furent d’abord hébergés par les Sved.
George Szekeres y fut un mathématicien productif et influent jusqu’au début des années 2000 (il n’avait pourtant jamais obtenu de diplôme en mathématiques !).
Ses sujets principaux de recherche furent la combinatoire, la géométrie,
et la relativité générale.
Dès 1964, il fut à Sydney le professeur fondateur du département de mathématiques fondamentales de l’Université de New South Wales [2].
En 1998, l’un de nous occupa un bureau à côté du sien,
d’où il entendait l’après-midi George et Esther dans leur duo de violons.
Esther Szekeres enseigna à l’Université Macquarie,
et s’investit beaucoup dans la stimulation mathématique des collégiens et lycéens. La base de données MathSciNet recense pour elle deux articles de recherche en mathématiques.

Le « happy end » dura : Esther et George moururent
de vieillesse à une heure d’intervalle.

Quant à Paul Erdös, il détient de nombreux records, dont celui du plus grand
nombre d’articles publiés (1421 dans la liste de MathSciNet au jour de notre dernier pointage),
et du plus grand nombre de co-auteurs (498 selon la même base de données).
On entretient à son sujet les légendes les plus incroyables,
et souvent vraies
 [3].

Les triangles et les quadrilatères sont les deux premières espèces
d’une population qui comprend des pentagones (polygones à $k=5$ côtés),
les hexagones ($k=6)$, les heptagones ($k=7$), ...

Un heptagone convexe

Lorsqu’on veut préciser qu’un certain polygone a exactement $k$ côtés,
on dit que c’est un $k$-gone.

L’article d’Erdös et Szekeres de 1935
 [4],
Compositio Math. 2 (1935), 463-470, énonce la généralisation « évidente » suivante du problème d’Esther Klein :

Pour un nombre donné $k$, peut-on trouver un nombre $N$ (dépendant de $k$)
tel que, de toute partie du plan contenant au moins $N$ points en position générale,
on puisse en choisir $k$ qui soient les sommets d’un $k$-gone convexe ?

Il y a en fait plusieurs questions : d’abord existe-t-il un tel $N$ ?
et si oui quelle est sa plus petite valeur possible, notée $N(k)$ ci-dessous ?
à défaut, peut-on au moins l’estimer ?

Théorème d’Erdös et Szekeres.
Pour tout $k \ge 3$, il existe un nombre entier $N(k)$
qui a les propriétés suivantes :

1. Soit $X$ un ensemble de $n$ points dans le plan, en position générale.
   Si $n \ge N(k)$, il existe $k$ points dans $X$ qui sont les sommets
   d’un $k$-gone convexe.
2. Dans 1. l’entier $N(k)$ ne peut pas être remplacé par un entier strictement plus petit.

L’article original offre deux démonstrations,
chacune fournissant pour tout $k$ une borne, c’est-à-dire une majoration de $N(k)$.
Mais ces bornes ne sont pas optimales, loin s’en faut.
Ainsi, pour $k=5$, la première borne est de l’ordre de $2^{10 000}$
(en anticipant une notation introduite plus bas,
disons que cette borne résulte de l’inégalité $N(k) \le R_4(5, k)$).
La seconde borne est $21$. Or un collègue d’Erdös et Szekeres
avait déjà montré en 1935 que la meilleure borne possible est $N(5)=9$.

Même s’il suffit souvent de savoir que le nombre $N(k)$ existe
et d’en connaître un majorant,
il est bien naturel de vouloir déterminer sa valeur exacte.
La conjecture qui suit, due à Erdös et Szekeres,
repose sur leur conviction, pour nous à la fois éclairée et mystérieuse ;
elle est vieille de 80 ans, et toujours ouverte :

\[ N(k) = 2^{k-2} + 1 \hskip.5cm \text{(non démontré)} \]

pour tout $k \ge 3$.
Par exemple, pour $k=7$, personne n’a encore pu montrer que,
dans tout ensemble de 33 points en position générale,
on peut toujours en trouver $7$ qui sont les sommets d’un heptagone convexe.

Quelques progrès

Autant que nous sachions, les seuls cas pour lesquels nous connaissions
exactement $N(k)$ aujourd’hui sont ceux pour lesquels $k \le 6$.
Plus précisément, en plus de l’égalité banale $N(3) = 3$ :

\[ N(4) = 5, \ N(5) = 9 \,\text{ et }\, N(6) = 17 . \]

La valeur $17$ pour $k=6$ fut établie par Szekeres lui-même
(avec son collègue Peters et un ordinateur bien programmé),
dans un article rédigé peu avant sa mort et paru en 2006,
septante ans après le premier article !
Bel exemple d’idée fixe (et fructueuse).

Vingt-cinq ans après leur premier article sur le sujet,
Erdös et Szekeres en publièrent un second
 [5],
dans lequel ils exhibent pour tout $k \ge 4$ un ensemble de $2^{k-2}$ points
en position générale sans qu’il existe $k$ de ces points
qui soient les sommets d’un $k$-gone convexe.
Il en résulte que $2^{k-2}+1 \le N(k)$.

Quatre points qui ne sont pas les sommets d’un quadrilatère convexe

Il existe aussi des majorations, de sorte qu’on sait
par exemple que

\[ 262.645 \le N(20) \le 4.537.567.650 \]

pour $k=20$, et en général que

\[ 2^{k-2} + 1 \le N(k) \le \binom{2k-5}{k-2} + 1 \]

pour tout $k \ge 5$.

Au membre de droite apparaît un coefficient binomial
de la forme $\binom{a}{b}$, où $a$ et $b$ sont deux nombres entiers
tels que $a \ge b \ge 0$ ;
par définition $\binom{a}{b} = \frac{a!}{b! (a-b)!}$.
Le point d’exclamation
désigne une factorielle : $a! = a (a-1) (a-2) \cdots 2 \cdot 1$ ;
par exemple $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$ et

\[ \binom{7}{4} \, = \, \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} {4 \cdot 3 \cdot 2 \cdot 1 \hskip.1cm \cdot \hskip.1cm 3 \cdot 2 \cdot 1} \, = \, \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} \, = \, 35 . \]

La borne supérieure pour $N(k)$ a péniblement progressé :
par exemple $\binom{2k-4}{k-2}+1$ en 1935,
$\binom{2k-4}{k-2}$ en 1998 (Chung et Graham, 63 ans pour cette petite amélioration,
mais une nouvelle idée),
$\binom{2k-5}{k-2}+2$ en 1998 (Tóth et Valtr),
et $\binom{2k-5}{k-2}+1$ en 2005 (les mêmes).

On est encore loin de la valeur conjecturée $2^{k-2}+1$,
puisque

\[ \binom{2k-5}{k-2} \, \approx \, \frac{1}{ \sqrt{\pi k} } 2^{2k-5} \, >> \, 2^{k-2}+1 . \]

Le signe $\approx$ indique que les termes à gauche et à droite ont le même ordre de grandeur
pour $k$ grand,
et le signe $>>$ se lit « beaucoup plus grand que ».

Théorie de Ramsey

L’article initial d’Erdös et Szekeres fut un point de départ
pour de nombreux travaux et résultats, dans plusieurs sujets.
Parmi eux la géométrie combinatoire,
dont nous ne dirons rien sinon
que c’est un sujet d’origine assez récente
qui regorge de problèmes ouverts captivants
 [6].
Et aussi la théorie de Ramsey, sur laquelle nous
avons choisi d’en dire un peu plus.

Frank Plumpton Ramsey fut une étoile filante. Anglais, né en 1903, il étudia les mathématiques à Cambridge, fut aussi étudiant de l’économiste Keynes, avait une connaissance encyclopédique de la littérature anglaise, et entreprit à Vienne une psychanalyse avec un disciple de Freud.
C’est à Vienne qu’il rencontra le philosophe Wittgenstein,
dont il fut plus tard le directeur de thèse à Cambridge.
Ramsey mourut à 26 ans.
Ses écrits vont de la logique mathématique à l’économie en passant par la philosophie.
Aujourd’hui, on s’en souvient surtout par un théorème qui fut d’abord
un lemme mineur dans un article de logique formelle paru en 1930.
Voici un cas particulier des énoncés tels qu’on les connaît aujourd’hui.
Pour une paraphrase des formulations de Ramsey
qui soit plus fidèle à l’original mais néanmoins en langage moderne
(et toutefois largement hors-piste), voir la section 1.7 de
 [7].

Théorème de Ramsey.
Soit $p, q, r$ des entiers tels que $p \ge r \ge 1$ et $q \ge r$.
Il existe un entier $R_r(p, q)$ qui a les propriétés suivantes :

1. Soit $X$ un ensemble fini à $n \ge \max \{p,q\}$ éléments
   et $S$ l’ensemble de ses parties à $r$ éléments.
   On suppose de plus $S$ divisé en deux parties disjointes, $T$ et $U$.
   Alors, si $n \ge R_r(p, q)$, l’une au moins des propriétés suivantes est satisfaite :
   • il existe une partie $P$ de $X$ à $p$ éléments telle que toute partie de $P$ à $r$ éléments est dans $T$,
   • il existe une partie $Q$ de $X$ à $q$ éléments telle que toute partie de $Q$ à $r$ éléments est dans $U$.
2. Dans 1. l’entier $R_r(p, q)$ ne peut pas être remplacé par un entier strictement plus petit.

En d’autres termes, si on cherche un peu d’ordre ($r$ éléments tous de la même espèce) et qu’on a des ambitions limitées, on est sûr de le trouver ($P$ ou $Q$) dans tout désordre suffisamment grand ($X$ avec au moins $R_r(p,q)$ éléments).

Notons que, même si on ne s’intéresse qu’aux nombres de Ramsey
pour lesquels $p=q$, les démonstrations que nous connaissons
procèdent par récurrence sur $r$, $p$ et $q$, et font intervenir des nombres
avec $p \ne q$. L’essentiel de la démonstration du Théorème de Ramsey consiste à montrer que

\[ R_r(p,q) \, \le \, R_{r-1}\left( R_r(p-1,q), R_r(p,q-1) \right) + 1 . \]

Par exemple :

\[ R_2(p,q) \, \le \, R_1(R_2(p-1,q), R_2(p,q-1)) +1 = R_2(p-1,q) + R_2(p,q-1) \]

pour tous $p,q \ge 2$.
(Pour en voir un peu plus, signalons le livre
 [8].)

Quelques égalités portant sur ces nombres de Ramsey sont faciles à déterminer.
Ainsi : $R_r(q,p) = R_r(p,q)$ pour tous $p,q,r$ avec $p,q \ge r \ge 1$.
Notons aussi que $R_1(p,q) = p+q-1$ pour tous $p,q \ge 1$ ;
par exemple, si je veux sortir à l’aveugle d’un tiroir contenant des chaussettes rouges et bleues
une paire de la même couleur, il suffit toujours que je sorte $R_1(2,2) = 3$ chaussettes.

Lorsque $r=2$, l’énoncé du théorème peut se reformuler comme suit.
On considère un ensemble $X$ à $n$ éléments,
vu comme les sommets d’un $n$-gone convexe.
L’ensemble $S$ s’identifie à celui des côtés et diagonales de ce polygone ;
par exemple, l’ensemble $S$ contient $10$ éléments pour un pentagone,
$15$ pour un hexagone, en général $\binom{n}{2}$ côtés et diagonales pour un $n$-gone.
La partition de $S$ s’interprète comme un coloriage de ces segments :
convenons que $T$ est l’ensemble des segments rouges et $U$ celui des segments bleus.

Il est alors presqu’évident que $R_2(p,2) = p$ pour tout $p \ge 2$.
En effet, si on colorie les segments d’un $p$-gone, ou bien ils seront tous rouges et leurs sommets constituent un ensemble rouge à $p$ éléments,
ou bien il y en a au moins un bleu dont les sommets constituent un ensemble bleu à 2 éléments.

Voici encore l’argument élémentaire classique montrant que $R_2(3,3) = 6$,
argument qui apparaît par exemple déjà
ici.
On considère l’ensemble $X$ des sommets d’un hexagone
dont les côtés et diagonales sont coloriés en rouge et en bleu ; on cherche un triangle ou bien à 3 côtés rouges ou bien à 3 côtés bleus.

Illustration de la démonstration de $R_2(3,3) \le 6$

Soit $A$ un sommet de $X$. Comme $A$ est l’origine de cinq segments,
il en existe au moins trois de la même couleur, disons rouge
(si c’était bleu, la suite du raisonnement serait analogue).
Notons $B, C, D$ les autres sommets de ces trois segments.
Si les trois côtés du triangle de sommets $B, C, D$ sont bleus, il n’y a plus rien à montrer.
Sinon, disons que c’est le côté $BC$ qui est rouge,
et alors les trois côtés du triangle de sommets $A, B, C$ sont rouges.

Nous avons ainsi montré que $R_2(3,3) \le 6$,
et nous laissons au lecteur le soin de se convaincre que $R_2(3,3) > 5$
(en dessinant un pentagone à côtés rouges et diagonales bleues).

A part quelques cas exceptionnels, dont ceux évoqués ci-dessus,
on ne sait pas calculer les nombres $R_r(p,q)$. On sait au mieux les estimer,
et souvent de manière grossière. Par exemple, le mieux que nous sachions
concernant $R_2(5,5)$ semble être la fourchette

\[ 43 \, \le \, R_2(5,5) \, \le \, 49 , \]

malgré de très nombreux efforts pour préciser ces inégalités.
De même,

\[ 798 \, \le \, R_2(10, 10) \, \le \, 23556 \]

(d’après
 [9]
).

Le théorème de Ramsey fut l’objet
de développements et d’applications innombrables,
auxquels Erdös contribua de manière fondamentale.

À propos de la démonstration de l’existence d’une borne pour $N(k)$

Terminons par quelques indications sur la démonstration
de bornes pour les entiers $N(k)$ qui interviennent dans le théorème
d’Erdös et Szekeres.
Nous suivons le livre de van Lint et Wilson cité plus haut
plutôt que l’article original de 1935 ;
les deux sources font appel au théorème de Ramsey.
En fait, Szekeres a découvert lui-même le théorème de Ramsey,
après Ramsey mais indépendamment de lui, pour les besoins
du théorème d’Erdös et Szekeres (selon la préface d’Erdös
au livre déjà cité de Brass, Moser et Pach).

Il y a d’abord une observation élémentaire mais cruciale pour la suite :

Pour qu’un polygone à $k \ge 4$ côtés soit convexe, il faut et il suffit que
chacun des quadrilatères déterminé par $4$ de ses sommets soit convexe.

Indiquons alors comment on montre que $N(k) \le R_3(k,k)$ pour tout $k \ge 4$.
Soit $X$ un ensemble de $N = R_3(k,k)$ points en position générale
dans un plan.
Soit $S$ l’ensemble des triplets $\{A,B,C\}$ de points de $X$.
Notons $T$ l’ensemble de ces triplets pour lesquels
le triangle de sommets $A,B,C$ contient un nombre pair (peut-être nul)
de points de $X$,
et $U$ son complémentaire dans $S$.
On choisit dans $X$ un $k$-uplet $P$ de sommets dont tous les triplets sont ou bien dans $T$
ou bien dans $U$.
Aucun des quadruplets de $P$
ne fournit un triangle avec un point intérieur, comme l’indique la figure suivante,

Illustration de la démonstration

Figure de gauche : les trois petits triangles contiennent des nombres pairs de points
(0, 2, 4, tous bleus) et le grand un nombre impair (7, point rouge compris).
Figure de droite : les trois petits triangles contiennent des nombres impairs de points
(1, 3, 5) et le grand un nombre pair (10).

Donc, chacun des quadruplets de $P$ constitue les sommets d’un quadrilatère convexe

Pour un aperçu sur les nombreuses variantes que le problème
de Klein-Erdös-Szekeres a suggérées,
nous signalons la section 8.2 du livre de Brass, Moser et Pach,
ainsi que le chapitre 3 d’un livre de J. Matousek
 [10].