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^[1], że dla dowolnej liczby ${\displaystyle 0<d<1}$ zwanej gęstością i dowolnej liczby naturalnej ${\displaystyle k}$ istnieje liczba ${\displaystyle N(d,k)}$ taka, że jeżeli ${\displaystyle N>N(d,k),}$ to dowolny podzbiór A zbioru ${\displaystyle \{1,\dots ,N\}}$ o liczebności większej od ${\displaystyle dN}$ zawiera ciąg arytmetyczny długości ${\displaystyle k.}$

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

Dowody

Przypadki ${\displaystyle k=1}$ i ${\displaystyle k=2}$ są trywialne. Przypadek ${\displaystyle k=3}$ został udowodniony w roku 1956 przez Klausa Rotha z wykorzystaniem metod analitycznych. Dla ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle N(k,d).}$ Najlepsze ze znanych oszacowań są następujące:

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

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

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

Przypisy