Chvátal aprendió por primera vez sobre la teoría de grafos 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:
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 gráfico, le valió a Chvátal su número Erdős de 1. Específicamente, si existe una s tal que una gráfica dada esté s - conectada por vértices y no tenga ( s + 1)-conjunto independiente de vértices, la gráfica debe ser hamiltoniana. Avis et al. [4] cuentan la historia de Chvátal y Erdő alcanzando 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 dureza del gráfico , una medida de la conectividad del gráfico que está estrechamente relacionada con la existencia de ciclos hamiltonianos . Un gráfico es t -difícil si, por 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 gráfico con un ciclo hamiltoniano, la eliminación de cualquier conjunto de vértices no vacío divide el ciclo como máximo en tantas partes como el número de vértices eliminados, por lo que los gráficos hamiltonianos son resistentes a 1. Chvátal conjeturó que las gráficas difíciles de 3/2, y más tarde las gráficas difíciles de 2, son siempre hamiltonianas; A pesar de que investigadores posteriores encontraron contraejemplos a estas conjeturas, aún permanece abierto si algún límite constante en la dureza del gráfico es suficiente para garantizar la hamiltonicidad. [13]
Parte del trabajo de Chvátal se refiere a familias de conjuntos, o de manera equivalente hipergrafías , un tema que ya se aborda en su doctorado. tesis, donde también estudió la teoría de Ramsey .
En una conjetura de 1972 que Erdős calificó de "sorprendente" y "hermosa", [14] y que permanece abierta (con un premio de 10 dólares 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 cruza por pares siempre se puede encontrar eligiendo un elemento de uno de los conjuntos y manteniendo todos los conjuntos que contienen ese elemento.
Chvátal se interesó por primera vez en la programación lineal gracias a la influencia de Jack Edmonds mientras Chvátal era estudiante en Waterloo. [4] Rápidamente reconoció la importancia de los planos de corte para atacar problemas de optimización combinatoria como el cálculo de conjuntos independientes máximos y, en particular, introdujo la noción de 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 son el corazón de la rama y del método de corte que utilizan los solucionadores eficientes del problema del viajante . Entre 1988 y 2005, el equipo de David L. Applegate , Robert E. Bixby , Vašek Chvátal y William J. Cook desarrolló uno de esos solucionadores, Concorde . [22] [23] El equipo recibió 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 enumera algunas de las mejoras del Concorde en el método de rama y corte que condujo a la solución. de una instancia de 13.509 ciudades y recibió el premio Frederick W. Lanchester en 2007 por su libro The Travelling Salesman Problem: A Computational Study .
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 gráficos 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. Prensa IOS. ISBN 978-1-60750-717-8.
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.
^ Ganadores anteriores del premio Beale-Orchard-Hays.
^ Premio Frederick W. Lanchester 2007, consultado el 19 de marzo de 2017.
^ Premio de Teoría John von Neumann 2015, consultado el 19 de marzo de 2017.
^ abcdef Avis, D .; Bondy, A.; Cocinero, W .; Caña, B. (2007). "Vasek Chvatal: una breve introducción" (PDF) . Gráficas y Combinatoria . 23 : 41–66. CiteSeerX 10.1.1.127.5910 . doi :10.1007/s00373-007-0721-4. S2CID 11121944.
^ ab Vasek Chvátal es 'el profesor viajero', Informe del jueves de Concordia, 10 de febrero de 2005.
^ El Proyecto Genealogía de las Matemáticas - Václav Chvátal
^ Vasek Chvatal recibió la cátedra de investigación de Canadá, Informe del jueves de Concordia, 23 de octubre de 2003.
^ Chvátal, Vašek (1997), "En alabanza de Claude Berge", Matemáticas discretas , 165–166: 3–9, doi : 10.1016/s0012-365x(96)00156-2,
^ Chvátal, Václav (1965), "Sobre torneos y gráficos rígidos finitos y contables", Commentationes Mathematicae Universitatis Carolinae , 6 : 429–438.
^ V. Chvátal; P. Erdős (1972), "Una nota sobre los circuitos hamiltonianos" (PDF) , Matemáticas discretas , 2 (2): 111–113, doi : 10.1016/0012-365x(72)90079-9,
^ Chvátal, V. (1973), "Gráficos difíciles y circuitos hamiltonianos", Matemáticas discretas , 5 (3): 215–228, doi : 10.1016/0012-365x(73)90138-6,
^ Lesniak, Linda, la difícil conjetura de Chvátal (PDF)
^ Revisiones matemáticas MR0369170
^ V. Chvátal; David A. Klarner ; DE Knuth (1972), "Problemas de investigación combinatorios seleccionados" (PDF) , Departamento de Ciencias de la Computación, Universidad de Stanford , Stan-CS-TR-72-292: Problema 25
^ Chvátal, Vašek, Una conjetura en combinatoria extrema
^ "Una heurística codiciosa para el problema de cobertura de conjuntos", Matemáticas de la investigación de operaciones, 1979
^ Chvátal, Václav (1973), "Politopos de Edmonds y gráficos débilmente hamiltonianos", Programación matemática , 5 : 29–40, doi :10.1007/BF01580109, S2CID 8140217,
^ Chvátal, Václav (1973), "Politopos de Edmonds y una jerarquía de problemas combinatorios", Matemáticas discretas , 4 (4): 305–337, doi : 10.1016/0012-365x(73)90167-2,
^ Chvátal, Václav (1975), "Algunos aspectos de programación lineal de la combinatoria" (PDF) , Congressus Numerantium , 13 : 2–30,
^ Chvátal, V. (1975), "Sobre ciertos politopos asociados con gráficos", Journal of Combinatorial Theory, Serie B , 18 (2): 138–154, doi : 10.1016/0095-8956(75)90041-6.
^ Problema de matemáticas, largo y desconcertante, rinde lentamente. New York Times , 12 de marzo de 1991.
^ Rutas ingeniosas, Science News Online, 1 de enero de 2005.
^ Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William (1998), "Sobre la solución de los problemas del viajante", Documenta Mathematica , Volumen adicional ICM III
^ Weisstein, Eric W. "Teorema de la galería de arte". De MathWorld: un recurso web de Wolfram. http://mathworld.wolfram.com/ArtGalleryTheorem.html
^ Diagonales: Parte I 4. Problemas de la galería de arte, columna destacada de AMS por Joseph Malkevitch
^ Teorema de la galería de arte de Chvatal en Cut the Knot de Alexander Bogomolny
^ Obsesión, Numb3rs, episodio 3, temporada 2
^ Chvátal, Vašek (1993), "Notas sobre la secuencia Kolakoski", Informes técnicos DIMACS , TR: 93-84
^ Problemas peligrosos, Science News Online, 13 de julio de 2002.
^ Chvátal, Václav; Sankoff, David (1975), "Subsecuencias comunes más largas de dos secuencias aleatorias", Journal of Applied Probability , 12 (2): 306–315, doi :10.2307/3212444, JSTOR 3212444, S2CID 250345191.
^ Chvátal, Vašek; Szemerédi, Endre (1988), "Muchos ejemplos difíciles de resolución", Journal of the ACM , 35 (4): 759–768, doi : 10.1145/48014.48016 , S2CID 2526816.
^ Borchers, Brian (25 de marzo de 2007). "Revisión del problema del viajante: un estudio computacional". Reseñas de MAA, Asociación Matemática de América .
