Янош Комлос (математик)

венгерско-американский математик

Янош Комлош (родился 23 мая 1942 года в Будапеште ) — венгерско-американский математик , работающий в области теории вероятностей и дискретной математики . С 1988 года он является профессором математики в Ратгерском университете ^[1]. Окончил Университет Этвеша Лоранда , затем стал научным сотрудником Математического института Венгерской академии наук . С 1984 по 1988 год он работал в Калифорнийском университете в Сан-Диего . ^[2]

Заметные результаты

• Теорема Комлоша : Он доказал, что каждая L 1 -ограниченная последовательность действительных функций содержит подпоследовательность, такую ​​что арифметические средние всех ее подпоследовательностей сходятся поточечно почти всюду . В вероятностной терминологии теорема выглядит следующим образом. Пусть ξ ₁ ,ξ ₂ ,... — последовательность случайных величин, такая что E [ξ ₁ ], E [ξ ₂ ],... ограничено. Тогда существуют подпоследовательность ξ' ₁ , ξ' ₂ ,... и случайная величина β, такие что для каждой дальнейшей подпоследовательности η ₁ ,η ₂ ,... из ξ' ₀ , ξ' ₁ ,... мы имеем (η ₁ +...+η _n )/n → β при .
• Совместно с Миклошем Айтаем и Эндре Семереди он доказал ^{[3] верхнюю} границу ct 2 /log t для числа Рамсея ^R ( 3 , t ) . Соответствующая нижняя граница была установлена ​​Чон Хан Кимом только в 1995 году, и этот результат принес ему премию Фулкерсона .

• Эта же группа авторов разработала оптимальную сортировочную сеть Айтая–Комлоша–Семереди . ^[4]
• Комлос и Семереди доказали, что если G — случайный граф на n вершинах с

${\displaystyle {\frac {1}{2}}n\log n+{\frac {1}{2}}n\log \log n+cn}$

ребра, где c — фиксированное действительное число, то вероятность того, что G имеет гамильтонов контур, сходится к

${\displaystyle e^{-e^{-2c}}.}$

• Совместно с Габором Шаркези и Эндре Семереди он доказал так называемую лемму о раздутии , которая утверждает, что регулярные пары в лемме Семереди о регулярности подобны полным двудольным графам при рассмотрении вложения графов с ограниченными степенями. ^[5]
• Комлос работал над проблемой Хейльбронна ; он, Янош Пинц и Семереди опровергли гипотезу Хейльбронна. ^[6]
• Комлош также написал часто цитируемые статьи о суммах случайных величин, ^[7] представлениях разреженных множеств с точки зрения экономии памяти, ^[8] случайных матрицах , ^[9] лемме Семереди о регулярности , [ ^10] и дерандомизации . ^[11]

Степени, награды

Комлос получил докторскую степень. в 1967 году из Университета Этвеша Лоранда под руководством Альфреда Реньи . ^[12] В 1975 году он получил премию Альфреда Реньи , премию, учрежденную для исследователей Института математики Альфреда Реньи . В 1998 году он был избран внешним членом Венгерской академии наук . ^[13]

Смотрите также

• Приближение Комлоша – Майора – Туснади

Ссылки

1. "Комлос, Янош".
2. История кафедры математики Калифорнийского университета в Сан-Диего. Архивировано 28 октября 2008 г. на Wayback Machine.
3. М. Айтай, Дж. Комлос, Э. Семереди: Примечание о числах Рамсея, Дж. Комбин. Теория Сер. А , 29 (1980), 354–360.
4. Айтай, Миклош ; Комлос, Янош; Семереди, Эндре (1983), «Сортировочная сеть O ( n  log  n )», Proc. 15-й симпозиум ACM по теории вычислений , стр. 1–9, doi : 10.1145/800061.808726, ISBN 0-89791-099-0, S2CID  15311122; Айтаи, Миклош ; Комлос, Янош; Семереди, Эндре (1983), «Сортировка в  журнале  n параллельных шагов», Combinatorica , 3 (1): 1–19, doi : 10.1007/BF02579338, S2CID  519246.
5. Дж. Комлос, Г. Саркози, Семереди: Лемма о разрушении, Combinatorica , 17 (1997), 109–123.
6. Комлос, Дж.; Пинц, Дж .; Семереди, Э. (1982), «Нижняя оценка проблемы Хейльбронна», Журнал Лондонского математического общества , 25 (1): 13–24, doi : 10.1112/jlms/s2-25.1.13
7. Комлош, Дж.; Майор, П.; Туснади, Г. (1975), «Аппроксимация частичных сумм независимых RV'-ов и выборочная функция распределения. I», Теория вероятностей и смежные области , 32 (1–2): 111–131, doi : 10.1007/BF00533093 , S2CID  8272486.
8. Фредман, Майкл Л .; Комлос, Янош; Семереди, Эндре (1984), «Хранение разреженной таблицы с временем доступа в наихудшем случае O (1)», Журнал ACM , 31 (3): 538, doi : 10.1145/828.1884 , S2CID  5399743. Предварительная версия появилась на 23-м симпозиуме по основам компьютерной науки , 1982, doi :10.1109/SFCS.1982.39.
9. Фюреди, Золтан ; Комлос, Янош (1981), «Собственные значения случайных симметричных матриц», Combinatorica , 1 (3): 233–241, doi : 10.1007/BF02579329, S2CID  7847476.
10. Комлос, Янош; Симоновиц, Миклош (1996), Лемма Семереди о регулярности и ее приложения в теории графов, Технический отчет: 96-10, DIMACS.
11. Айтай, Миклош ; Комлос, Янош; Семереди, Эндре (1987), «Детерминистическое моделирование в LOGSPACE», Proc. 19-й симпозиум ACM по теории вычислений , стр. 132–140, doi : 10.1145/28395.28410 , ISBN 0-89791-221-7, S2CID  15323404.
12. Янош Комлос в проекте «Математическая генеалогия» .
13. Математический факультет Ратгерского университета – Недавние награды преподавателей. Архивировано 18 декабря 2008 г. на Wayback Machine .