Twierdzenie Szemerédiego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 zwanej gęstością i dowolnej liczby naturalnej k istnieje liczba taka, że jeżeli , 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]

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]

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

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

Przypisy