Теорема Радо (теория Рамси)

---

Теорема Радо — это теорема из раздела математики , известного как теория Рамсея . Он назван в честь немецкого математика Рихарда Радо . Это было доказано в его диссертации Studien zur Kombinatorik .

Пусть - система линейных уравнений, где - матрица с целыми элементами. Эта система называется -регулярной , если для каждой -раскраски натуральных чисел 1, 2, 3,... система имеет одноцветное решение. Система называется регулярной , если она r-регулярна для всех  r  ≥ 1.${\ Displaystyle А \ mathbf {х} = \ mathbf {0}}$${\ Displaystyle А}$${\ Displaystyle г}$${\ Displaystyle г}$

Теорема Радо утверждает, что система является регулярной тогда и только тогда, когда матрица A удовлетворяет условию столбцов . Пусть c _i обозначает i - й столбец A . Матрица A удовлетворяет условию столбцов при условии, что существует разбиение C ₁ , C ₂ , ..., C _n индексов столбцов такое, что если , то${\ Displaystyle А \ mathbf {х} = \ mathbf {0}}$${\ displaystyle s_ {i} = \ Sigma _ {j \ in C_ {i}} c_ {j}}$

Теорема Фолкмана , утверждение о том, что существуют сколь угодно большие множества целых чисел, все непустые суммы которых являются одноцветными, может рассматриваться как частный случай теоремы Радо о регулярности системы уравнений.

Другими частными случаями теоремы Радо являются теорема Шура и теорема Ван дер Вардена . Для доказательства первого применима теорема Радо к матрице . Для теоремы Ван дер Вардена с m , выбранным как длина монохроматической арифметической прогрессии, можно, например, рассмотреть следующую матрицу:${\ Displaystyle (1 \ 1 \ {-1})}$

---