Андраш Хайнал - András Hajnal
Андраш Хайнал (13 мая 1931 - 30 июля 2016) был профессором математики в Университете Рутгерса и членом Венгерской академии наук, известным своими работами в области теории множеств и комбинаторики .
биография
Хайнал родился 13 мая 1931 года в Будапеште , Венгрия .
Он получил университетский диплом (степень магистра наук) в 1953 году в Университете Этвёша Лоранда , степень кандидата математических наук (примерно эквивалентную докторской степени) в 1957 году под руководством Ласло Калмара и его доктора математических наук. В 1962 году получил ученую степень. С 1956 по 1995 год он был преподавателем в Университете Этвеша Лоранда ; в 1994 году он перешел в университет Рутгерса, чтобы стать директором DIMACS , и оставался там профессором до выхода на пенсию в 2004 году. Он стал членом Венгерской академии наук в 1982 году и руководил ее математическим институтом с 1982 по 1992 год. Он был генеральным секретарем математического общества Яноша Бойяи с 1980 по 1990 год и президентом общества с 1990 по 1994 год. С 1981 года он был редактором-консультантом журнала Combinatorica . Хайнал был также одним из почетных президентов Европейского общества теории множеств.
Хайнал был заядлым шахматистом .
Хайнал был отцом Питера Хайнала , со-декана Европейского колледжа свободных искусств .
Исследования и публикации
Хайнал был автором более 150 публикаций. Среди многих соавторов Пола Эрдеша у него было второе место по количеству совместных статей - 56. Вместе с Питером Гамбургером он написал учебник « Теория множеств» (Cambridge University Press, 1999, ISBN 0-521-59667-X ). Некоторые из его наиболее цитируемых исследовательских работ включают:
- Документ по цепи сложности с Maas, Pudlak, Szegedy , и György Турана, показывающий экспоненциальные нижние оценки размера ограниченных глубинных схем с весовыми большинства ворот, решающих задачу вычисления четности из внутренних продуктов .
- Теорема Hajnal-Семередите на равноправной раскраске , доказав 1964 гипотезы Эрдеша: пусть Δ обозначает максимальную степень вершины в конечном графе G . Тогда G можно раскрасить в Δ + 1 цвет так, чтобы размеры цветовых классов отличались не более чем на единицу. Некоторые авторы впоследствии опубликовали упрощения и обобщения этого результата.
- Бумага с Эрдешем и JW Луной на графиках , которые избегают имеющих любую K - клики . Теорема Турана характеризует графы этого типа с максимальным числом ребер; Эрдеш, Хайнал и Мун находят аналогичную характеристику наименьших максимальных k -свободных графов, показывая, что они принимают форму определенных расщепленных графов . Эта статья также доказывает гипотезу Эрдеша и Галлаи о количестве ребер в критическом графе для доминирования .
- Статья с Эрдешем о задачах раскраски графов для бесконечных графов и гиперграфов . В этой статье методы жадной раскраски расширяются с конечных графов до бесконечных: если вершины графа могут быть упорядочены так, чтобы каждая вершина имела несколько предыдущих соседей, она имеет низкое хроматическое число. Когда каждый конечный подграф имеет порядок этого типа, в котором количество предыдущих соседей не превышает k (то есть он k -вырожден ), бесконечный граф имеет хороший порядок с не более чем 2 k - 2 более ранними соседями на вершина. В статье также доказывается отсутствие бесконечных графов с большим конечным обхватом и достаточно большим бесконечным хроматическим числом, а также существование графов с большим нечетным обхватом и бесконечным хроматическим числом.
Другие выбранные результаты включают:
- В своей диссертации он ввел модели L ( A ) (см. Относительную конструктивность ) и доказал, что если κ - регулярный кардинал, а A - подмножество κ + , то ZFC и 2 κ = κ + выполняются в L ( A ). Это может быть применено для доказательства результатов относительной согласованности: например, если 2 ℵ 0 = 2 непротиворечиво, то также и 2 ℵ 0 = ℵ 2 и 2 ℵ 1 = ℵ 2 .
- Теорема Хайнала об отображении множеств , решение гипотезы Станислава Рузевича . Эта работа касается функций ƒ, которые отображают элементы бесконечного множества S в малые подмножества S ; более конкретно, кардинальность всех подмножеств должно быть меньше , чем некоторые верхняя граница , которая сама по себе меньше , чем мощность S . Хайнал показывает, что S должно иметь равное количество подмножеств, в котором никакая пара элементов x и y не имеет x в ( y ) или y в ( x ). Этот результат значительно расширяет случай n = 1 теоремы Куратовского о свободном множестве , которая утверждает, что когда ƒ отображает несчетное множество в конечные подмножества, существует пара x , y, ни одна из которых не принадлежит образу другого.
- Пример двух графиков, каждый с бесчисленным хроматическим числом, но со счетным хроматическим прямым произведением. То есть для бесконечных графов гипотеза Хедетниеми неверна.
- В работе с Эрдёшем он доказал несколько результатов в системах бесконечных множеств , имеющих свойство B .
- Работа с Фредом Гэлвином, в которой они доказали, что если - сильный предельный кардинал, то
- Это был результат , который инициировал Шел «s теории PCF .
- Вместе с Джеймсом Эрлом Баумгартнером он доказал результат бесконечной теории Рамсея, согласно которому для любого разбиения вершин полного графа на ω 1 вершинах на конечное число подмножеств по крайней мере одно из подмножеств содержит полный подграф на α вершинах для каждого α <ω 1 . Это можно выразить, используя обозначения отношений разделения как
- Вместе с Мэтью Форманом он доказал, что если κ измеримо, то соотношение разбиения выполняется для α <Ω, где Ω < κ + - очень большой ординал.
- Вместе с Иштваном Юхасом он опубликовал несколько результатов по теоретико-множественной топологии . Они впервые установили существование пространств Хаусдорфа, которые наследственно отделимы, но не наследственно Линделёф, или наоборот. Существование регулярных пространств с этими свойствами ( S-пространство и L-пространство ) было установлено намного позже Тодорцевичем и Муром .
Награды и почести
В 1992 году Хайнал был награжден Офицерским крестом ордена Венгерской Республики. В 1999 году конференция в честь его 70-летия была проведена в DIMACS , а вторая конференция, посвященная 70-летию Хайнала и Веры Сош, была проведена в 2001 году в Будапеште . Хайнал стал членом Американского математического общества в 2012 году.