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 przypuszczenieArtykuł: http://web.archive.org/web/20090718043620/http://www.renyi.hu/~p_erdos/1936-05.pdf, że dla dowolnej liczby zwanej gęstością i dowolnej liczby naturalnej istnieje liczba taka, że jeżeli to dowolny podzbiór A zbioru o liczebności większej od zawiera ciąg arytmetyczny długości
Jest to uogólnienie twierdzenia van der Waerdena z 1927 roku.
Dowody Przypadki i są trywialne. Przypadek został udowodniony w roku 1956 przez Klausa Rotha z wykorzystaniem metod analitycznych. Dla 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 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 Najlepsze ze znanych oszacowań są następujące:
gdzie Dla górne oszacowanie daje się poprawić do
Przypisy
Kategoria:Twierdzenia kombinatoryki Kategoria:Twierdzenia teorii liczb