Szemerédiho věta

Szemerédiho věta je tvrzení z oboru teorie čísel, které potvrzuje Erdősovu-Turánovu domněnku z roku 1936. Pál Erdős a Paul Turán vyslovili hypotézu, že pro každé přirozené číslo k a reálné číslo d, 0n_0, že pro všechna n\ge n_0 každá podmnožina {1,2,\dots,n} mohutnosti alespoň dn obsahuje k-prvkovou aritmetickou posloupnost. Jako větu tvrzení dokázal v roce 1975 Endre Szemerédi, který již předtím v roce 1969 publikoval důkaz pro k = 4. Předtím existoval důkaz pro k=3 z roku 1953 od Klause Rotha (případy k=1,2 mají důkaz triviální).

Szemerédiho větu se později podařilo dokázat několika dalšími metodami, jeden z alternativních důkazů publikoval v roce 1977 Hilel Fürstenberg, další v roce 2001 Timothy Gowers.

Tvrzení lze vyslovit také tak, že každá podmnožina přirozených čísel s nenulovou horní asymptotickou hustotou obsahuje konečné aritmetické posloupnosti libovolné délky.

Jedná se o zobecnění van der Waerdenovy věty, naopak Greenova-Taova věta představuje silnější tvrzení pro speciální případ množiny prvočísel (ta má asymptotickou hustotu nulovou a samotná Szemerédiho věta se na ni tedy nevztahuje).

Reference

Kategorie:Kombinatorika Kategorie:Ramseyovská teorie Kategorie:Matematické věty a důkazy