Radosova věta (Ramseyova teorie) - Rados theorem (Ramsey theory) - Wikipedia

Radova věta je věta z oboru matematika známý jako Ramseyova teorie. Je pojmenován pro německého matematika Richard Rado. To bylo prokázáno v jeho práci, Studien zur Kombinatorik.

Prohlášení

Nechat ${ displaystyle A mathbf {x} = mathbf {0}}$ být soustavou lineárních rovnic, kde ${ displaystyle A}$ je matice s celočíselnými zápisy. Tento systém se říká, že je ${ displaystyle r}$-pravidelný pokud pro každého ${ displaystyle r}$-barvení přirozených čísel 1, 2, 3, ..., systém má monochromatické řešení. Systém je pravidelný Pokud to je r-pravidelný pro všechnyr ≥ 1.

Radova věta říká, že systém ${ displaystyle A mathbf {x} = mathbf {0}}$ je regulární, právě když je matice A uspokojuje podmínka sloupců. Nechat C_i označit i-tý sloupec A. Matice A splňuje podmínku sloupců za předpokladu, že existuje oddíl C₁, C₂, ..., C_n indexů sloupců tak, že pokud ${ displaystyle s_ {i} = Sigma _ {j v C_ {i}} c_ {j}}$, pak

1. s₁ = 0
2. pro všechny i ≥ 2, s_i lze psát jako racionální^[1] lineární kombinace C_j'je ve všech C_k s k < i. Tohle znamená tamto s_i je v lineárním podprostoru Q^m rozložený souborem C_jje.

Speciální případy

Folkmanova věta, tvrzení, že existují libovolně velké množiny celých čísel, jejichž všechny neprázdné součty jsou jednobarevné, lze považovat za zvláštní případ Radovy věty o zákonitosti soustavy rovnic

${ displaystyle x_ {T} = součet _ {i v T} x _ { {i }},}$

kde T rozsahy přes každou neprázdnou podmnožinu sady {1, 2, ..., X}.^[2]

Další speciální případy Radovy věty jsou Schurova věta a Van der Waerdenova věta. Pro prokázání první platí Radova věta na matici ${ displaystyle (1 1 {-1})}$. Pro Van der Waerdenovu větu s m je-li zvolena délka monochromatické aritmetické progrese, lze například uvažovat o následující matici:

${ 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)}$

Vyčíslitelnost

Vzhledem k systému lineárních rovnic je a priori nejasné, jak výpočetně ověřit, zda je pravidelný. Raduova věta naštěstí poskytuje kritérium, které je testovatelné v konečném čase. Místo uvažování o barvení (nekonečně mnoho přirozených čísel) je třeba zkontrolovat, zda daná matice splňuje podmínku sloupců. Protože matice se skládá pouze z konečně mnoha sloupců, lze tuto vlastnost ověřit v konečném čase.

Nicméně problém s podmnožinou může být snížena k problému výpočtu požadovaného oddílu C₁, C₂, ..., C_n sloupců: Vzhledem k vstupní sadě S pro problém součtu podmnožiny můžeme napsat prvky S v matici tvaru 1 × |S|. Pak prvky S odpovídající vektorům v oddílu C₁ součet na nulu. Problém s podmnožinou součtu je NP-kompletní. Ověření, že systém lineárních rovnic je pravidelný, je tedy také NP-úplný problém.

Reference