András Hajnal

Teórico de conjuntos húngaro

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 .

Biografía

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 .

Investigación 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 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 .

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 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.

Referencias

1. Anuncio del Instituto Rényi
2. Recordando a András Hajnal (1931-2016)
3. Departamento de Matemáticas de la Universidad Rutgers – Profesor emérito Archivado el 15 de julio de 2010 en Wayback Machine .
4. Academia Húngara de Ciencias, Sección de Matemáticas Archivado el 11 de marzo de 2009 en Wayback Machine .
5. Currículum vitae.
6. A halmazelmélet huszadik századi "Hajnal A", entrevista de M. Streho con AH, Magyar Tudomány , 2001.
7. Andras Hajnal en el Proyecto de Genealogía Matemática . La fecha de 1957 corresponde al CV de Hajnal; el sitio de genealogía matemática indica que la fecha del doctorado de Hajnal es 1956.
8. 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.
9. Lista de publicaciones Archivado el 16 de julio de 2010 en Wayback Machine desde el sitio web de Hajnal.
10. Lista de colaboradores de Erdős por número de artículos conjuntos, del sitio web del proyecto Número de Erdős.
11. Según recuento de citas de Google Scholar, consultado el 1 de marzo de 2009.
12. Hajnal, A.; Maass, W.; Pudlak, P.; Szegedy, M.; Turán, G. (1987), "Circuitos de umbral de profundidad limitada", Proc. 28th Symp. Foundations of Computer Science (FOCS 1987) , págs. 99-110, doi :10.1109/SFCS.1987.59, ISBN 0-8186-0807-2, Número de identificación del sujeto  9206369
13. 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
14. 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", Combinatorics, Probability and Computing , 17 (2): 265–270, CiteSeerX 10.1.1.86.4139 , doi :10.1017/S0963548307008619, MR  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
15. Erdős, P .; Hajnal, A.; Moon, JW (1964), "Un problema en la 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 19 de febrero de 2020
16. Erdős, P. ; Hajnal, A. (1966), "Sobre el número cromático de grafos 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 
17. 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
18. Hajnal, A. (1961–1962), "Prueba de una conjetura de S. Ruziewicz", Fund. Math. , 50 (2): 123–128, doi : 10.4064/fm-50-2-123-128 , MR  0131986
19. Hajnal, A. (1985), "El número cromático del producto de dos grafos cromáticos ℵ ₁ puede ser contable", Combinatorica , 5 (2): 137–140, doi :10.1007/BF02579376, MR  0815579, S2CID  27087122.
20. 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
21. Galvin, F. ; Hajnal, A. (1975), "Desigualdades para potencias cardinales", Anales de Matemáticas , Segunda serie, 101 (3): 491–498, doi :10.2307/1970936, JSTOR  1970936
22. 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), "A remark on participation relationships for infinite ordinals with an application to finite combinatorics", Logic and combinatorics (Arcata, Calif., 1985) , Contemp. Math., vol. 65, Providence, RI: Amer. Math. Soc., págs. 157–167, doi :10.1090/conm/065/891246, ISBN 978-0-8218-5052-7, Sr.  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
23. Foreman, M.; Hajnal, A. (2003). "Una relación de partición para sucesores de grandes cardinales". Mathematische Annalen . 325 (3): 583–623. doi :10.1007/s00208-002-0323-7. S2CID  120500400.
24. 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.
25. Thomas, Simon, ed. (1999), Teoría de conjuntos: la conferencia de Hajnal, 15-17 de octubre de 1999, DIMACS Center , Serie DIMACS en matemáticas discretas y ciencias de la computación teórica, vol. 58, American Mathematical Society , ISBN 978-0-8218-2786-4
26. 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
27. Lista de miembros de la Sociedad Americana de Matemáticas

Enlaces externos

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