Accueil🇫🇷Chercher

Théorème de Rado (théorie de Ramsey)

Le théorème de Rado est un théorème issu de la branche des mathématiques appelée théorie de Ramsey, portant le nom du mathématicien allemand Richard Rado. Ce théorème a été démontré dans sa thèse Studien zur Kombinatorik (1933).

Soit Ax = 0 un système d'équations linéaires, où A est une matrice à coefficients entiers. Le système est dit r-régulier si, pour chaque r-coloriage[1] des entiers naturels non nuls 1, 2, 3, ..., le système admet une solution monochromatique. Un système est dit régulier s'il est r-régulier pour tout r ≥ 1.

Le théorème de Rado affirme qu'un système d'équations Ax = 0 est régulier si et seulement si A remplit la condition des colonnes. Notons ci la ième colonne de la matrice A. La matrice A remplit la condition des colonnes s'il existe une partition des indices de colonnes C1, C2, ..., Cn telle que si , alors

  1. s1 = 0
  2. pour tout i ≥ 2, si peut être écrit comme une combinaison linéaire à coefficients rationnels[2] des colonnes cj dont les indices j appartiennent à la réunion des Ck avec k < i.

Le théorème de Folkman, qui affirme qu'il existe des ensembles finis d'entiers de cardinal m arbitrairement grand tels que toute somme non vide d'éléments de ces ensembles soit monochromatique, peut être vu comme un cas particulier du théorème de Rado. Le système considéré serait alors le suivant

pour toute partie T de {1, 2, ..., m}[3].

Notes et références

  1. C'est-à-dire une partition en r sous-ensembles.
  2. (en) Béla Bollobás, Modern graph theory, , 1re éd., 394 p. (ISBN 978-0-387-98488-9, lire en ligne), p. 204
  3. Ronald L. Graham, Bruce L. Rothschild et Joel H. Spencer, Ramsey Theory, Wiley-Interscience, , « 3.4 Finite Sums and Finite Unions (Folkman's Theorem) », p. 65-69
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Rado's theorem (Ramsey theory) » (voir la liste des auteurs).
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.