# Enseignement

## Leçon inaugurale – Combinatoire

Cette leçon était une introduction à la combinatoire, un domaine des mathématiques dont les racines remontent aux xviiie et xixe siècles mais qui n’est devenue un domaine de recherche majeur que dans la deuxième moitié du xxe siècle. Parmi les résultats discutés, citons le problème des ponts de Königsberg, résolu par Euler, le théorème des quatre couleurs, conjecturé au xixe siècle mais qui n’a été résolu qu’en 1976 par Appel et Haken à l’aide de plus de 1 200 heures de calcul informatique, la preuve par Erdős d’une limite inférieure pour le théorème de Ramsey, qui a lancé la méthode probabiliste en combinatoire, et le théorème de Szemerédi, qui a joué un rôle clé dans mes propres recherches et plus généralement en combinatoire additive, un sous-domaine de la combinatoire qui concerne les ensembles d’entiers. La conférence s’est terminée par une discussion sur certaines des applications de la combinatoire en dehors des mathématiques.

## Cours – Les outils de la combinatoire (en ligne)

La combinatoire est un domaine qui tend à se concentrer davantage sur la résolution de problèmes que sur le développement de la théorie. Néanmoins, les solutions aux problèmes qui sont les plus célèbres sont souvent celles qui introduisent un nouvel outil ou une nouvelle technique qui peuvent être appliqués dans de nombreuses autres situations. Ce cours porte sur six outils de ce type. Chacun d’entre eux permet de résoudre des problèmes qui seraient très difficiles à résoudre autrement.

### Cours 1 – Probabilité (I) : utiliser la moyenne et le moment de second ordre

Il est évident que la plus grande valeur possible d’une quantité aléatoire est au moins aussi grande que la valeur moyenne de cette quantité et que la plus petite valeur possible est au plus aussi grande que la valeur moyenne. De manière surprenante, cette observation très basique s’avère extrêmement utile si la quantité aléatoire est bien choisie. Par exemple, en examinant le nombre moyen de cliques et de stables d’une taille donnée dans un graphe aléatoire, Erdős a déduit qu’il existe des graphes pour lesquels la plus grande clique et le plus grand stable sont tous deux très petits. Cette preuve a donné naissance à la méthode probabiliste en combinatoire. En utilisant la variance de quantités aléatoires, on peut pousser la méthode plus loin et prouver des résultats qui ne découlent pas de la seule considération de la moyenne.

### Cours 2 – Probabilité (II) : la concentration de la mesure en grande dimension

Le phénomène de concentration de la mesure consiste en ce qu’une somme de nombreuses petites quantités aléatoires suffisamment indépendantes a de grandes chances d’être proche de sa moyenne. Ce phénomène permet de prouver de nombreux résultats pour lesquels la méthode de la variance n’est pas suffisamment puissante. Un exemple en est un résultat en théorie des irrégularités de distribution : il est possible de colorer les arêtes d’un graphe complet à n sommets en utilisant les couleurs rouge et bleue de telle sorte que pour tout sous-ensemble de sommets, le nombre d’arêtes bleues diffère du nombre d’arêtes rouges d’au plus 100 n3/2.

### Cours 3 – Analyse : la transformation de Fourier discrète et ses applications

L’analyse de Fourier est l’un des outils les plus importants de la combinatoire additive. Étant donné un sous-ensemble d’un groupe abélien fini, la transformation de Fourier de sa fonction caractéristique encapsule une grande partie de l’information essentielle sur la structure additive de ce sous-ensemble, c’est-à-dire sur les relations additives qui existent entre ses éléments. Cela peut être utilisé pour donner des preuves de nombreux résultats qui sont difficiles à prouver en utilisant des méthodes combinatoires directes. Un exemple clé est un théorème de Roth, qui affirme que tout ensemble d’entiers de densité positive contient une progression arithmétique de longueur 3.

### Cours 4 – Entropie : comment l’utiliser pour obtenir des bornes sur la taille d’un ensemble

L’entropie d’une distribution de probabilité sur un ensemble fini X est en gros le nombre moyen de questions oui/non qu’il faut poser pour déterminer quel élément de X a été choisi lorsqu’il a été choisi au hasard selon cette distribution. Par exemple, l’entropie de la distribution uniforme sur un ensemble de taille 1 024 est de 10, puisque chaque question permet de diviser le nombre de possibilités par 2. L’entropie permet d’estimer la taille de certains ensembles, puisque si l’on peut trouver une distribution de probabilité sur un ensemble X et montrer que son entropie est au moins égale à n, alors X doit avoir une taille au moins égale à 2n. Cela ne semble pas, à première vue, être une observation utile, puisque, si toute distribution sur X a une entropie d’au moins n, alors il en est de même pour la distribution uniforme. Cependant, il arrive parfois qu’il existe d’autres distributions pour lesquelles il est beaucoup plus facile d’obtenir des bornes inférieures pour leur entropie. J’ai donné plusieurs exemples d’applications surprenantes de l’entropie pour résoudre des problèmes combinatoires.

### Cours 5 – Algèbre (I) : applications de l’algèbre linéaire

De nombreux problèmes combinatoires se présentent sous la forme suivante : on donne un ensemble X et on demande quelle taille peut avoir un sous-ensemble A de X s’il vérifie certaines propriétés. Une technique surprenante pour résoudre de tels problèmes est de plonger X dans un espace vectoriel V, d’obtenir une limite supérieure pour la dimension de V, et de montrer que, si A satisfait aux propriétés données, alors ses éléments correspondent à un ensemble indépendant dans V. De nombreux problèmes qui ont été résolus de cette façon semblent n’avoir aucun rapport avec l’algèbre linéaire, mais un indice que l’algèbre linéaire peut être utile est qu’il semble y avoir de nombreux sous-ensembles A qui atteignent la taille maximale possible, tout comme dans un espace vectoriel il y a de nombreux ensembles linéairement indépendants maximaux.

### Cours 6 – Algèbre (II) : la méthode des polynômes

La méthode des polynômes n’est pas tant une méthode qu’un ensemble diversifié de techniques permettant de résoudre des problèmes combinatoires en trouvant les polynômes associés et en exploitant leurs propriétés. Par exemple, de simples arguments d’algèbre linéaire peuvent être utilisés pour montrer que pour tout petit ensemble, il y aura un polynôme non trivial de bas degré (dans de nombreux contextes, un polynôme en plusieurs variables) qui disparaît sur cet ensemble. Si l’ensemble a d’autres propriétés, cela peut être une information suffisante pour obtenir une contradiction, puisque les polynômes sont des objets « rigides », dans le sens où la connaissance de certaines de leurs valeurs en détermine beaucoup d’autres. Parmi les résultats discutés dans cette conférence, on trouve la solution de Dvir au problème de Kakeya en champs finis et une limite supérieure exponentiellement petite, due à Ellenberg et Gijswijt, pour la version en champs finis du théorème de Roth sur les progressions arithmétiques.

## Séminaire

Annulé en raison de la pandémie.

# Recherche

Un groupe fini peut être caractérisé comme un ensemble fini avec une opération binaire associative qui est injective dans chaque variable séparément. Le premier des quatre articles énumérés ci-dessous concerne la question de savoir ce que l’on peut dire si x(yz) = (xy)z pour seulement une proportion positive, par exemple 1 %, de triplets (x,y,z) dans l’ensemble. Jason Long et moi observons qu’une telle opération binaire ne semble pas devoir coïncider sur un grand ensemble avec une opération de groupe, mais qu’elle doit coïncider sur un grand ensemble avec une opération binaire qui se rapproche d’une opération de groupe dans un sens métrique.

Un célèbre théorème de Ruzsa et Szemerédi concerne le nombre maximal de triangles dans un graphe dont aucune arête n’est contenue dans plus d’un triangle. La meilleure borne inférieure connue pour ce problème provient d’une construction de Behrend dans les années 1940. Barnabás Janzer et moi utilisons une construction différente pour obtenir une borne inférieure similaire pour un problème généralisé où l’on suppose qu’aucune clique de r sommets n’est contenue dans plus d’une clique de s sommets. (Le problème original est le cas r = 2, s = 3).

Les deux articles avec Luka Milićević concernent des versions « quadratiques » de résultats « linéaires » bien connus en combinatoire additive. Le théorème de Bogolyubov, un lemme très utile dans le sujet, montre qu’une convolution itérée de la fonction caractéristique d’un sous-ensemble dense d’un groupe abélien fini doit être à peu près constante sur des ensembles hautement structurés connus sous le nom d’ensembles de Bohr qui ressemblent à des ensembles de solutions d’équations linéaires. Nous avons prouvé qu’une « convolution bilinéaire » itérée doit être à peu près constante sur des ensembles qui ressemblent à des ensembles de solutions d’équations bilinéaires. Dans le second article, nous prouvons un lemme qui montre que les applications multilinéaires définies sur des analogues multilinéaires de ces ensembles coïncident sur de grands sous-ensembles multilinéaires avec des applications multilinéaires définies partout.

# Publications

Gowers W.T. et Long J., « Partial associativity and rough approximate groups », Geometric and Functional Analysis, vol. 30, no 6, 2020, p. 1583-1647, https://doi.org/​10.1007/​s00039-020-00553-1 [arXiv : 1904.08732].

Gowers W.T. et Janzer B., « Generalizations of the Ruzsa-Szemerédi and rainbow Turán problems for cliques », Combinatorics, Probability and Computing, vol. 30, no 4, 2021, p. 591-608, https://doi.org/​10.1017/​S0963548320000589 [arXiv : 2003.02754].

Gowers W.T. et Milićević L., « A bilinear version of Bogolyubov’s theorem », Proceedings of the American Mathematical Society, vol. 148, 2020, p. 4695-4704, https://doi.org/​10.1090/​proc/​15129 [arXiv : 1712.00248].

Gowers W.T. et Milićević L., « A note on extensions of multilinear maps defined on multilinear varieties », Proceedings of the Edinburgh Mathematical Society, vol. 64, no 2, 2021, p. 148-173, https://doi.org/​10.1017/​S0013091521000055 [arXiv : 1906.04807].