Théorème de Folkman

Le théorème de Folkman est un théorème en théorie combinatoire des nombres et théorie de Ramsey selon lequel, pour toute partition finie de l'ensemble des entiers strictement positifs, il existe un ensemble arbitrairement grand d'entiers dont toutes les sommes partielles appartiennent à la même partie de la partition. Découvert et démontré indépendamment par plusieurs mathématiciens, il a été baptisé « théorème de Folkman » (en mémoire de Jon Folkman (en)) par Graham, Rothschild et Spencer.

Énoncé

Soit (N₁, N₂, … , N_k) une partition finie de l'ensemble {1, 2, 3, … }. Pour tout entier m > 0, il existe un ensemble S de m entiers et un indice i tels que pour toute partie non vide T de S, la somme des éléments de T appartienne à N_i.

Liens avec les théorèmes de Schur et de Rado

Le théorème de Schur est le cas m = 2 du théorème de Folkman.

Le théorème de Rado porte lui aussi sur les partitions finies de l'ensemble {1, 2, 3, … } : il caractérise les matrices A à coefficients entiers pour lesquelles, quelle que soit la partition choisie, le système d'équations linéaires Ax = 0 a toujours une solution x dont toutes les coordonnées sont dans une même partie de la partition. Le théorème de Folkman en est le cas particulier correspondant aux systèmes

$x_{T}=\sum _{i\in T}x_{\{i\}},$

où T parcourt les parties non vides de l'ensemble {1, 2, … , m}.

Version multiplicative

On peut remplacer l'addition par la multiplication dans le théorème de Folkman : pour toute partition finie de {1, 2, 3, … }, il existe un ensemble arbitrairement grand S d'entiers tel que tous les produits de parties non vides de S soient dans une même partie de la partition. Il suffit en effet de choisir un S constitué uniquement de puissances de 2 pour se ramener à la version additive du théorème de Folkman. Cependant, on ne sait pas si les deux versions (additive et multiplicative) peuvent toujours être réalisées par un même S. On ne le sait même pas pour m = 2 : existe-t-il, quelle que soit la partition choisie, un ensemble de la forme {x, y, x + y, xy} inclus dans une même partie de cette partition ?

Résultats antérieurs

Richard Rado et Jon Sanders avaient démontré des variantes du théorème de Folkman .

Notes et références

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