Эндре Семереди ( венгерский: [ˈɛndrɛ ˈsɛmɛreːdi] ; родился 21 августа 1940 года) — венгерско-американский [1] математик и учёный-компьютерщик , работающий в области комбинаторики и теоретической информатики . С 1986 года он является профессором информатики в Университете Ратгерса . Он также имеет статус почётного профессора в Институте математики имени Альфреда Реньи Венгерской академии наук .
Семереди получил премии в области математики и естественных наук, в том числе Абелевскую премию в 2012 году. Он сделал ряд открытий в области комбинаторики и информатики, в том числе теорему Семереди , лемму о регулярности Семереди , теорему Эрдеша-Семереди , теорему Хайнала-Семереди и теорема Семереди –Троттера .
Семереди родился в Будапеште . Поскольку его родители хотели, чтобы он стал врачом, Семереди поступил в медицинский колледж, но бросил учёбу через шесть месяцев (в интервью [2] он объяснил это так: «Я не был уверен, что смогу выполнять работу, несущую такую ответственность»). [3] [4] [5] Он учился на факультете наук Университета Этвёша Лоранда в Будапеште и получил докторскую степень в Московском государственном университете . Его научным руководителем был Израиль Гельфанд . [6] Это произошло из-за опечатки, поскольку изначально Семереди хотел учиться у Александра Гельфонда . [3]
С 1986 года Семереди является профессором компьютерных наук в Ратгерском университете штата Нью-Джерси. Он занимал приглашенные должности в Стэнфордском университете (1974), Университете Макгилла (1980), Университете Южной Каролины (1981–1983) и Чикагском университете (1985–1986).
Эндре Семереди опубликовал более 200 научных статей в области дискретной математики, теоретической информатики, арифметической комбинаторики и дискретной геометрии. Он наиболее известен своим доказательством от 1975 года старой гипотезы Пола Эрдёша и Пала Турана : если последовательность натуральных чисел имеет положительную верхнюю плотность , то она содержит произвольно длинные арифметические прогрессии . Теперь это известно как теорема Семереди . Одна из лемм, введенных в его доказательстве, теперь известна как лемма о регулярности Семереди , которая стала важной леммой в комбинаторике , используемой, например, при тестировании свойств графов и в теории пределов графов .
Он также известен теоремой Семереди–Троттера в геометрии инцидентности и теоремой Хайнала–Семереди и проблемой Ружи–Семереди в теории графов . Миклош Айтай и Семереди доказали теорему об углах , важный шаг к многомерным обобщениям теоремы Семереди . Совместно с Айтаем и Яношем Комлошем он доказал верхнюю границу ct 2 /log t для числа Рамсея R (3, t ) и построил сортировочную сеть оптимальной глубины. Совместно с Айтаем, Вацлавом Хваталом и Монро М. Ньюборном Семереди доказал знаменитую лемму о пересечении, согласно которой граф с n вершинами и m ребрами, где m > 4 n , имеет не менее m 3 / 64 n 2 пересечений . С Полом Эрдёшем он доказал теорему Эрдёша–Семереди о числе сумм и произведений в конечном множестве. С Вольфгангом Полем, Ником Пиппенгером и Уильямом Троттером он установил разделение между недетерминированным линейным временем и детерминированным линейным временем [7] в духе печально известной проблемы P против NP .
Семереди получил множество наград и почестей за свой вклад в математику и информатику. Некоторые из них перечислены здесь:
Семереди является членом-корреспондентом (1982) и членом (1987) Венгерской академии наук и членом (2010) Национальной академии наук США . [18] Он был избран в Academia Europaea в 2022 году. [15] Он также является членом Института перспективных исследований в Принстоне, штат Нью-Джерси , и постоянным научным сотрудником Математического института Альфреда Реньи в Будапеште. Он был выдающимся стипендиатом Fairchild в Калифорнийском технологическом институте в 1987–1988 годах. Он является почетным доктором [19] Карлова университета в Праге. Он был лектором на Сорок седьмом ежегодном цикле лекций Делонга [20] в Университете Колорадо . Он также является получателем кафедры Айзенштадта в CRM, [21] Монреальском университете . В 2008 году он был профессором имени Эйзенбуда в Научно-исследовательском институте математических наук в Беркли, Калифорния .
В 2012 году Семереди был награжден премией Абеля «за его фундаментальный вклад в дискретную математику и теоретическую информатику, а также в знак признания глубокого и длительного влияния этих вкладов на аддитивную теорию чисел и эргодическую теорию » [22]. В награду за премию Абеля Семереди также отметили за то, что он вывел комбинаторику на центральное место в математике, и отметили его место в традиции венгерских математиков, таких как Джордж Пойа , который подчеркивал подход к решению задач в математике. [23] Семереди отреагировал на объявление, сказав, что «это не мое личное достижение, а признание этой области математики и венгерских математиков», что доставило ему наибольшее удовольствие. [24]
2–7 августа 2010 г. Институт математики Альфреда Реньи и Математическое общество Яноша Бойяи организовали конференцию в честь 70-летия Эндре Семереди. [25]
Перед конференцией был опубликован том серии «Бойяйское общество математических исследований» под названием «Нерегулярный ум» , сборник статей под редакцией Имре Барани и Йожефа Шоймоши , в честь достижений Семереди по случаю его 70-летия. [26] Еще одна конференция, посвященная чествованию работы Семереди, — Третья Абелевская конференция: Математическое празднование Эндре Семереди. [27]
Семереди женат на Анне Кепес; у них пятеро детей: Андреа, Анита, Питер, Кати и Жужи. [20] [28]
