Янош Комлош ( Будапешт , 23 мая 1942 г.) - венгерско-американский математик , занимающийся теорией вероятностей и дискретной математикой . Он был профессором математики в Университете Рутгерса [1] с 1988 г. Окончил Этвеш Loránd университета , затем стал научным сотрудником в Математическом институте в Венгерской академии наук . С 1984 по 1988 год работал в Калифорнийском университете в Сан-Диего . [2]
Заметные результаты
- Он доказал, что каждая L 1 -ограниченная последовательность вещественных функций содержит такую подпоследовательность, что средние арифметические всех ее подпоследовательностей поточечно сходятся почти всюду . В вероятностной терминологии это следующая теорема. Пусть ξ 1 , ξ 2 , ... последовательность случайных величин такая, что E [ξ 1 ], E [ξ 2 ], ... ограничено. Тогда существуют подпоследовательность ξ ' 1 , ξ' 2 , ... и случайная величина β такие, что для каждой последующей подпоследовательности η 1 , η 2 , ... из ξ ' 0 , ξ' 1 , ... имеем (η 1 + ... + η n ) / n → β при .
- С Миклоша Ajtai и Семередите он доказал [3] кт 2 / войти т верхней границы для числа Ramsey R (3, т ). Соответствующая нижняя граница была установлена Чжон Хан Ким только в 1995 году, и этот результат принес ему премию Фулкерсона .
- Эта же группа авторов разработала оптимальную сортировочную сеть Айтай – Комлоша – Семереди . [4]
- Комлош и Семереди доказали, что если G - случайный граф на n вершинах с
- ребер, где c - фиксированное действительное число, то вероятность того, что G имеет гамильтонову схему, сходится к
- Вместе с Габором Шаркози и Эндре Семереди он доказал так называемую лемму о раздутии, которая утверждает, что регулярные пары в лемме Семереди о регулярности подобны полным двудольным графам при рассмотрении вложения графов с ограниченными степенями. [5]
- Комлос работал над проблемой Хейльбронна ; он, Янош Пинц и Семереди опровергли гипотезу Хейльбронна. [6]
- Комлоша также написала весьма цитируемые документы по суммам случайных величин, [7] пространство-эффективных представлений разреженных множеств, [8] случайные матриц , [9] регулярность леммы Семереди , [10] и derandomization . [11]
Дипломы, награды
Комлош получил докторскую степень. в 1967 году из Университета Этвеша Лоранда под руководством Альфреда Реньи . [12] В 1975 году он получил Премию Альфреда Реньи, премию , учрежденную для исследователей Математического института Альфреда Реньи . В 1998 году он был избран внешним членом Венгерской академии наук . [13]
Смотрите также
- Приближение Комлоша – Майора – Тушнади.
Рекомендации
- ^ Профиль факультета Рутгерса для Комлоша .
- ^ История отдела математики UCSD. Архивировано 28 октября 2008 г. в Wayback Machine.
- ^ M. Ajtai, J. Komlós, E. Szemerédi: Примечание о числах Рамсея, J. Combin. Теория Сер. А , 29 (1980), 354–360.
- ^ Айтай, Миклош ; Комлос, Янош; Семереди, Эндре (1983), " Сортировочная сеть O ( n log n )", Proc. 15-й симпозиум ACM по теории вычислений , стр. 1–9, doi : 10.1145 / 800061.808726; Айтай, Миклош ; Комлос, Янош; Семереди, Эндре (1983), «Сортировка в c log n параллельных шагов», Combinatorica , 3 (1): 1–19, doi : 10.1007 / BF02579338.
- ^ J. Комлоша, Г. Саркози, Семереди: Blow-Up Лемма, Combinatorica , 17 (1997), 109-123.
- ^ Komlós, J .; Pintz, J .; Семереди, E. (1982), "Нижняя граница для задачи Хейльбронна", журнал Лондонского математического общества , 25 (1): 13-24, DOI : 10.1112 / jlms / s2-25.1.13
- ^ Komlós, J .; Major, P .; Туснади, Г. (1975), "Приближение частных сумм независимых RV'-ов и выборки DF. I", Теория вероятностей и родственные поля , 32 (1–2): 111–131, doi : 10.1007 / BF00533093.
- ^ Фредман, Майкл Л .; Комлос, Янош; Семереди, Эндре (1984), "Сохранение разреженной таблицы с O (1) В худшем случае время доступа", Журнал ACM , 31 (3): 538, DOI : 10,1145 / 828,1884. Предварительная версия появилась на 23-м симпозиуме по основам информатики , 1982 г., DOI : 10.1109 / SFCS.1982.39 .
- ^ Фюреди, Золтан ; Комлоша, Янош (1981), "Собственные случайных симметричных матриц", Combinatorica , 1 (3): 233-241, DOI : 10.1007 / BF02579329.
- ^ Комлос, Янош; Симоновиц, Миклош (1996), Лемма Семереди о регулярности и ее приложения в теории графов , Технический отчет: 96-10, DIMACS.
- ^ Айтай, Миклош ; Комлос, Янош; Семереди, Эндре (1987), "Детерминированное моделирование в LOGSPACE", Proc. Девятнадцатый ACM симпозиум по теории вычислений ., Стр 132-140, DOI : 10,1145 / 28395,28410.
- ^ Джанос Комлос на Математической генеалогии .
- ^ Математический факультет Рутгерса - Последние награды факультета Архивировано 18 декабря 2008 г. в Wayback Machine .