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

Математический результат по системам линейных уравнений

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

Заявление

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

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

1. с ₁ = 0
2. для всех i  ≥ 2, s _i можно записать как рациональную ^[1] линейную комбинацию c _j ' во всех C _k с k  <  i . Это означает, что s _i находится в линейном подпространстве Q ^{m ,} охватываемом множеством c _j ' .

Особые случаи

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

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

где T пробегает каждое непустое подмножество множества {1, 2, ..., x }. ^[2]

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

${\displaystyle \left({\begin{matrix}1&1&-1&0&\cdots &0&0\\1&2&0&-1&\cdots &0&0\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&m-1&0&0&\cdots &-1&0\\1&m&0&0&\cdots &0&-1\end{matrix}}\right)}$

Вычислимость

Если задана система линейных уравнений, то априори неясно, как проверить вычислительно, что она регулярна. К счастью, теорема Радо дает критерий, который можно проверить за конечное время. Вместо того чтобы рассматривать раскраски (бесконечного числа натуральных чисел), нужно проверить, что заданная матрица удовлетворяет условию столбцов. Поскольку матрица состоит только из конечного числа столбцов, это свойство можно проверить за конечное время.

Однако задачу суммы подмножества можно свести к задаче вычисления требуемого разбиения C ₁ , C ₂ , ..., C _n столбцов: Имея входной набор S для задачи суммы подмножества, мы можем записать элементы S в матрицу формы 1 × | S |. Тогда элементы S, соответствующие векторам в разбиении C _{1 ,} в сумме дают ноль. Задача суммы подмножества является NP-полной . Следовательно, проверка того, что система линейных уравнений является регулярной, также является NP-полной задачей.

Ссылки

1. Современная теория графов Белы Боллобаса . 1-е изд. 1998. ISBN  978-0-387-98488-9 . Страница 204
2. Грэм, Рональд Л.; Ротшильд , Брюс Л .; Спенсер, Джоэл Х. (1980), «3.4 Конечные суммы и конечные объединения (теорема Фолкмана)», Теория Рамсея , Wiley-Interscience, стр. 65–69.