Teórico de conjuntos húngaro
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 (maestría en ciencias) en 1953 de la Universidad Eötvös Loránd , [6] su título de Candidato en Ciencias Matemáticas (aproximadamente equivalente a un 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 Sociedad Europea de Teoría de Conjuntos.
Hajnal era un ávido jugador de ajedrez . [8]
Hajnal era el padre de Peter Hajnal, codecano 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, Teoría de conjuntos (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 los 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 acotada con puertas mayoritarias ponderadas que resuelven el problema de calcular la paridad de productos internos .
- El teorema de Hajnal-Szemerédi sobre coloración equitativa , que demuestra una conjetura de Erdős de 1964: [13] sea Δ el grado máximo de un vértice en un gráfico finito G. Entonces G se puede colorear con Δ + 1 colores de tal manera que los tamaños de las clases de color difieran como máximo en uno. Varios autores han publicado posteriormente simplificaciones y generalizaciones de este resultado. [14]
- Un artículo con Erdős y JW Moon sobre gráficos que evitan tener k - cliques . El teorema de Turán caracteriza las gráficas de este tipo con el máximo número de aristas; Erdős, Hajnal y Moon encuentran una caracterización similar de los gráficos libres de camarilla k máximos más pequeños , mostrando que toman la forma de ciertos gráficos divididos . 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 infinitos e hipergráficos . [16] Este artículo extiende los métodos de coloración codiciosa de gráficos finitos a infinitos: si los vértices de un gráfico pueden estar bien ordenados de modo que cada vértice tenga pocos vecinos anteriores, tiene un número cromático bajo. Cuando todo 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 gráfico infinito tiene un ordenamiento bueno 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 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 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 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 más pequeñas que algún límite superior que sea en sí mismo más pequeño que la cardinalidad de S. Hajnal muestra que S debe tener un subconjunto equinumero en el que ningún par de elementos x e y tengan x en ƒ( y ) o y en ƒ( x ). Este resultado amplía enormemente el caso n = 1 del teorema del conjunto libre 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 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áficos 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 límite cardinal fuerte entonces
![{\displaystyle \aleph _ {\omega _ {1}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 2^{\aleph _{\omega _{1}}}<\aleph _{(2^{\aleph _{1}})^{+}}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Este fue el resultado que inició la teoría del pcf de Sela .
- 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 ω 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
![{\displaystyle \omega _{1}\to (\alpha )_{n}^{2}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Con Matthew Foreman demostró que si κ es medible entonces [23] la relación de partición es válida para α < Ω, donde Ω < κ + es un ordinal muy grande.
![{\displaystyle \kappa ^{+}\to (\alpha )^{2}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- 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 ( espacio S y espacio L) fue establecida mucho más tarde, 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 en 2001 se celebró en Budapest una segunda conferencia en honor a los 70 cumpleaños de Hajnal y Vera Sós . [26] Hajnal se convirtió en miembro de la Sociedad Estadounidense de Matemáticas [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 Wayback Machine .
- ↑ Academia Húngara de Ciencias, Sección de Matemáticas Archivado el 11 de marzo de 2009 en Wayback Machine .
- ^ abcde Currículum 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 Matemáticas . La fecha de 1957 es del cv de Hajnal; el sitio de genealogía matemática enumera la fecha del doctorado de Hajnal. como 1956.
- ↑ El anuncio Archivado el 24 de julio de 2008 en Wayback Machine para la conferencia de 2001 en honor a Hajnal y Sós lo llama “el gran ajedrecista”; la conferencia incluyó un torneo de ajedrez relámpago en su honor.
- ^ Lista de publicaciones Archivado el 16 de julio de 2010 en Wayback Machine desde el 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 el recuento de citas de Google Scholar, consultado el 1 de marzo de 2009.
- ^ Hajnal, A.; Maass, W.; Pudlak, P.; Szegedy, M.; Turán, G. (1987), “Circuitos umbral de profundidad acotada”, Proc. 28º Simposio. 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 Septentrional, 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, SEÑOR 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, SEÑOR 1698745; Kierstead, HA; Kostochka, AV (2008), "Una breve prueba 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 ; Martín, 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, SEÑOR 2433861
- ^ Erdős, P .; Hajnal, A.; Moon, JW (1964), "Un problema en teoría de grafos" (PDF) , American Mathematical Monthly , 71 (10), Mathematical Association of America: 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, CiteSeerX 10.1.1.414.4942 , doi : 10.1007/BF02020444 , MR 0193025 , S2CID 189780485
- ^ Hajnal, A. (1961), "Sobre un teorema de consistencia relacionado con el problema del continuo generalizado", Acta Mathematica Academiae Scientiarum Hungaricae , 12 (3–4): 321–376, doi :10.1007/BF02023921, MR 0150046, S2CID 120522353
- ^ Hajnal, A. (1961-1962), "Prueba de una conjetura de S. Ruziewicz", Fondo. Matemáticas. , 50 (2): 123–128, doi : 10.4064/fm-50-2-123-128 , SEÑOR 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.
- ^ Erdős, P .; Hajnal, A. (1964), "Sobre una propiedad de familias de conjuntos", Acta Mathematica Academiae Scientiarum Hungaricae , 12 (1–2): 87–123, doi :10.1007/BF02066676
- ^ Galvin, F .; Hajnal, A. (1975), "Desigualdades de potencias cardinales", Annals of Mathematics , Segunda Serie, 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 las relaciones de partición, consulte los dos artículos siguientes: Baumgartner, JE; Hajnal, A. (1987), "Una observación sobre las relaciones de partición para ordinales infinitos con una aplicación a la combinatoria finita", Lógica y combinatoria (Arcata, California, 1985) , Contemp. Matemáticas, vol. 65, Providencia, Rhode Island: 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 , 66 (2), Association for Symbolic Logic: 811–821, doi :10.2307/2695046, JSTOR 2695046, MR 1833480, S2CID 28122765
- ^ Capataz, M.; Hajnal, A. (2003). "Una relación de partición para los sucesores de grandes cardenales". Annalen Matemáticas . 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. Ciencia. Budapest. Secta Eötvös. Matemáticas. , 11 (1968), 115-124.
- ^ Thomas, Simón, ed. (1999), Teoría de conjuntos: Conferencia de Hajnal, 15 al 17 de octubre de 1999 Centro DIMACS , Serie DIMACS en Matemáticas Discretas e Informática Teórica, vol. 58, Sociedad Matemática Estadounidense , 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 , Estudios Matemáticos de la Sociedad Bolyai, vol. 15, Springer-Verlag, ISBN 978-3-540-32377-8
- ^ Lista de miembros de la Sociedad Estadounidense de Matemáticas
enlaces externos
- Página web de Hajnal en Rutgers.
- Página web de Hajnal en la academia de ciencias de Hungría