Twierdzenie Szemerédiego

Twierdzenie Szemerédiego – udowodnione przez Endre Szemerédiego twierdzenie znane też jako przypuszczenie Erdősa-Turána. W roku 1936 Erdős i Turán wyrazili przypuszczenie, że dla dowolnej liczby $0<d<1$ zwanej gęstością i dowolnej liczby naturalnej $k$ istnieje liczba $N(d,k)$ taka, że jeżeli $N>N(d,k),$ to dowolny podzbiór A zbioru $\{1,\dots ,N\}$ o liczebności większej od $dN$ zawiera ciąg arytmetyczny długości $k.$

Jest to uogólnienie twierdzenia van der Waerdena z 1927 roku.

Dowody

Przypadki $k=1$ i $k=2$ są trywialne. Przypadek $k=3$ został udowodniony w roku 1956 przez Klausa Rotha z wykorzystaniem metod analitycznych. Dla $k=4$ odpowiedni dowód podał w roku 1969 Szemerédi; był to dowód kombinatoryczny. Korzystając z podobnych metod, jak Roth, Szemerédi podał kolejny dowód dla $k=4$ w roku 1972. W końcu, w roku 1975 Szemerédi udowodnił przypuszczenie Erdősa-Turána w całej ogólności.

Później znaleziono inne dowody twierdzenia: Hillel Furstenberg wykorzystał metody teorii ergodycznej (1977), natomiast Timothy Gowers (2001) posłużył się metodami analizy Fouriera i kombinatoryki.

Rząd wielkości N(k,d)

W związku ze sformułowaniem twierdzenia Szemerédiego powstaje pytanie o rząd wielkości liczby $N(k,d).$ Najlepsze ze znanych oszacowań są następujące:

$C^{\log (1/d{)}^{k-1}}⩽N(k,d)⩽2^{2^{d^{-2^{2^{k+9}}}}},$

gdzie $C>1.$ Dla $k=3$ górne oszacowanie daje się poprawić do

$N(3,d)⩽C^{d^{-2}\log (1/d)}.$