Twierdzenie Erdősa-Szekeresa
W matematyce twierdzenie Erdősa -Szekeresa stwierdza, że dla danego r , s dowolny ciąg różnych liczb rzeczywistych o długości co najmniej ( r - 1) ( s - 1) + 1 zawiera monotonicznie rosnący podciąg o długości r lub monotonicznie malejący podciąg o długości s . Dowód pojawił się w tym samym artykule z 1935 r., w którym wspomniano o problemie szczęśliwego zakończenia .
Jest to wynik skończony, który uściśla jeden z wniosków twierdzenia Ramseya . Podczas gdy twierdzenie Ramseya ułatwia udowodnienie, że każdy nieskończony ciąg różnych liczb rzeczywistych zawiera monotonicznie rosnący nieskończony podciąg lub monotonicznie malejący nieskończony podciąg, wynik udowodniony przez Paula Erdősa i George'a Szekeresa idzie dalej.
Przykład
Dla r = 3 i s = 2 wzór mówi nam, że każda permutacja trzech liczb ma rosnący podciąg o długości trzy lub malejący podciąg o długości dwa. Wśród sześciu permutacji liczb 1,2,3:
- 1,2,3 ma rosnący podciąg składający się ze wszystkich trzech liczb
- 1,3,2 ma malejący podciąg 3,2
- 2,1,3 ma malejący podciąg 2,1
- 2,3,1 ma dwa malejące podciągi, 2,1 i 3,1
- 3,1,2 ma dwa malejące podciągi, 3,1 i 3,2
- 3,2,1 ma trzy podciągi o malejącej długości-2, 3,2, 3,1 i 2,1.
Alternatywne interpretacje
Interpretacja geometryczna
Pozycje liczb w ciągu można interpretować jako współrzędne x punktów na płaszczyźnie euklidesowej , a same liczby jako współrzędne y ; odwrotnie, dla dowolnego punktu ustawionego na płaszczyźnie y punktów, uporządkowane według ich współrzędnych x , tworzą ciąg liczb (chyba że dwa punkty mają równe współrzędne x ). Dzięki tej translacji między sekwencjami i zbiorami punktów twierdzenie Erdősa – Szekeresa można zinterpretować jako stwierdzające, że w dowolnym zbiorze co najmniej rs - r - s + 2 punkty możemy znaleźć ścieżkę wielokątną o r - 1 krawędzie o dodatnim nachyleniu lub s − 1 krawędzi o ujemnym nachyleniu. W szczególności (biorąc r = s ), w dowolnym zbiorze co najmniej n punktów możemy znaleźć wielokątną ścieżkę o co najmniej ⌊ √ n -1 ⌋ krawędziach o nachyleniu tego samego znaku. Na przykład, przyjmując r = s = 5, każdy zestaw co najmniej 17 punktów ma czterokrawędziową ścieżkę, w której wszystkie nachylenia mają ten sam znak.
Przykład rs − r − s + 1 punktów bez takiej ścieżki, pokazujący, że ta granica jest ścisła, można utworzyć, stosując mały obrót siatki ( r − 1) na ( s − 1).
Interpretacja wzorca permutacji
Twierdzenie Erdősa-Szekeresa można również interpretować w języku wzorców permutacyjnych jako stwierdzające, że każda permutacja o długości co najmniej rs + 1 musi zawierać albo wzór 1, 2, 3, ..., r + 1 albo wzór s + 1, s , ..., 2, 1.
Dowody
Twierdzenie Erdősa – Szekeresa można udowodnić na kilka różnych sposobów; Steele (1995) analizuje sześć różnych dowodów twierdzenia Erdősa – Szekeresa, w tym dwa następujące. Inne dowody zbadane przez Steele obejmują oryginalne dowody Erdősa i Szekeresa, a także dowody Blackwella (1971) , Hammersleya (1972) i Lovásza (1979) .
Zasada przegródek
Biorąc pod uwagę ciąg o długości ( r − 1)( s − 1) + 1, oznacz każdą liczbę n i w ciągu parą ( a i , b i ), gdzie a i jest długością najdłuższego monotonicznie rosnącego podciągu kończącego się gdzie n i b i . jest długością najdłuższego monotonicznie malejącego podciągu kończącego się na n i Każde dwie liczby w ciągu są oznaczone inną parą: jeśli i < j oraz n i ≤ n j to a i < a j , a z drugiej strony jeśli n i ≥ n j to b i < b j . Ale są tylko ( r − 1) ( s − 1) możliwe etykiety tylko wtedy, gdy a i wynosi co najwyżej r − 1, a b i wynosi co najwyżej s − 1, więc zgodnie z zasadą przegródki musi istnieć wartość i , dla której a i lub b i jest poza tym zakresem. Jeśli a i jest poza zakresem, to n i jest częścią rosnącego ciągu o długości co najmniej r , a jeśli bi jest poza zakresem, to n i jest częścią malejącego ciągu o długości co najmniej s .
Steele (1995) przypisuje ten dowód jednostronicowemu artykułowi Seidenberga (1959) i nazywa go „najsprytniejszym i najbardziej systematycznym” z dowodów, które przegląda.
Twierdzenie Dilwortha
Inny dowód wykorzystuje twierdzenie Dilwortha o dekompozycjach łańcuchów w rzędach częściowych lub jego prostszą dualność ( twierdzenie Mirsky'ego ).
Aby udowodnić twierdzenie, zdefiniuj uporządkowanie częściowe elementów ciągu, w którym x jest mniejsze lub równe y w porządku częściowym, jeśli x ≤ y jako liczby i x nie jest późniejsze niż y w ciągu. Łańcuch w tym porządku częściowym jest podsekwencją rosnącą monotonicznie, a antyłańcuch jest podsekwencją malejącą monotonicznie. Zgodnie z twierdzeniem Mirsky'ego albo istnieje łańcuch o długości r , albo sekwencję można podzielić na co najwyżej r - 1 antyłańcuchów; ale w takim przypadku największy z antyłańcuchów musi tworzyć malejący podciąg o długości co najmniej
Alternatywnie, na podstawie samego twierdzenia Dilwortha, albo istnieje antyłańcuch o długości s , albo sekwencja może być podzielona na co najwyżej s - 1 łańcuchów, z których najdłuższy musi mieć długość co najmniej r .
Zastosowanie korespondencji Robinsona – Schensteda
Wynik można również uzyskać jako następstwo korespondencji Robinsona – Schensteda .
Przypomnijmy, że korespondencja Robinsona-Schensteda przypisuje każdej sekwencji tablicę Younga P , której wpisy są wartościami sekwencji. Tablica P ma następujące właściwości:
- Długość najdłuższego rosnącego podciągu jest równa długości pierwszego rzędu P .
- Długość najdłuższego malejącego podciągu jest równa długości pierwszej kolumny P .
Teraz nie jest możliwe zmieszczenie ( r − 1) ( s − 1) + 1 wpisów w kwadratowym pudełku o rozmiarze ( r − 1) ( s − 1), tak aby pierwszy wiersz miał długość co najmniej r lub ostatni rząd ma długość co najmniej s .