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 N1, N2, ... Nk, kde k je jakékoli kladné celé číslo. Pak Folkmanova věta říká, že pro každé kladné celé číslo m, existuje sada Sm a index im takhle Sm má m prvky a takové, že každá suma neprázdné podmnožiny Sm patří Nim.[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
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 + y2}, 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 označit množinu všech konečných součtů prvků z . Nechat být (možná nekonečné) zbarvení kladných celých čísel a nechat být libovolné kladné celé číslo. Tady existuje tak, aby platila alespoň jedna z následujících 3 podmínek.
1) je monochromatická sada.
2) je duhová sada.
3) Pro všechny , barva je určen pouze .
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
- ^ A b C d E F G Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980), „3.4 Konečné součty a konečné odbory (Folkmanova věta)“, Ramseyova teorie, Wiley-Interscience, str. 65–69.
- ^ A b Rado, R. (1970), "Některé věty o rozdělení", Kombinatorická teorie a její aplikace, III: Proc. Colloq., Balatonfüred, 1969, Amsterdam: Severní Holandsko, s. 929–936, PAN 0297585.
- ^ A b Sanders, Jon Henry (1968), Zobecnění Schurovy věty, Ph.D. diplomová práce, Yale University, PAN 2617864.
- ^ Moreira, J. (2017), „Monochromatické částky a produkty v N", Annals of Mathematics, SECOND SERIES, sv. 185, č. 3, Evanston: Katedra matematiky, Princetonská univerzita, s. 1069–1090, PAN 3664819.