Twierdzenie Rado ( teoria Ramseya )

Twierdzenie Rado jest twierdzeniem z gałęzi matematyki znanej jako teoria Ramseya . Jej nazwa pochodzi od niemieckiego matematyka Richarda Rado . Udowodnił to w swojej pracy Studien zur Kombinatorik .

Oświadczenie

Niech $jest$ układem równań liniowych, gdzie $.$ całkowitymi Mówi się, że ten system jest -regularny $,$ dla każdego $liczb$ naturalnych 1, 2, 3, ..., system ma rozwiązanie monochromatyczne. System jest regularny , jeśli jest r-regularny dla wszystkich r ≥ 1.

$,$ że system jest regularny wtedy i tylko wtedy, gdy spełnia warunek kolumn . Niech c _i oznacza i -tą kolumnę A . Macierz A spełnia warunek kolumn pod warunkiem, że istnieje podział C ₁ , C ₂ , ..., C _n indeksów kolumn taki, że jeśli $\ Displaystyle s_ {i} = \ Sigma _ {j \ w C_ {i}} c_ {j}}$ , a następnie

s ₁ = 0
dla wszystkich i ≥ 2, s _i można zapisać jako wymierną kombinację we _. liniową cj wszystkich C _k z k < i Oznacza to, że s _i cj _jest w liniowej podprzestrzeni Q ^m rozpiętej przez zbiór .

Przypadki specjalne

Twierdzenie Folkmana , stwierdzenie, że istnieją dowolnie duże zbiory liczb całkowitych, których wszystkie niepuste sumy są monochromatyczne, może być postrzegane jako szczególny przypadek twierdzenia Rado dotyczącego regularności układu równań

{\ Displaystyle x_ {T} = \ suma _ {i \ w T} x_ {\ {i \}},}

gdzie T rozciąga się na każdy niepusty podzbiór zbioru {1, 2, ..., x }.

Inne szczególne przypadki twierdzenia Rado to twierdzenie Schura i twierdzenie Van der Waerdena . Aby udowodnić to pierwsze, zastosuj twierdzenie Rado do macierzy ${\ Displaystyle (1 \ 1 \ {-1})}$ . W przypadku twierdzenia Van der Waerdena, w którym m jest długością monochromatycznego ciągu arytmetycznego, można na przykład rozważyć następującą macierz:

${\ Displaystyle \ lewo ({\ rozpocząć {macierz} 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{macierz}}\right)}$

Obliczalność

Biorąc pod uwagę układ równań liniowych, nie jest a priori jasne, jak sprawdzić obliczeniowo, czy jest on regularny. Na szczęście twierdzenie Rado dostarcza kryterium sprawdzalnego w skończonym czasie. Zamiast brać pod uwagę kolorowania (nieskończenie wielu liczb naturalnych), należy sprawdzić, czy dana macierz spełnia warunek kolumn. Ponieważ macierz składa się tylko ze skończonej liczby kolumn, właściwość tę można zweryfikować w skończonym czasie.

Jednak problem sumy podzbioru można sprowadzić do problemu obliczenia wymaganego podziału kolumn C ₁ , C ₂ , ..., C _n : Mając zbiór wejściowy S dla problemu sumy podzbioru, możemy zapisać elementy S w macierz kształtu 1 × | S |. Wtedy elementy S odpowiadające wektorom w podziale C ₁ sumują się do zera. Problem sumy podzbioru jest NP-zupełny . Dlatego sprawdzenie, czy układ równań liniowych jest regularny, jest również problemem NP-zupełnym.

^ Nowoczesna teoria grafów autorstwa Béli Bollobása . 1. wyd. 1998. ISBN 978-0-387-98488-9 . Strona 204
^ Graham, Ronald L .; Rothschild, Bruce L .; Spencer, Joel H. (1980), „3.4 Sumy skończone i związki skończone (twierdzenie Folkmana)”, Ramsey Theory , Wiley-Interscience, s. 65–69 .

[1] Nowoczesna teoria grafów autorstwa Béli Bollobása . 1. wyd. 1998. ISBN 978-0-387-98488-9 . Strona 204

[grs-2] Graham, Ronald L .; Rothschild, Bruce L .; Spencer, Joel H. (1980), „3.4 Sumy skończone i związki skończone (twierdzenie Folkmana)”, Ramsey Theory , Wiley-Interscience, s. 65–69 .