Folkmansova věta - Folkmans theorem - Wikipedia

Folkmanova věta je teorém v matematice a konkrétněji v aritmetická kombinatorika a Ramseyova teorie. Podle této věty, kdykoli přirozená čísla jsou rozdělené do konečně mnoha podskupin existují libovolně velké sady čísel, jejichž součty patří do stejné podmnožiny oddílu.^[1] Věta byla objevena a prokázána nezávisle několika matematiky,^[2][3] předtím to bylo pojmenováno "Folkmanova věta", jako památník Jon Folkman tím, že Graham, Rothschild, a Spencer.^[1]

Výrok věty

Nechat N být množinou {1, 2, 3, ...} kladných celých čísel a předpokládejme, že N je rozdělen na k různé podmnožiny N₁, N₂, ... N_k, kde k je jakékoli kladné celé číslo. Pak Folkmanova věta říká, že pro každé kladné celé číslo m, existuje sada S_m a index i_m takhle S_m má m prvky a takové, že každá suma neprázdné podmnožiny S_m patří N_im.^[1]

Vztah k Radově teorému a Schurově teorému

Schurova věta v Ramseyově teorii se uvádí, že pro každé konečné rozdělení kladných celých čísel existují tři čísla X, y, a X + y že všechny patří do stejné sady oddílů. To znamená, že se jedná o zvláštní případ m = 2 Folkmanovy věty.

Radova věta v Ramseyově teorii jde o podobný problémový výrok, ve kterém jsou celá čísla rozdělena na konečně mnoho podmnožin; věta charakterizuje celočíselné matice A s majetkem, který soustava lineárních rovnic A X = 0 může být zaručeno, že bude mít řešení, ve kterém bude každá souřadnice vektoru řešení X patří do stejné podmnožiny oddílu. Říká se, že systém rovnic je pravidelný kdykoli splňuje podmínky Radovy věty; Folkmanova věta je ekvivalentní pravidelnosti 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, ..., m}.^[1]

Násobení versus sčítání

Ve Folkmanově větě je možné nahradit sčítání násobením: pokud jsou přirozená čísla definitivně rozdělena, existují libovolně velké množiny S takové, že všechny produkty neprázdných podskupin S patří do jedné sady oddílů. Ve skutečnosti, pokud to někdo omezuje S sestávat pouze z pravomoci dvou, pak tento výsledek bezprostředně vyplývá z aditivní verze Folkmanovy věty. Je však otevřené, zda existují libovolně velké sady, takže všechny součty a všechny produkty neprázdných podmnožin patří do jedné sady oddílů. První příklad nelinearity v Ramseyově teorii, který nespočívá v monomiích, dali nezávisle Furstenberg a Sarkozy v roce 1977 s rodinou {X, X + y²}, výsledek, který Bergelson dále vylepšil v roce 1987. V roce 2016 J. Moreira prokázal, že existuje soubor formuláře {X, X + y, xy} obsažený v prvku oddílu^[4] Není však ani známo, zda nutně musí existovat sada formuláře {X, y, X + y, xy} pro které všechny čtyři prvky patří do stejné sady oddílů.^[1]

Kanonická lidová věta

Nechat ${ displaystyle FS ( {x_ {i} } _ {i = 1} ^ {n})}$ označit množinu všech konečných součtů prvků z ${ displaystyle {x_ {i} } _ {i = 1} ^ {n}}$. Nechat ${ displaystyle C}$ být (možná nekonečné) zbarvení kladných celých čísel a nechat ${ displaystyle n}$ být libovolné kladné celé číslo. Tady existuje ${ displaystyle {x_ {i} } _ {i = 1} ^ {n}}$ tak, aby platila alespoň jedna z následujících 3 podmínek.

1) ${ displaystyle FS ( {x_ {i} } _ {i = 1} ^ {n})}$ je monochromatická sada.

2) ${ displaystyle FS ( {x_ {i} } _ {i = 1} ^ {n})}$ je duhová sada.

3) Pro všechny ${ displaystyle B subseteq [1, n]}$, barva ${ displaystyle sum _ {i v B} x_ {i}}$ je určen pouze ${ displaystyle min (B)}$.

Předchozí výsledky

Varianty Folkmanovy věty byly prokázány Richard Rado a J. H. Sanders.^[2][3][1] Folkmanova věta byla pojmenována na památku Jon Folkman podle Ronald Graham, Bruce Lee Rothschild, a Joel Spencer, ve své knize o Ramseyova teorie.^[1]

Reference