András Hajnal (13 de mayo de 1931 - 30 de julio de 2016 [1] [2] ) fue profesor de matemáticas en la Universidad de Rutgers [3] y miembro de la Academia de Ciencias de Hungría [4] conocido por su trabajo en teoría de conjuntos y combinatoria .
Biografía
Hajnal nació el 13 de mayo de 1931, [5] en Budapest , Hungría .
Recibió su diploma universitario (grado de maestría) en 1953 de la Universidad Eötvös Loránd , [6] su título de Candidato en Ciencias Matemáticas (aproximadamente equivalente al doctorado) 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 de 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 de Ciencias de Hungría en 1982 y dirigió su instituto de matemáticas desde 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 European Set Theory Society.
Hajnal era un ávido jugador de ajedrez . [8]
Hajnal era el padre de Peter Hajnal , el co-decano del Colegio Europeo de Artes Liberales .
Investigaciones y publicaciones
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 trabajos de investigación mejor citados [11] incluyen
- Un artículo sobre la complejidad del circuito con Maas, Pudlak, Szegedy y György Turán, [12] que muestra límites inferiores exponenciales en el tamaño de los circuitos de profundidad limitada con puertas de mayoría ponderada que resuelven el problema de calcular la paridad de los productos internos .
- El teorema Hajnal-Szemerédi en coloración equitativa , lo que demuestra una conjetura 1964 de Erdős: [13] dejó Δ denota el grado máximo de un vértice en un gráfico finito G . Entonces G se puede colorear con colores Δ + 1 de tal manera que los tamaños de las clases de colores difieran como máximo en uno. Posteriormente, varios autores han publicado simplificaciones y generalizaciones de este resultado. [14]
- Un artículo con Erdős y JW Moon sobre gráficos que evitan tener k - camarillas . El teorema de Turán caracteriza las gráficas de este tipo con el número máximo de aristas; Erdős, Hajnal y Moon encuentran una caracterización similar de las gráficas libres de k -clicas máximas más pequeñas , mostrando que toman la forma de ciertas gráficas divididas . Este artículo también prueba una conjetura de Erdős y Gallai sobre el número de aristas en un gráfico crítico para la dominación . [15]
- Un artículo con Erdős sobre problemas de coloración de gráficos para gráficos e hipergráficos infinitos . [16] Este artículo extiende los métodos codiciosos de coloración de gráficas finitas a infinitas: si los vértices de una gráfica 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 gráficos infinitos con una circunferencia finita alta y un número cromático infinito suficientemente grande y la existencia de gráficos con una circunferencia alta impar 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 mantienen en L ( A ). Esto se puede aplicar para probar resultados de consistencia relativa: por ejemplo, si 2 ℵ 0 = ℵ 2 es consistente, entonces también lo es 2 ℵ 0 = ℵ 2 y 2 ℵ 1 = ℵ 2 .
- Teorema de mapeo de conjuntos de Hajnal , la solución a una conjetura de Stanisław Ruziewicz . [18] Este trabajo se refiere a funciones ƒ que mapean los miembros de un conjunto infinito S a pequeños subconjuntos de S ; más específicamente, cardinalidades todos los subconjuntos debe ser menor que algunos límite superior que es en sí mismo más pequeña que la cardinalidad de S . Shows Hajnal que S debe tener un equinumerous subconjunto en el que ningún par de elementos de x y y Tienes x en ƒ ( y ) o y en ƒ ( x ). Este resultado amplía enormemente el caso n = 1 del teorema de conjuntos libres de Kuratowski , que establece que cuando f mapea 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 gráficos cada uno con un número cromático incontable, pero con un producto directo cromático contable. [19] Es decir, la conjetura de Hedetniemi falla para gráficas infinitas.
- En un documento [20] con Paul Erdős demostró varios resultados en los sistemas de conjuntos infinitos que tienen la propiedad B .
- Un artículo con Fred Galvin en el que [21] demostraron que sies un fuerte límite cardinal entonces
- 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 por cada partición de los vértices de un grafo completo en ω 1 vértices en un número finito de subconjuntos, al menos uno de los subconjuntos contiene un subgrafo completo en α vértices, para cada α <ω 1 . [22] Esto se puede expresar usando la notación de relaciones de partición como
- Con Matthew Foreman demostró que si κ es medible, entonces [23] la relación de particiónse cumple para α <Ω, donde Ω < κ + es un ordinal muy grande.
- Con István Juhász publicó varios resultados en topología de teorí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 mucho más tarde se estableció, por Todorcevic y Moore .
Premios y honores
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 años de Hajnal y Vera Sós se llevó a cabo en 2001 en Budapest . [26] Hajnal se convirtió en miembro de la American Mathematical Society [27] en 2012.
Referencias
- ^ Anuncio del Instituto Rényi
- ↑ Recordando a András Hajnal (1931-2016)
- ^ Departamento de matemáticas de la Universidad de Rutgers - Facultad emérita Archivado el 15 de julio de 2010 en la Wayback Machine .
- ^ Academia de Ciencias de Hungría, Sección de Matemáticas. Archivado el 11 de marzo de 2009 en la Wayback Machine .
- ^ a b c d e Curriculum vitae .
- ↑ A halmazelmélet huszadik századi "Hajnal A" , Entrevista de M. Streho con AH, Magyar Tudomány , 2001.
- ^ Andras Hajnal en el Proyecto de genealogía de las matemáticas . La fecha de 1957 es del cv de Hajnal; el sitio de genealogía de las matemáticas enumera la fecha del doctorado de Hajnal. como 1956.
- ^ El anuncio Archivado el 24 de julio de 2008 en la Wayback Machine para la conferencia de 2001 en honor a Hajnal y Sós lo llama "el gran jugador de ajedrez"; la conferencia incluyó un torneo de ajedrez relámpago en su honor.
- ^ Lista de publicaciones archivadas el 16 de julio de 2010 en la Wayback Machine del sitio web de Hajnal.
- ^ Lista de colaboradores de Erdős por número de artículos conjuntos , del sitio web del proyecto Erdős number.
- ^ Según recuentos de citas del académico de Google, recuperado el 1 de marzo de 2009.
- ^ Hajnal, A .; Maass, W .; Pudlak, P .; Szegedy, M .; Turán, G. (1987), "Circuitos de umbral de profundidad acotada", Proc. 28th Symp. Fundamentos de la informática (FOCS 1987) , págs. 99-110, doi : 10.1109 / SFCS.1987.59 , S2CID 9206369
- ^ Hajnal, A .; Szemerédi, E. (1970), "Prueba de una conjetura de P. Erdős", Teoría combinatoria y sus aplicaciones, II (Proc. Colloq., Balatonfüred, 1969) , Holanda del Norte, págs. 601–623, MR 0297607
- ^ Catlin, Paul A. (1980), "Sobre el teorema de Hajnal-Szemerédi sobre camarillas disjuntas", Utilitas Mathematica , 17 : 163-177, MR 0583138; Fischer, Eldar (1999), "Variantes del teorema de Hajnal-Szemerédi", Journal of Graph Theory , 31 (4): 275-282, doi : 10.1002 / (SICI) 1097-0118 (199908) 31: 4 <275: : AID-JGT2> 3.0.CO; 2-F , MR 1698745; Kierstead, HA; Kostochka, AV (2008), "Una breve demostración del teorema de Hajnal-Szemerédi sobre coloración equitativa", Combinatoria, Probabilidad y Computación , 17 (2): 265-270, CiteSeerX 10.1.1.86.4139 , doi : 10.1017 / S0963548307008619 , Señor 2396352 , S2CID 12254683; Martin, Ryan; Szemerédi, Endre (2008), "Versión cuatripartita del teorema de Hajnal-Szemerédi", Matemáticas discretas , 308 (19): 4337–4360, doi : 10.1016 / j.disc.2007.08.019 , MR 2433861
- ^ Erdős, P .; Hajnal, A .; Moon, JW (1964), "Un problema en la teoría de grafos" (PDF) , American Mathematical Monthly , Asociación Matemática de América, 71 (10): 1107-1110, doi : 10.2307 / 2311408 , JSTOR 2311408 , MR 0170339 , S2CID 120072868 , archivado desde el original (PDF) el 2020-02-19
- ^ Erdős, P .; Hajnal, A. (1966), "Sobre el número cromático de gráficos y sistemas de conjuntos", Acta Mathematica Hungarica , 17 (1–2): 61–99, doi : 10.1007 / BF02020444 , MR 0193025 , S2CID 189780485
- ^ Hajnal, A. (1961), "Sobre un teorema de coherencia relacionado con el problema continuo generalizado", Acta Math. Acad. Sci. Colgado. , 12 (3–4): 321–376, doi : 10.1007 / BF02023921 , MR 0150046 , S2CID 120522353
- ^ Hajnal, A. (1961-1962), "Prueba de una conjetura de S. Ruziewicz", Fund. Matemáticas. , 50 (2): 123–128, doi : 10.4064 / fm-50-2-123-128 , MR 0131986
- ^ Hajnal, A. (1985), "El número cromático del producto de dos gráficos cromáticos ℵ 1 puede ser contable", Combinatorica , 5 (2): 137–140, doi : 10.1007 / BF02579376 , MR 0815579 , S2CID 27087122 .
- ^ P. Erdős, A. Hajnal: En una propiedad de familias de conjuntos, Acta Math. Acad. Sci. Hung .. , 12 (1961), 87-123.
- ^ Galvin, F .; Hajnal, A. (1975), "Desigualdades para los poderes cardinales", Annals of Mathematics , Second Series, 101 (3): 491–498, doi : 10.2307 / 1970936 , JSTOR 1970936
- ^ Baumgartner, J .; Hajnal, A. (1973), "Una prueba (que involucra el axioma de Martin) de una relación de partición", Fundamenta Mathematicae , 78 (3): 193-203, doi : 10.4064 / fm-78-3-193-203 , MR 0319768. Para obtener resultados adicionales de Baumgartner y Hajnal sobre relaciones de partición, consulte los dos artículos siguientes: Baumgartner, JE; Hajnal, A. (1987), "Un comentario sobre las relaciones de partición para infinitos ordinales con una aplicación a la combinatoria finita", Lógica y combinatoria (Arcata, Calif., 1985) , Contemp. Math., 65 años , Providence, RI: Amer. Matemáticas. Soc., Págs. 157-167, doi : 10.1090 / conm / 065/891246 , MR 0891246; Baumgartner, James E .; Hajnal, Andras (2001), "Relaciones de partición polarizadas", The Journal of Symbolic Logic , Association for Symbolic Logic, 66 (2): 811–821, doi : 10.2307 / 2695046 , JSTOR 2695046 , MR 1833480 , S2CID 28122765
- ^ Foreman, M .; Hajnal, A. (2003). "Una relación de partición para los sucesores de grandes cardenales". Matemáticas. Ann . 325 (3): 583–623. doi : 10.1007 / s00208-002-0323-7 . S2CID 120500400 .
- ^ A. Hajnal, I. Juhász: Sobre espacios hereditariamente α-Lindelöf y hereditariamente α-separables, Ann. Univ. Sci. Budapest. Secta Eötvös. Matemáticas. , 11 (1968), 115-124.
- ^ Thomas, Simon, ed. (1999), Teoría de conjuntos: Conferencia de Hajnal, 15-17 de octubre de 1999 Centro DIMACS, Serie DIMACS en Matemáticas discretas y Ciencias de la computación teórica, 58 , American Mathematical Society , ISBN 978-0-8218-2786-4
- ^ Győri, Ervin; Katona, Gyula OH ; Lovász, László , eds. (2006), Más conjuntos, gráficos y números: un saludo a Vera Sós y András Hajnal , Bolyai Society Mathematical Studies, 15 , Springer-Verlag, ISBN 978-3-540-32377-8
- ^ Lista de miembros de la American Mathematical Society
enlaces externos
- Página web de Hajnal en Rutgers .
- Página web de Hajnal en la academia de ciencias de Hungría