Андраш Хайнал - András Hajnal - Wikipedia

Для венгерского олимпийского дайвера см. Андраш Хайнал (ныряльщик).

Андраш Хайнал (13 мая 1931 г. - 30 июля 2016 г.[1][2]) был профессором математики в Университет Рутгерса[3] и член Венгерская Академия Наук[4] известен своей работой в теория множеств и комбинаторика.

биография

Хайнал родился 13 мая 1931 года,[5] в Будапешт, Венгрия.

Он получил университетский диплом (степень магистра) в 1953 г. Университет Этвёша Лоранда,[6] его Кандидат степени математических наук (примерно эквивалент доктора философии) в 1957 году под руководством Ласло Калмар,[7] и степень доктора математических наук в 1962 году. С 1956 по 1995 год он был преподавателем в Университет Этвёша Лоранда; в 1994 году он перешел в университет Рутгерса, где стал директором DIMACS, и он оставался там профессором до выхода на пенсию в 2004 году.[5] Он стал членом Венгерской академии наук в 1982 году и руководил ее математический институт с 1982 по 1992 гг.[5] Он был генеральным секретарем Математическое общество Яноша Бойяи с 1980 по 1990 год, а с 1990 по 1994 президент общества.[5] С 1981 г. - редактор-консультант журнала. Комбинаторика. Хайнал также был одним из почетных президентов Европейского общества теории множеств.

Хайнал был заядлым шахматы игрок.[8]

Хайнал был отцом Питер Хайнал, помощник декана Европейский колледж свободных искусств.

Исследования и публикации

Хайнал был автором более 150 публикаций.[9] Среди множества соавторов Пол Эрдёш, у него было второе место по количеству совместных работ - 56.[10]Вместе с Питером Гамбургером он написал учебник, Теория множеств (Издательство Кембриджского университета, 1999 г., ISBN  0-521-59667-X). Некоторые из его наиболее цитируемых научных работ[11] включают

  • Бумага о сложность схемы с Маасом, Пудлаком, Сегеди, и Дьёрдь Туран,[12] показаны экспоненциальные нижние границы размера схем ограниченной глубины с взвешенными большинство вентили, которые решают задачу вычисления паритет из внутренние продукты.
  • В Теорема Хайнала – Семереди на справедливая окраска, доказывая гипотезу Эрдеша 1964 года:[13] пусть Δ обозначает максимальную степень вершины в конечном графе грамм. потом грамм возможно цветной с Δ + 1 цветами таким образом, что размеры цветовых классов отличаются не более чем на единицу. Несколько авторов впоследствии опубликовали упрощения и обобщения этого результата.[14]
  • Статья с Эрдёшем и Дж. У. Муном о графиках, которые не имеют k-клики. Теорема Турана характеризует графы этого типа с максимальным количеством ребер; Эрдеш, Хайнал и Мун находят похожую характеристику самых маленьких максимальный k-безкликовых графиков, показывающих, что они принимают форму определенных разделить графики. В этой статье также доказана гипотеза Эрдеша и Галлай от количества ребер в критический граф за господство.[15]
  • Бумага с Эрдёшем на раскраска графика задачи для бесконечных графов и гиперграфы.[16] Эта статья расширяет жадная окраска методы от конечных графов к бесконечным: если вершины графа можно упорядочить так, чтобы каждая вершина имела несколько предыдущих соседей, она имеет низкое хроматическое число. Когда каждый конечный подграф имеет упорядочение этого типа, в котором количество предыдущих соседей не превышает k (то есть это k-вырожденный ) бесконечный граф имеет хороший порядок с не более чем 2k - 2 предыдущих соседа на вершину. В статье также доказывается отсутствие бесконечных графов с высокими конечными обхват и достаточно большое бесконечное хроматическое число и существование графов с большим нечетным обхватом и бесконечным хроматическим числом.

Другие выбранные результаты включают:

  • В его диссертации[17] он представил модели L(А) (видеть относительная конструктивность ), и доказал, что если κ является обычный кардинал и А является подмножеством κ+, затем ZFC и 2κ = κ+ держать в L(А). Это можно применить для доказательства результатов относительной согласованности: например, если 2ℵ0 = ℵ2 непротиворечиво, то 2ℵ0 = ℵ2 и 2ℵ1 = ℵ2.
  • Теорема Хайнала об отображении множеств, решение гипотезы Станислав Рузевич.[18] Эта работа касается функций ƒ, которые отображают элементы бесконечного множества S к небольшим подмножествам S; более конкретно, мощности всех подмножеств должны быть меньше некоторой верхней границы, которая сама по себе меньше мощности S. Хайнал показывает, что S должен иметь равномерный подмножество, в котором нет пары элементов Икс и у имеют Икс в ƒ (у) или же у в ƒ (Икс). Этот результат значительно расширяет возможности п = 1 из Теорема Куратовского о свободном множестве, который утверждает, что когда ƒ отображает несчетное множество в конечные подмножества, существует пара Икс, у ни один из них не принадлежит образу другого.
  • Пример двух графиков, каждый с бесчисленным хроматическим числом, но со счетным хроматическим прямым произведением.[19] То есть, Гипотеза Хедетниеми не работает для бесконечных графов.
  • В статье[20] с Пол Эрдёш он доказал несколько результатов о системах бесконечных множеств, имеющих свойство B.
  • Бумага с Фред Гэлвин в котором[21] они доказали, что если это сильный предел кардинала тогда
Это был результат, который положил начало Шела с теория pcf.

Награды и отличия

В 1992 году Хайнал был награжден Офицерским крестом ордена Венгерской Республики.[5] В 1999 г. конференция в честь его 70-летия прошла в г. DIMACS,[25] и вторая конференция, посвященная 70-летию со дня рождения Хайнала и Вера Сос состоялась в 2001 г. Будапешт.[26] Хайнал стал членом Американское математическое общество[27] в 2012.

Рекомендации

  1. ^ Объявление от института Реньи
  2. ^ Вспоминая Андраша Хайнала (1931-2016)
  3. ^ Математический факультет Университета Рутгерса - Почетный факультет В архиве 2010-07-15 на Wayback Machine.
  4. ^ Венгерская академия наук, отделение математики В архиве 11 марта 2009 г. Wayback Machine.
  5. ^ а б c d е Биография Резюме.
  6. ^ Halmazelmélet huszadik századi "Hajnal A", Интервью М. Стрехо с А. Х., Мадьяр Тудомани, 2001.
  7. ^ Андраш Хайнал на Проект "Математическая генеалогия". Дата 1957 года взята из резюме Хайнала; на сайте генеалогии математиков указана дата защиты доктора Хайнала. как 1956 год.
  8. ^ Объявление В архиве 2008-07-24 на Wayback Machine на конференции 2001 г. в честь Хайнала и Сош называет его «великим шахматистом»; В рамках конференции в его честь прошел турнир по блиц-шахматам.
  9. ^ Список публикаций В архиве 16 июля 2010 г. Wayback Machine с веб-сайта Хайнала.
  10. ^ Список сотрудников Эрдеша по количеству совместных работ, с веб-сайта проекта числа Эрдёша.
  11. ^ Согласно подсчету цитирования ученого Google, полученному 1 марта 2009 г.
  12. ^ Hajnal, A .; Maass, W .; Pudlak, P .; Szegedy, M .; Turán, G. (1987), "Пороговые схемы ограниченной глубины", Proc. 28-й симпозиум Основы компьютерных наук (FOCS 1987), стр. 99–110, Дои:10.1109 / SFCS.1987.59
  13. ^ Hajnal, A .; Семереди, Э. (1970), «Доказательство гипотезы П. Эрдеша», Комбинаторная теория и ее приложения, II (Proc. Colloq., Balatonfüred, 1969), Северная Голландия, стр. 601–623, МИСТЕР  0297607
  14. ^ Катлин, Пол А. (1980), "О теореме Хайнала – Семереди о непересекающихся кликах", Utilitas Mathematica, 17: 163–177, МИСТЕР  0583138; Фишер, Эльдар (1999), "Варианты теоремы Хайнала – Семереди", Журнал теории графов, 31 (4): 275–282, Дои:10.1002 / (SICI) 1097-0118 (199908) 31: 4 <275 :: AID-JGT2> 3.0.CO; 2-F, МИСТЕР  1698745; Kierstead, H.A .; Косточка, А. В. (2008), "Краткое доказательство теоремы Хайнала – Семереди о справедливой раскраске", Комбинаторика, теория вероятностей и вычисления, 17 (2): 265–270, CiteSeerX  10.1.1.86.4139, Дои:10.1017 / S0963548307008619, МИСТЕР  2396352; Мартин, Райан; Семереди, Эндре (2008), "Четырехчастная версия теоремы Хайнала – Семереди", Дискретная математика, 308 (19): 4337–4360, Дои:10.1016 / j.disc.2007.08.019, МИСТЕР  2433861
  15. ^ Эрдеш, П.; Hajnal, A .; Мун, Дж. У. (1964), «Проблема теории графов» (PDF), Американский математический ежемесячный журнал, Математическая ассоциация Америки, 71 (10): 1107–1110, Дои:10.2307/2311408, JSTOR  2311408, МИСТЕР  0170339
  16. ^ Эрдеш, П.; Хайнал, А. (1966), "О хроматическом числе графов и систем множеств", Acta Mathematica Hungarica, 17 (1–2): 61–99, Дои:10.1007 / BF02020444, МИСТЕР  0193025
  17. ^ Хайнал, А. (1961), "О теореме совместимости, связанной с обобщенной проблемой континуума", Acta Math. Акад. Sci. Подвешенный., 12 (3–4): 321–376, Дои:10.1007 / BF02023921, МИСТЕР  0150046
  18. ^ Хайнал, А. (1961–1962), "Доказательство гипотезы С. Рузевича", Фонд. Математика., 50: 123–128, Дои:10.4064 / FM-50-2-123-128, МИСТЕР  0131986
  19. ^ Хайнал, А. (1985), "Хроматическое число произведения двух ℵ1 хроматические графы можно исчислить », Комбинаторика, 5 (2): 137–140, Дои:10.1007 / BF02579376, МИСТЕР  0815579.
  20. ^ П. Эрдеш, А. Хайнал: Об одном свойстве семейств множеств, Acta Math. Акад. Sci. Подвешенный.., 12(1961), 87–123.
  21. ^ Гальвин, Ф.; Хайнал, А. (1975), "Неравенства для кардинальных степеней", Анналы математики, Вторая серия, 101 (3): 491–498, Дои:10.2307/1970936, JSTOR  1970936
  22. ^ Baumgartner, J .; Хайнал, А. (1973), "Доказательство (с использованием аксиомы Мартина) отношения разбиения", Fundamenta Mathematicae, 78 (3): 193–203, Дои:10.4064 / fm-78-3-193-203, МИСТЕР  0319768. Дополнительные результаты Баумгартнера и Хайнала о соотношениях разбиения см. В следующих двух статьях: Baumgartner, J. E .; Хайнал А. (1987), "Замечание об отношениях разбиения для бесконечных ординалов в приложении к конечной комбинаторике", Логика и комбинаторика (Арката, Калифорния, 1985), Contemp. Математика, 65, Провиденс, Род-Айленд: амер. Математика. Soc., Стр. 157–167, Дои:10.1090 / conm / 065/891246, МИСТЕР  0891246; Баумгартнер, Джеймс Э .; Хайнал, Андраш (2001), «Поляризованные отношения разделения», Журнал символической логики, Ассоциация символической логики, 66 (2): 811–821, Дои:10.2307/2695046, JSTOR  2695046, МИСТЕР  1833480
  23. ^ Бригадир, М .; Хайнал, А. (2003). «Отношение разделения для наследников больших кардиналов». Математика. Анна. 325: 583–623. Дои:10.1007 / s00208-002-0323-7.
  24. ^ А. Хайнал, И. Юхас: Об наследственно α-линделёфских и наследственно α-сепарабельных пространствах, Анна. Univ. Sci. Будапешт. Eötvös Sect. Математика., 11(1968), 115–124.
  25. ^ Томас, Саймон, изд. (1999), Теория множеств: Хайнальная конференция, 15–17 октября 1999 г. Центр DIMACS, Серия DIMACS по дискретной математике и теоретической информатике, 58, Американское математическое общество, ISBN  978-0-8218-2786-4
  26. ^ Дьёри, Эрвин; Катона, Дьюла О.; Ловас, Ласло, ред. (2006), Еще наборы, графики и числа: привет Вере Сош и Андрашу Хайналу, Математические исследования Общества Бойяи, 15, Springer-Verlag, ISBN  978-3-540-32377-8
  27. ^ Список членов Американского математического общества

внешняя ссылка