András Hajnal

András Hajnal (13 de mayo de 1931 - 30 de julio de 2016 ^{[1] [2]} ) fue un profesor de matemáticas en la Universidad Rutgers ^[3] y miembro de la Academia Húngara de Ciencias ^[4] conocido por su trabajo en teoría de conjuntos y combinatoria .

Hajnal nació el 13 de mayo de 1931, ^[5] en Budapest , Hungría .

Recibió su diploma universitario (grado de M.Sc.) en 1953 de la Universidad Eötvös Loránd , ^[6] su título de Candidato en Ciencias Matemáticas (aproximadamente equivalente a Ph.D.) en 1957, bajo la supervisión de László Kalmár , ^[7] y su título de Doctor en Ciencias Matemáticas en 1962. De 1956 a 1995 fue miembro de la facultad de la Universidad Eötvös Loránd ; En 1994 se trasladó a la Universidad Rutgers para convertirse en director de DIMACS , y permaneció allí como profesor hasta su jubilación en 2004. ^[5] Se convirtió en miembro de la Academia Húngara de Ciencias en 1982, y dirigió su instituto matemático de 1982 a 1992. ^[5] Fue secretario general de la Sociedad Matemática János Bolyai de 1980 a 1990, y presidente de la sociedad de 1990 a 1994. ^[5] A partir de 1981, fue editor asesor de la revista Combinatorica . Hajnal también fue uno de los presidentes honorarios de la Sociedad Europea de Teoría de Conjuntos.

Hajnal era un ávido jugador de ajedrez . ^[8]

Hajnal fue el padre de Peter Hajnal, co-decano del Colegio Europeo de Artes Liberales .

Hajnal fue autor de más de 150 publicaciones. ^[9] Entre los muchos coautores de Paul Erdős , tuvo el segundo mayor número de artículos conjuntos, 56. ^[10] Con Peter Hamburger, escribió un libro de texto, Set Theory (Cambridge University Press, 1999, ISBN  0-521-59667-X ). Algunos de sus artículos de investigación más citados ^[11] incluyen

• Un artículo sobre la complejidad de circuitos con Maas, Pudlak, Szegedy y György Turán, ^[12] que muestra límites inferiores exponenciales en el tamaño de circuitos de profundidad limitada con puertas de mayoría ponderada que resuelven el problema de calcular la paridad de productos internos .
• El teorema de Hajnal–Szemerédi sobre coloración equitativa , que prueba una conjetura de Erdős de 1964: ^[13] sea Δ el grado máximo de un vértice en un grafo finito G . Entonces G puede colorearse con Δ + 1 colores de tal manera que los tamaños de las clases de color difieran en como máximo uno. Varios autores han publicado posteriormente simplificaciones y generalizaciones de este resultado. ^[14]
• Un artículo con Erdős y JW Moon sobre grafos que evitan tener k - camarillas . El teorema de Turán caracteriza los grafos de este tipo con el máximo número de aristas; Erdős, Hajnal y Moon encuentran una caracterización similar de los grafos libres de k -camarillas más pequeños , mostrando que toman la forma de ciertos grafos divididos . Este artículo también prueba una conjetura de Erdős y Gallai sobre el número de aristas en un grafo crítico para la dominación . ^[15]
• Un artículo con Erdős sobre problemas de coloración de grafos para grafos infinitos e hipergrafos . ^[16] Este artículo extiende los métodos de coloración voraz de grafos finitos a infinitos: si los vértices de un grafo pueden estar bien ordenados de modo que cada vértice tenga pocos vecinos anteriores, tiene un número cromático bajo. Cuando cada subgrafo finito tiene un ordenamiento de este tipo en el que el número de vecinos anteriores es como máximo k (es decir, es k -degenerado ), un grafo infinito tiene un buen ordenamiento con como máximo 2 k  − 2 vecinos anteriores por vértice. El artículo también demuestra la inexistencia de grafos infinitos con una circunferencia finita alta y un número cromático infinito suficientemente grande y la existencia de grafos con una circunferencia impar alta y un número cromático infinito.

Otros resultados seleccionados incluyen:

• En su disertación ^[17] introdujo los modelos L ( A ) (ver constructibilidad relativa ), y demostró que si κ es un cardinal regular y A es un subconjunto de κ ⁺ , entonces ZFC y 2 ^κ  = κ ⁺ se cumplen en L ( A ). Esto se puede aplicar para demostrar resultados de consistencia relativa: por ejemplo, si 2 ^{ℵ ₀}  = ℵ ₂ es consistente, entonces también lo es 2 ^{ℵ ₀}  = ℵ ₂ y 2 ^{ℵ ₁}  = ℵ ₂ .
• Teorema de aplicación de conjuntos de Hajnal, la solución a una conjetura de Stanisław Ruziewicz . ^[18] Este trabajo se ocupa de funciones ƒ que asignan los miembros de un conjunto infinito S a pequeños subconjuntos de S ; más específicamente, las cardinalidades de todos los subconjuntos deben ser menores que algún límite superior que sea en sí mismo menor que la cardinalidad de S . Hajnal muestra que S debe tener un subconjunto equinumeroso en el que ningún par de elementos x e y tenga x en ƒ( y ) o y en ƒ( x ). Este resultado extiende en gran medida el caso n  = 1 del teorema de conjuntos libres de Kuratowski , que establece que cuando ƒ asigna un conjunto incontable a subconjuntos finitos existe un par x , y ninguno de los cuales pertenece a la imagen del otro.
• Un ejemplo de dos grafos cada uno con número cromático incontable, pero con producto directo cromático contable. ^[19] Es decir, la conjetura de Hedetniemi falla para grafos infinitos.
• En un artículo ^[20] con Paul Erdős demostró varios resultados sobre sistemas de conjuntos infinitos que tienen la propiedad B.
• Un artículo con Fred Galvin en el que ^[21] demostraron que si es un cardinal límite fuerte entonces${\displaystyle \aleph _ {\omega _ {1}}}$

  ${\displaystyle 2^{\aleph _{\omega _{1}}}<\aleph _{(2^{\aleph _{1}})^{+}}.}$

Este fue el resultado que inició la teoría PCF de Shelah .

• Con James Earl Baumgartner demostró un resultado en la teoría infinita de Ramsey , que para cada partición de los vértices de un grafo completo en ω ₁ vértices en un número finito de subconjuntos, al menos uno de los subconjuntos contiene un subgrafo completo en α vértices, para cada α < ω ₁ . ^[22] Esto se puede expresar utilizando la notación de relaciones de partición como

  ${\displaystyle \omega _{1}\to (\alpha )_{n}^{2}.}$

• Con Matthew Foreman demostró que si κ es medible entonces ^[23] la relación de partición se cumple para α  < Ω, donde Ω <  κ ⁺ es un ordinal muy grande.${\displaystyle \kappa ^{+}\to (\alpha )^{2}}$
• Junto con István Juhász publicó varios resultados en topología de conjuntos . Primero establecieron ^[24] la existencia de espacios de Hausdorff que son hereditariamente separables, pero no hereditariamente Lindelöf, o viceversa. La existencia de espacios regulares con estas propiedades ( S-espacio y L-espacio) fue establecida mucho más tarde, por Todorcevic y Moore .

En 1992, Hajnal recibió la Cruz de Oficial de la Orden de la República de Hungría. ^[5] En 1999, se celebró una conferencia en honor a su 70 cumpleaños en DIMACS , ^[25] y una segunda conferencia en honor a los 70 cumpleaños de Hajnal y Vera Sós se celebró en 2001 en Budapest . ^[26] Hajnal se convirtió en miembro de la American Mathematical Society ^[27] en 2012.

• Página web de Hajnal en Rutgers.
• Página web de Hajnal en la Academia Húngara de Ciencias