Відкрити головне меню

Зміни

Теорема Семереді вплинула не тільки на дискретну математику і адитивну теорію чисел, але й надихнула Хіллела Фюрстенберга на розробку нових напрямків ергодичної теорії. Фюрстенберг дав нове доведення теореми Семереді, створивши теорему кратного повернення в ергодичній теорії, тим самим несподівано встановивши зв'язок між задачами з області дискретної математики і [[теорія динамічних систем|теорією динамічних систем]]. Цей фундаментальний зв'язок привів в свою чергу до низки інших наукових досягнень, таких, як [[теорема Гріна—Тао]] про арифметичні прогресії будь-якої довжини в [[прості числа|простих числах]].
 
Семереді належать інші глибокі й важливі досягнення, що зробили великий вплив на розвиток таких областей математики, як дискретна математика та інформатика. З області дискретної математики можна привести такі приклади, як [[теорема Семереді—Семереді—Троттера]], напів-випадковий [[метод Айта—Комлоша—Семереді]], теорема про добуток Ердеша—Семереді і лема Балога—Семереді—Гауерса.
Троттера]], напів-випадковий [[метод Айта—Комлоша—Семереді]], теорема про добуток Ердеша—Семереді і лема Балога—Семереді—Гауерса.
 
Приклади з теорії інформатики включають в себе сортовану мережу Айта—Комлоша—Семереді, схему хешування Фрідмана—Комлоша—Семереді і теорему Пауля—Піппінгера—Семереді—Троттера, що розділяє детермінований і недетермінований лінійний час.