Twierdzenie Folkmana

Twierdzenie Folkmana jest twierdzeniem w matematyce, a dokładniej w kombinatoryce arytmetycznej i teorii Ramseya . Zgodnie z tym twierdzeniem, ilekroć liczby naturalne są podzielone na skończenie wiele podzbiorów, istnieją dowolnie duże zbiory liczb, których wszystkie sumy należą do tego samego podzbioru podziału. Twierdzenie to zostało odkryte i udowodnione niezależnie przez kilku matematyków, zanim zostało nazwane „twierdzeniem Folkmana” przez Grahama , Rothschilda i Spencera na pamiątkę Jona Folkmana .

Stwierdzenie twierdzenia

Niech N będzie zbiorem {1, 2, 3, ...} dodatnich liczb całkowitych i załóżmy, że N jest podzielone na k różnych podzbiorów N ₁ , N ₂ , ... N _k , gdzie k jest dowolną dodatnią liczbą całkowitą. _{_Następnie twierdzenie} Folkmana stwierdza, że dla każdej dodatniej liczby całkowitej m istnieje zbiór S _m i indeks i _m taki, że S _m ma m elementów i taki, że każda suma niepustego podzbioru S _m należy do Nim .

Związek z twierdzeniem Rado i twierdzeniem Schura

Twierdzenie Schura w teorii Ramseya stwierdza, że dla dowolnego skończonego podziału dodatnich liczb całkowitych istnieją trzy liczby x , y i x + y , które wszystkie należą do tego samego zbioru podziału. Oznacza to, że jest to szczególny przypadek m = 2 twierdzenia Folkmana.

Twierdzenie Rado w teorii Ramseya dotyczy podobnego sformułowania problemu, w którym liczby całkowite są podzielone na skończenie wiele podzbiorów; twierdzenie charakteryzuje macierze całkowite A tą właściwością, że można zagwarantować, że układ równań liniowych A x = 0 ma rozwiązanie, w którym każda współrzędna wektora rozwiązania x należy do tego samego podzbioru podziału. Mówimy, że układ równań jest regularny , gdy spełnia warunki twierdzenia Rado; Twierdzenie Folkmana jest równoważne 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, ..., m }.

Mnożenie a dodawanie

W twierdzeniu Folkmana możliwe jest zastąpienie dodawania przez mnożenie: jeśli liczby naturalne są skończenie podzielone, istnieją dowolnie duże zbiory S takie, że wszystkie iloczyny niepustych podzbiorów S należą do jednego zbioru podziału. Rzeczywiście, jeśli ograniczymy S do potęg dwóch , to wynik ten wynika bezpośrednio z addytywnej wersji twierdzenia Folkmana. Otwarte jest jednak, czy istnieją dowolnie duże zbiory, takie, że wszystkie sumy i wszystkie iloczyny niepustych podzbiorów należą do jednego zbioru partycji. Pierwszy przykład nieliniowości w teorii Ramseya, który nie składa się z jednomianów, podali niezależnie Furstenberg i Sarkozy w 1977 r., z rodziną { x , x + y 2 ^} , wynik, który został dodatkowo poprawiony przez Bergelsona w 1987 r. W 2016 r. , J. Moreira udowodnił, że istnieje zbiór postaci { x , x + y , xy } zawarty w elemencie podziału Nie wiadomo nawet, czy koniecznie musi istnieć zbiór postaci { x , y , x + y , xy } dla których wszystkie cztery elementy należą do tego samego zestawu partycji.

Kanoniczne twierdzenie Folkmana

Niech ${\ Displaystyle FS (\ {x_ {i} \} _ {i = 1} ^ {n})}$ oznacza zbiór wszystkich skończonych sum elementów ${\ Displaystyle \ {x_ {i} \} _ {i = 1} ^ {n}}$ . Niech $będzie$ (być może nieskończonym) kolorowaniem dodatnich liczb całkowitych i niech $dowolną$ liczbą całkowitą. Istnieje takie, że zachodzi co najmniej jeden z następujących 3 warunków. ${\ displaystyle \ {x_ {i} \} _ {i = 1} ^ {n}}$

1) ${\ Displaystyle FS (\ {x_ {i} \} _ {i = 1} ^ {n})}$ jest zbiorem monochromatycznym.

2) ${\ Displaystyle FS (\ {x_ {i} \} _ {i = 1} ^ {n})}$ to zestaw tęczy.

${\ Displaystyle \ suma _ {i \ w B$ ) Dla dowolnego koloru $b$ jest określony wyłącznie przez ${\ Displaystyle \ min (B)}$ .

Poprzednie wyniki

Warianty twierdzenia Folkmana zostały udowodnione przez Richarda Rado i JH Sandersa. Twierdzenie Folkmana zostało nazwane ku pamięci Jona Folkmana przez Ronalda Grahama , Bruce'a Lee Rothschilda i Joela Spencera w ich książce o teorii Ramseya .