Twierdzenie Halesa-Jewetta

W matematyce twierdzenie Halesa-Jewetta jest podstawowym kombinatorycznym wynikiem teorii Ramseya, nazwanej na cześć Alfreda W. Halesa i Roberta I. Jewetta, dotyczącej stopnia, w jakim obiekty wielowymiarowe muszą koniecznie wykazywać jakąś kombinatoryczną strukturę; niemożliwe jest, aby takie obiekty były „całkowicie przypadkowe”.

Nieformalnym geometrycznym stwierdzeniem twierdzenia jest to, że dla dowolnych dodatnich liczb całkowitych n i c istnieje taka liczba H , że jeśli komórki H - wymiarowego sześcianu n × n × n × ... × n są pokolorowane c kolorami , to musi być jednym wierszem, kolumną lub określoną przekątną (więcej szczegółów poniżej) o długości n , której wszystkie komórki są tego samego koloru. Innymi słowy, wielowymiarowe, wieloosobowe uogólnienie gry typu n -w-rzędzie kółko i krzyżyk nie może zakończyć się remisem, bez względu na to, jak duże jest n , bez względu na to, ile osób gra c , i bez względu na to, który gracz gra w każdej turze, pod warunkiem, że jest rozgrywany na planszy o odpowiednio wysokim wymiarze H . Za pomocą standardowego argumentu kradzieży strategii można zatem wywnioskować, że jeśli dwóch graczy zmienia się, to pierwszy gracz ma zwycięską strategię, gdy H jest wystarczająco duże, chociaż nie jest znany żaden praktyczny algorytm uzyskania tej strategii.

Oświadczenie formalne

Linia kombinatoryczna w sześcianie

Niech W
H n będzie zbiorem słów o długości H nad alfabetem o n literach; to znaczy zbiór sekwencji {1, 2, ..., n } o długości H . Ten zestaw tworzy hipersześcian, który jest przedmiotem twierdzenia. Słowo zmienne w ( x ) nad W
H n nadal ma długość H , ale zawiera element specjalny x zamiast co najmniej jednej z liter. Słowa w (1), w (2), ..., w ( n ) otrzymane przez zastąpienie wszystkich wystąpień elementu specjalnego x przez 1, 2, ..., n , tworzą linię kombinatoryczną w przestrzeni W
H n ; linie kombinatoryczne odpowiadają rzędom, kolumnom i (niektórym) przekątnym hipersześcianu . Twierdzenie Halesa-Jewetta stwierdza następnie, że dla danych liczb całkowitych dodatnich n i c istnieje dodatnia liczba całkowita H , zależna od n i c , tak, że dla dowolnego podziału W
H n na c części istnieje co najmniej jedna część zawierająca całą linię kombinatoryczną.

Weźmy na przykład n = 3, H = 2 i c = 2. Hipersześcian W
H n w tym przypadku to po prostu standardowa tablica do gry w kółko i krzyżyk z dziewięcioma pozycjami:

11 12 13
21 22 23
31 32 33

Typową linią kombinatoryczną byłoby słowo 2x, które odpowiada linii 21, 22, 23; inną linią kombinatoryczną jest xx, która jest linią 11, 22, 33. (Zauważ, że linia 13, 22, 31, chociaż jest poprawna dla gry w kółko i krzyżyk , nie jest uważana za linię kombinatoryczną). w szczególnym przypadku twierdzenie Halesa-Jewetta nie ma zastosowania; planszę do gry w kółko i krzyżyk można podzielić na dwa zestawy, np. {11, 22, 23, 31} i {12, 13, 21, 32, 33}, z których żaden nie zawiera linii kombinatorycznej (i odpowiadałby do remisu w grze w kółko i krzyżyk ). Z drugiej strony, jeśli zwiększymy H do, powiedzmy, 8 (tak, że plansza jest teraz ośmiowymiarowa, z 3 8 = 6561 pozycjami) i podziel tę planszę na dwa zestawy („kółka” i „krzyżyki”), to jeden z tych dwóch zestawów musi zawierać linia kombinatoryczna (tj. w tym wariancie kółko i krzyżyk nie jest możliwy remis ). Aby uzyskać dowód, patrz poniżej.

Dowód twierdzenia Halesa-Jewetta (w szczególnym przypadku)

Udowodnimy teraz twierdzenie Halesa-Jewetta w szczególnym przypadku n = 3, c = 2, H = 8 omówionym powyżej. Chodzi o to, aby sprowadzić to zadanie do udowodnienia prostszych wersji twierdzenia Halesa-Jewetta (w tym konkretnym przypadku do przypadków n = 2, c = 2, H = 2 i n = 2, c = 6, H = 6). Ogólny przypadek twierdzenia Halesa-Jewetta można udowodnić podobnymi metodami, stosując indukcję matematyczną .

Każdy element hipersześcianu W 8
3 to ciąg ośmiu liczb od 1 do 3, np. 13211321 to element hipersześcianu. Zakładamy, że ten hipersześcian jest całkowicie wypełniony „kółkami” i „krzyżykami”. Zastosujemy dowód przez sprzeczność i założymy, że ani zbiór zer, ani zbiór krzyżyków nie zawiera linii kombinatorycznej. Jeśli ustalimy pierwsze sześć elementów takiego sznurka i pozwolimy, aby dwa ostatnie się zmieniały, otrzymamy zwykły kółko i krzyżyk tablica, na przykład „132113 ???” daje taką tablicę. Dla każdej takiej tablicy "abcdef???", rozważamy pozycje "abcdef11", "abcdef12", "abcdef22". Każdy z nich musi być wypełniony zerem lub krzyżykiem, więc zgodnie z zasadą przegródki dwa z nich muszą być wypełnione tym samym symbolem. Ponieważ dowolne dwie z tych pozycji są częścią linii kombinatorycznej, trzeci element tej linii musi być zajęty przez przeciwny symbol (ponieważ zakładamy, że żadna linia kombinatoryczna nie ma wszystkich trzech elementów wypełnionych tym samym symbolem). Innymi słowy, dla każdego wyboru „abcdef” (który można traktować jako element sześciowymiarowego hipersześcianu W
6 3 ), istnieje sześć (nakładających się) możliwości:

  1. abcdef11 i abcdef12 to zera; abcdef13 jest krzyżykiem.
  2. abcdef11 i abcdef22 to zera; abcdef33 to krzyż.
  3. abcdef12 i abcdef22 to zera; abcdef32 to krzyż.
  4. abcdef11 i abcdef12 to krzyżyki; abcdef13 to zero.
  5. abcdef11 i abcdef22 to krzyżyki; abcdef33 to zero.
  6. abcdef12 i abcdef22 to krzyżyki; abcdef32 to zero.

W ten sposób możemy podzielić sześciowymiarowy hipersześcian W
6 3 na sześć klas odpowiadających każdej z sześciu powyższych możliwości. (Jeżeli element abcdef spełnia wiele możliwości, możemy wybrać dowolny, np. wybierając najwyższy z powyższej listy).

Rozważmy teraz siedem elementów 111111, 111112, 111122, 111222, 112222, 122222, 222222 w W
6 3 . Zgodnie z zasadą przegródki dwa z tych elementów muszą należeć do tej samej klasy. Załóżmy na przykład, że 111112 i 112222 należą do klasy (5), więc 11111211, 11111222, 11222211, 11222222 to krzyżyki, a 11111233, 11222233 to zera. Ale teraz rozważmy pozycję 11333233, która musi być wypełniona krzyżykiem lub zerem. Jeśli jest ona wypełniona krzyżem, to linia kombinatoryczna 11xxx2xx jest w całości wypełniona krzyżami, co jest sprzeczne z naszą hipotezą. Jeśli zamiast tego jest wypełniony zerami, to linia kombinatoryczna 11xxx233 jest całkowicie wypełniona zerami, co ponownie zaprzecza naszej hipotezie. Podobnie, jeśli jakiekolwiek inne dwa z powyższych siedmiu elementów W
6 3 należą do tej samej klasy. Ponieważ we wszystkich przypadkach mamy sprzeczność, pierwotna hipoteza musi być fałszywa; zatem musi istnieć co najmniej jedna linia kombinatoryczna składająca się wyłącznie z zer lub wyłącznie z krzyżyków.

Powyższy argument był nieco marnotrawny; w rzeczywistości to samo twierdzenie odnosi się do H = 4. Jeśli rozszerzyć powyższy argument na ogólne wartości n i c , to H będzie rosło bardzo szybko; nawet gdy c = 2 (co odpowiada grze w kółko i krzyżyk dla dwóch graczy ) H podane w powyższym argumencie rośnie tak szybko, jak funkcja Ackermanna . Pierwsze prymitywne ograniczenie rekurencyjne wynika z Saharon Shelah i nadal jest ogólnie najlepiej znaną granicą dla liczby Halesa-Jewetta H = H ( n , c ).

Związki z innymi twierdzeniami

Zauważ, że powyższy argument daje również następujący wniosek: jeśli pozwolimy, że A będzie zbiorem wszystkich liczb ośmiocyfrowych, których wszystkie cyfry to 1, 2, 3 (stąd A zawiera liczby takie jak 11333233) i pokolorujemy A dwoma kolorów, to A zawiera co najmniej jeden ciąg arytmetyczny o długości trzech, którego wszystkie elementy są tego samego koloru. Dzieje się tak po prostu dlatego, że wszystkie linie kombinatoryczne występujące w powyższym dowodzie twierdzenia Halesa-Jewetta również tworzą ciągi arytmetyczne w notacji dziesiętnej . Bardziej ogólne sformułowanie tego argumentu może być użyte do wykazania, że ​​twierdzenie Halesa-Jewetta uogólnia twierdzenie van der Waerdena . Rzeczywiście twierdzenie Halesa-Jewetta jest zasadniczo silniejszym twierdzeniem.

Tak jak twierdzenie van der Waerdena ma mocniejszą wersję gęstości w twierdzeniu Szemerédiego , tak twierdzenie Halesa-Jewetta ma również wersję gęstości. W tej wzmocnionej wersji twierdzenia Halesa-Jewetta, zamiast kolorowania całego hipersześcianu W
H n na kolory c , otrzymuje się dowolny podzbiór A hipersześcianu W
H n o określonej gęstości 0 < δ < 1. Twierdzenie stwierdza że jeśli H jest wystarczająco duże w zależności od n i δ, to zbiór A musi koniecznie zawierać całą prostą kombinatoryczną.

Twierdzenie Halesa-Jewetta o gęstości zostało pierwotnie udowodnione przez Furstenberga i Katznelsona przy użyciu teorii ergodycznej . W 2009 roku w ramach projektu Polymath opracowano nowy dowód twierdzenia Halesa-Jewetta o gęstości, oparty na pomysłach z dowodu twierdzenia o rogach . Dodos, Kanellopoulos i Tyros przedstawili uproszczoną wersję dowodu Polymath.

Hales-Jewett jest uogólniony przez twierdzenie Grahama-Rothschilda o wielowymiarowych kostkach kombinatorycznych .

Zobacz też

  1. ^   Hales, Alfred W.; Jewett, Robert I. (1963). „Regularność i gry pozycyjne” . Trans. Amer. Matematyka soc. 106 (2): 222–229. doi : 10.1090/S0002-9947-1963-0143712-1 . MR 0143712 .
  2. Bibliografia   _ Tressler, Eric (2014). „Pierwsza nietrywialna liczba Halesa-Jewetta to cztery” (PDF) . Ars Combinatoria . 113 : 385–390. MR 3186481 .
  3. ^    Szela, Saharon (1988). „Prymitywne granice rekurencyjne dla liczb van der Waerdena” . J.Amer. Matematyka soc. 1 (3): 683–697. doi : 10.2307/1990952 . JSTOR 1990952 . MR 0929498 .
  4. ^    Fürstenberg, Hillel ; Katznelson, Icchak (1991). „Wersja gęstości twierdzenia Halesa-Jewetta” . Journal d'Analyse Mathématique . 57 (1): 64–119. doi : 10.1007/BF03041066 . MR 1191743 . S2CID 123036744 .
  5. ^   DHJ Polimat (2012). „Nowy dowód twierdzenia Halesa-Jewetta o gęstości” . Roczniki matematyki . 175 (3): 1283–1327. doi : 10.4007/annals.2012.175.3.6 . MR 2912706 .
  6. ^    Gowers, William Tymoteusz (2010). „Polymath i twierdzenie Halesa-Jewetta o gęstości”. W Bárány, Imre; Solymosi, József (red.). Nieregularny umysł . Studia matematyczne Towarzystwa Bolyai. Tom. 21. Budapeszt: Towarzystwo Matematyczne Jánosa Bolyai. s. 659–687. doi : 10.1007/978-3-642-14444-8_21 . ISBN 978-963-9453-14-2 . MR 2815619 .
  7. ^   Ajtai, Miklós; Szemeredi, Endre (1974). „Zestawy punktów sieci, które nie tworzą kwadratów”. Stadnina. nauka Matematyka węgierski . 9 : 9–11. MR 0369299 .
  8. ^   Dodos, Pandelis; Kanellopoulos, Wasilis; Tyros, Konstantinos (2014). „Prosty dowód twierdzenia Halesa-Jewetta o gęstości”. Int. Matematyka Rez. Nie. IMRN . 2014 (12): 3340–3352. ar Xiv : 1209.4986 . doi : 10.1093/imrn/rnt041 . MR 3217664 .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Hales–Jewett_theorem&oldid=1140136736 ”