Twierdzenie Szemerédiego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 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,...,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[edytuj | edytuj kod]

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)[edytuj | edytuj kod]

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}} \leqslant N(k,d) \leqslant 2^{2^{d^{-2^{2^{k+9}}}}}

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

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

Przypisy