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 c_i 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 C₁, C₂, ..., C_n telle que si ${\displaystyle s_{i}=\Sigma _{j\in C_{i}}c_{j}}$, alors

1. s₁ = 0
2. pour tout i ≥ 2, s_i peut être écrit comme une combinaison linéaire à coefficients rationnels[2] des colonnes c_j dont les indices j appartiennent à la réunion des C_k 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

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

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.