Теорема Радоса (теория Рамсея) - Rados theorem (Ramsey theory) - Wikipedia

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

Заявление

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

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

1. s₁ = 0
2. для всех я ≥ 2, s_я можно записать как рациональное^[1] линейная комбинация c_j'во всех C_k с k < я. Это означает, что s_я находится в линейном подпространстве Q^м охватывается множеством c_jс.

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

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

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

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

Другие частные случаи теоремы Радо: Теорема Шура и Теорема Ван дер Вардена. Для доказательства первого применим теорему Радо к матрице ${\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_п столбцов: учитывая входной набор S для задачи о сумме подмножеств мы можем записать элементы S в матрице формы 1 × |S|, Тогда элементы S соответствующие векторам в разбиении C₁ сумма к нулю. Проблема суммы подмножества НП-полный. Следовательно, проверка регулярности системы линейных уравнений также является NP-полной задачей.

Рекомендации

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