Václav (Vašek) Chvátal ( checo: [ˈvaːtslaf ˈxvaːtal] es profesor emérito en el Departamento de Ciencias de la Computación e Ingeniería de Software de la Universidad de Concordia en Montreal, Quebec , Canadá. Ha publicado extensamente sobre temas de teoría de grafos , combinatoria y optimización combinatoria. .
Václav Chvátal | |
---|---|
Nació | |
Nacionalidad | Canadiense , checo |
alma mater | Universidad de Waterloo Charles University |
Premios | Premio Beale-Orchard-Hays (2000) [1] Docteur Honoris Causa, Université de la Méditerranné (2003) Premio Frederick W. Lanchester (2007) [2] Premio Teórico John von Neumann (2015) [3] |
Carrera científica | |
Campos | Matemáticas , Ciencias de la Computación , Investigación de Operaciones |
Instituciones | Universidad de Concordia |
Asesor de doctorado | Crispin Nash-Williams |
Estudiantes de doctorado | David Avis (Stanford 1977) Bruce Reed (McGill 1986) |
Biografía
Chvátal nació en Praga en 1946 y se licenció en matemáticas en la Universidad Charles 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ó cargos en la Universidad McGill (1971 y 1978-1986), Universidad de Stanford (1972 y 1974-1977), la Université de Montréal (1972-1974 y 1977-1978) y la Rutgers University (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.
Investigar
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:
- Su primera publicación matemática, a la edad de 19 años, se refería a gráficos dirigidos que no pueden mapearse a sí mismos mediante ningún homomorfismo de gráfico no trivial [9].
- Otro resultado de la teoría de gráficos de Chvátal fue la construcción en 1970 del gráfico sin triángulos más pequeño posible que es 4- cromático y 4- regular , ahora conocido como el gráfico de Chvátal . [4] [10]
- A 1972 papel [11] relativa ciclos hamiltonianos a la conectividad y el conjunto independiente máximo tamaño de un gráfico, ganado Chvátal su número Erdős de 1. Específicamente, si existe un s tal que un gráfico dado es s - vértice-conectado y no tiene ( s + 1) -vertex conjunto independiente, la gráfica debe ser hamiltoniana. Avis y col. [4] cuenta 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 dureza de los gráficos , una medida de la conectividad de los gráficos que está estrechamente relacionada con la existencia de ciclos hamiltonianos . Un gráfico es t -tough 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 en, como máximo, tantas piezas como el número de vértices eliminados, por lo que los gráficos hamiltonianos son difíciles de 1. Chvátal conjeturó que las gráficas de 3/2-difíciles, y luego las gráficas de 2-difíciles, son siempre hamiltonianas; A pesar de que investigadores posteriores encontraron contraejemplos de 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 equivalentemente hipergráficos , un tema que ya aparece en su doctorado. tesis, donde también estudió la teoría de Ramsey .
- En una conjetura de 1972 que Erdős llamó "sorprendente" y "hermosa", [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 de intersección por pares más grande 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 codicioso proporciona buenas aproximaciones a la solución óptima, generalizando los resultados anteriores no ponderados de David S. Johnson (J. Comp. Sys. Sci. 1974 ) y László Lovász (Matemáticas discretas. 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 estudiaba 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 máximos independientes 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, Linear Programming , que se publicó en 1983. [4]
Los planos de corte se encuentran en el corazón de la rama y el método de corte utilizado por los solucionadores eficientes para el problema del vendedor ambulante . Entre 1988 y 2005, el equipo de David L. Applegate , Robert E. Bixby , Vašek Chvátal y William J. Cook desarrollaron 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 algunos de los refinamientos del método de corte y rama de Concorde que condujeron 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, El problema del vendedor ambulante: un estudio computacional .
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 controlando el comportamiento del problema de subsecuencia común más largo en entradas aleatorias, [31] y por su trabajo con Endre Szemerédi en instancias difíciles para la demostración del teorema de resolución . [32]
Libros
- Vašek 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.CS1 maint: texto adicional: lista de autores ( enlace )
- David L. Applegate; Robert E. Bixby; Vašek 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-8.CS1 maint: texto adicional: lista de autores ( enlace )
Ver también
- Lista de personas de la Universidad de Waterloo
Referencias
- ^ 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.
- ^ a b c d e f Avis, D .; Bondy, A .; Cook, W .; Reed, B. (2007). "Vasek Chvatal: una breve introducción" (PDF) . Gráficos y Combinatoria . 23 : 41–66. CiteSeerX 10.1.1.127.5910 . doi : 10.1007 / s00373-007-0721-4 . S2CID 11121944 .
- ^ a b Vasek Chvátal es 'el profesor viajero' , Informe del jueves de Concordia, 10 de febrero de 2005.
- ^ Proyecto de genealogía matemática - Václav Chvátal
- ^ Vasek Chvatal galardonado con la cátedra de investigación de Canadá , Informe del jueves de Concordia, 23 de octubre de 2003.
- ^ Chvátal, Vašek (1997), "En elogio 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 contables y finitos" , Commentationes Mathematicae Universitatis Carolinae , 6 : 429–438.
- ^ Weisstein, Eric W. "Gráfico de Chvátal" . MathWorld .
- ^ 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, Chvátal's t 0 -tough conjetura (PDF)
- ^ Reseñas de matemáticas MR0369170
- ^ V. Chvátal ; David A. Klarner ; DE Knuth (1972), "Problemas seleccionados de investigación combinatoria" (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áficas débilmente hamiltonianas", 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 la 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 matemático, desconcertante largo, rinde lentamente. New York Times , 12 de marzo de 1991.
- ^ Artful Routes , Science News Online, 1 de enero de 2005.
- ^ Applegate, David; Bixby, Robert; Chvátal, Vašek ; Cook, William (1998), "Sobre la solución de problemas de los vendedores ambulantes" , Documenta Mathematica , Volumen extra 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 de características AMS por Joseph Malkevitch
- ^ Teorema de la galería de arte de Chvatal enCortar el nudo de Alexander Bogomolny
- ↑ Obsession , Numb3rs, Episodio 3, Temporada 2
- ^ Chvátal, Vašek (1993), "Notes on the Kolakoski Sequence" , DIMACS Technical Reports , TR: 93-84
- ^ Problemas peligrosos , Science News Online, 13 de julio de 2002.
- ^ Chvátal, Václav ; Sankoff, David (1975), "Las subsecuencias comunes más largas de dos secuencias aleatorias", Journal of Applied Probability , 12 (2): 306–315, doi : 10.2307 / 3212444 , JSTOR 3212444.
- ^ 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 " . MAA Reviews, Asociación Matemática de América .
enlaces externos
- Página de inicio de Chvátal