Václav Chvátal

Václav (Vašek) Chvátal ( en checo: [ˈvaːtslaf ˈxvaːtal] ) es profesor emérito del Departamento de Ciencias de la Computación e Ingeniería de Software de la Universidad Concordia en Montreal, Quebec , Canadá, y profesor visitante en la Universidad Charles de Praga . Ha publicado extensamente sobre temas de teoría de grafos , combinatoria y optimización combinatoria .

Chvátal nació en 1946 en Praga y estudió matemáticas en la Universidad Carolina de Praga, donde estudió bajo la supervisión de Zdeněk Hedrlín . ^[4] Huyó de Checoslovaquia en 1968, tres días después de la invasión soviética , ^[5] y completó su doctorado. en Matemáticas en la Universidad de Waterloo , bajo la supervisión de Crispin St. JA Nash-Williams , en el otoño de 1970. ^{[4] [6]} Posteriormente, ocupó puestos en la Universidad McGill (1971 y 1978-1986), la Universidad de Stanford (1972 y 1974-1977), la Universidad de Montreal (1972-1974 y 1977-1978) y la Universidad Rutgers (1986-2004) antes de regresar a Montreal para la Cátedra de Investigación de Canadá en Optimización Combinatoria ^{[7] [5]} en Concordia (2004-2011) y la Cátedra de Investigación de Canadá en Matemáticas Discretas (2011-2014) hasta su jubilación.

Chvátal conoció la teoría de grafos por primera vez en 1964, al encontrar un libro de Claude Berge en una librería de Pilsen ^[8] y gran parte de su investigación involucra la teoría de grafos:

• Su primera publicación matemática, a la edad de 19 años, trataba sobre gráficos dirigidos que no pueden asignarse a sí mismos mediante ningún homomorfismo de gráfico no trivial ^[9].
• Otro resultado de la teoría de grafos de Chvátal fue la construcción en 1970 del grafo libre de triángulos más pequeño posible que es a la vez 4- cromático y 4- regular , ahora conocido como el grafo de Chvátal . ^{[4] [10]}
• Un artículo de 1972 ^[11] que relaciona los ciclos hamiltonianos con la conectividad y el tamaño máximo de conjunto independiente de un grafo le valió a Chvátal su número de Erdős de 1. Específicamente, si existe un s tal que un grafo dado es s - conexo por vértices y no tiene ningún conjunto independiente de ( s  + 1) vértices, el grafo debe ser hamiltoniano. Avis et al. ^[4] cuentan la historia de Chvátal y Erdős trabajando en este resultado en el transcurso de un largo viaje por carretera, y luego agradeciendo a Louise Guy "por su conducción constante".
• En un artículo de 1973, ^[12] Chvátal introdujo el concepto de tenacidad de grafos , una medida de la conectividad de grafos que está estrechamente relacionada con la existencia de ciclos hamiltonianos . Un grafo es t -tenso si, para cada k mayor que 1, la eliminación de menos de tk vértices deja menos de k componentes conectados en el subgrafo restante. Por ejemplo, en un grafo con un ciclo hamiltoniano, la eliminación de cualquier conjunto no vacío de vértices divide el ciclo en, como máximo, tantas piezas como el número de vértices eliminados, por lo que los grafos hamiltonianos son 1-tensos. Chvátal conjeturó que los grafos 3/2-tensos, y más tarde que los grafos 2-tensos, son siempre hamiltonianos; a pesar de que investigadores posteriores encontraron contraejemplos a estas conjeturas, aún permanece abierto si algún límite constante en la tenacidad del grafo es suficiente para garantizar la hamiltonicidad. ^[13]

Algunos de los trabajos de Chvátal se refieren a familias de conjuntos, o equivalentemente hipergrafos , un tema que ya abordó en su tesis doctoral, donde también estudió la teoría de Ramsey .

• En una conjetura de 1972 que Erdős llamó "sorprendente" y "bella", ^[14] y que permanece abierta (con un premio de $10 ofrecido por Chvátal por su solución) ^{[15] [16]} sugirió que, en cualquier familia de conjuntos cerrados bajo la operación de tomar subconjuntos , la subfamilia más grande que se interseca por pares siempre se puede encontrar eligiendo un elemento de uno de los conjuntos y manteniendo todos los conjuntos que contienen ese elemento.
• En 1979, ^[17] estudió una versión ponderada del problema de cobertura de conjuntos y demostró que un algoritmo voraz proporciona buenas aproximaciones a la solución óptima, generalizando resultados no ponderados previos de David S. Johnson (J. Comp. Sys. Sci. 1974) y László Lovász (Discrete Math. 1975).

Chvátal se interesó por primera vez en la programación lineal a través de la influencia de Jack Edmonds mientras Chvátal era estudiante en Waterloo. ^[4] Rápidamente reconoció la importancia de los planos de corte para abordar problemas de optimización combinatoria como el cálculo de conjuntos independientes máximos y, en particular, introdujo la noción de una prueba de plano de corte. ^{[18] [19] [20] [21]} En Stanford en la década de 1970, comenzó a escribir su popular libro de texto, Programación lineal , que se publicó en 1983. ^[4]

Los planos de corte se encuentran en el corazón del método de ramificación y corte utilizado por los solucionadores eficientes para el problema del viajante de comercio . Entre 1988 y 2005, el equipo de David L. Applegate , Robert E. Bixby , Vašek Chvátal y William J. Cook desarrolló uno de estos solucionadores, Concorde . ^{[22] [23]} El equipo fue galardonado con el Premio Beale-Orchard-Hays a la Excelencia en Programación Matemática Computacional en 2000 por su artículo de diez páginas ^[24] que enumeraba algunos de los refinamientos de Concorde del método de ramificación y corte que llevaron a la solución de una instancia de 13.509 ciudades y fue galardonado con el Premio Frederick W. Lanchester en 2007 por su libro, The Traveling Salesman Problem: A Computational Study .

Chvátal también es conocido por demostrar el teorema de la galería de arte , ^{[25] [26] [27] [28]} por investigar una secuencia digital autodescriptiva, ^{[29] [30]} por su trabajo con David Sankoff en las constantes de Chvátal-Sankoff que controlan el comportamiento del problema de la subsecuencia común más larga en entradas aleatorias, ^[31] y por su trabajo con Endre Szemerédi en instancias difíciles para demostrar el teorema de resolución . ^[32]

• Vasek Chvátal (1983). Programación lineal . WH Freeman. ISBN 978-0-7167-1587-0.. Traducción japonesa publicada por Keigaku Shuppan, Tokio, 1986.
• C. Berge y V. Chvátal (eds.) (1984). Temas sobre grafos perfectos. Elsevier. ISBN 978-0-444-86587-8. {{cite book}}: |author=tiene nombre genérico ( ayuda )
• David L. Applegate; Robert E. Bixby; Vasek Chvátal; William J. Cook (2007). El problema del viajante: un estudio computacional. Prensa de la Universidad de Princeton. ISBN 978-0-691-12993-8.^[33]
• Vašek Chvátal, ed. (2011). Optimización combinatoria: métodos y aplicaciones. IOS Press. ISBN 978-1-60750-717-8Archivado desde el original el 21-03-2017 . Consultado el 22-03-2017 .
• Vašek Chvátal (2021). Encantos matemáticos discretos de Paul Erdős. Una introducción sencilla. Prensa de la Universidad de Cambridge. ISBN 978-1-108-92740-6.

• Lista de personas de la Universidad de Waterloo

• Página de inicio de Chvátal