Ендре Семереді

Ендре Семереді (угор. Endre Szemerédi; 21 серпня 1940(19400821)) — угорський математик, який працює в областях комбінаторики та теоретичних комп'ютерних наук.

Ендре Семереді народився в 1940 році в Будапешті. Закінчивши Будапештський університет, в 1970 році він захистив дисертацію в Московському державному університеті імені Ломоносова (науковий керівник — Ізраїль Гельфанд). Семереді — постійний науковий співробітник Математичного інституту Альфреда Реньї Угорської академії наук. Крім того, він займає посаду професора інформатики в Рутгерському університеті в Нью-Джерсі.

Внесок у науку

Ендре Семереді зробив значний внесок у дискретну математику, створивши оригінальні нові методи, а також вирішивши багато фундаментальних проблем. Його праці звели комбінаторику на центральну сцену математики, виявивши глибокі зв'язки з такими розділами, як адитивна теорія чисел, ергодична теорія, інформатика та геометрія інцидентних структур.

У 1975 Ендре Семереді вперше привернув увагу багатьох математиків своїм доказом знаменитої гіпотези Ердеша—Турана, яка стверджує, що будь-яка підмножина цілих чисел, що має позитивну щільність, містить арифметичні прогресії будь-якої довжини. Це було несподіваним, тому що навіть випадки з прогресіями довжини 3 або 4 раніше вимагали суттєвих зусиль з боку Клауса Рота і самого Семереді.

Доказ Семереді був шедевром комбінаторного мислення, і був відразу ж визнаний винятково глибоким і значним. Ключовим кроком у доказі, відомому як лема про регулярне розбитті або лема регулярності Семереді (Szemeredi's regularity lemma), є структурна класифікація великих графів. Ця лема стала на сьогоднішній день найважливішим інструментом і теорії графів, та інформатики, що дозволяє вирішувати складні завдання перевірки властивостей, і стала також джерелом теорії меж графа.

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

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

Приклади з теорії інформатики включають в себе сортована мережа Айта—Комлоша—Семереді, схему хешування Фрідмана—Комлоша—Семереді і теорему Пауля—Піппінгера—Семереді—Троттера, що розділяє детерминістський і недетерміністський лінійний час.