Václav Chvátal

Václav (Vašek) Chvátal (born 1946 [http://www.ece.tufts.edu/colloquia/archives/fall00/perfectGraphs.html Biography included with abstract for talk by Chvátal at Tufts Univ., 2000] .] ) (pronounced|ˈvaːt͡slaf ˈxvaːtal) is a professor in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Canada, where he holds the
Canada Research Chair in Combinatorial Optimization. [http://ctr.concordia.ca/2003-04/oct_23/01-chvatal/index.shtml Vasek Chvatal awarded Canada Research Chair] , Concordia's Thursday Report, Oct. 23, 2003.] [http://ctr.concordia.ca/2004-05/feb_10/01/ Vasek Chvátal is ‘the travelling professor’] , Concordia's Thursday Report, Feb. 10, 2005.]

Chvátal has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.

Biography

Chvátal was born in Prague in 1946 and educated in mathematics at Charles University in Prague, where he studied under the supervision of Zdeněk Hedrlín.citation|first1=D.|last1=Avis|authorlink1=David Avis|first2=A.|last2=Bondy|first3=W.|last3=Cook|first4=B.|last4=Reed|title=Vasek Chvatal: A Short Introduction|journal=Graphs and Combinatorics|volume=23|year=2007|pages=41–66|url=http://cgm.cs.mcgill.ca/~avis/doc/avis/ABCR07.pdf.] He and his wife Jarmila fled Czechoslovakia in 1968, three days after the Russian invasion. He completed his Ph.D. in Mathematics at the University of Waterloo, in only a single year, under the supervision of Crispin St. J. A. Nash-Williams. [ [http://genealogy.math.ndsu.nodak.edu/html/id.phtml?id=37109 The Mathematics Genealogy Project – Václav Chvátal] .] Subsequently he took positions at McGill University, the Université de Montréal, Stanford University, and Rutgers University, where he remained for 18 years before returning to Canada for his position at Concordia. While at Rutgers, Chvátal won in 1988 the Alexander von Humboldt Distinguished Senior Scientist Award, a visiting professorship in Germany given to approximately 100 scientists by the Alexander von Humboldt Foundation, and, in 2000, the Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming, an annual best-paper award from the Mathematical Programming Society. [ [http://www.mathprog.org/prz/boh.htm The Beale-Orchard-Hays Prize: past winners] .]

Research

Chvátal first learned of graph theory in 1964, on finding a book by Claude Berge in a Pilsen bookstore, and his first mathematical publication, at the age of 19, concerned directed graphs that cannot be mapped to themselves by any nontrivial graph homomorphism. In a 1973 paper, Chvátal introduced the concept of graph toughness, a measure of graph connectivity that is closely connected to the existence of Hamiltonian cycles. A graph is "t"-tough if the removal of fewer than "kt" vertices leaves fewer than "k" connected components in the remaining subgraph. For instance, in a graph with a Hamiltonian cycle, the removal of any set of vertices partitions the cycle into at most as many pieces as the number of removed vertices, so Hamiltonian graphs are 1-tough. Chvátal conjectured that 3/2-tough graphs, and later that 2-tough graphs, are always Hamiltonian; despite later researchers finding counterexamples to these conjectures, it still remains open whether some constant bound on the graph toughness is enough to guarantee Hamiltonicity. Another work on Hamiltonian cycles, relating it to the connectivity and maximum independent set size of a graph, earned Chvátal his Erdős number of 1; Avis et al. tell the story of Chvátal and Erdős working out this result over the course of a long road trip, and later thanking Louise Guy "for her steady driving." Another graph-theoretic result of Chvátal was the 1970 construction of the smallest possible triangle-free graph that is both 4-chromatic and 4-regular, now known as the Chvátal graph, [MathWorld | title = Chvátal Graph | urlname = ChvatalGraph]

Some of Chvátal's work concerns families of sets, or equivalently hypergraphs, a subject already occurring in his Ph.D. thesis, where he also studied Ramsey theory. In 1979, ["A greedy heuristic for the set-covering problem", Mathematics of Operations Research, 1979: 554 citations in Google Scholar.] he studied a weighted version of the set cover problem, and proved that a greedy algorithm provides good approximations to the optimal solution, generalizing previous unweighted results by David S. Johnson (J. Comp. Sys. Sci. 1974) and László Lovász (Discrete Math. 1975). In a conjecture that Erdős called "surprising" and "beautiful", and that remains open (with a $10 prize offered by Chvátal for its solution) he suggested that, in any family of sets closed under the operation of taking subsets, the largest pairwise-intersecting subfamily may always be found by choosing an element of one of the sets and keeping all sets containing that element.

Chvátal first became interested in linear programming through the influence of Jack Edmonds while Chvátal was a student at Waterloo, and quickly recognized its importance for attacking combinatorial optimization problems; at Stanford in the 1970s, he worked on these problems with George Dantzig. It is also during this time that he wrote his popular textbook, "Linear Programming". In 1984, he investigated the cutting-plane method, based on linear programming for computing maximum independent sets. His later implementations of efficient solvers for the traveling salesman problem also use this method. [Math Problem, Long Baffling, Slowly Yields. New York Times, Mar. 12, 1991. [http://www.sciencenews.org/articles/20050101/mathtrek.asp Artful Routes] , Science News Online, Jan. 1, 2005.]

Chvátal is also known for proving the art gallery theorem, for researching self-describing digital sequences, [ [http://www.sciencenews.org/articles/20020713/mathtrek.asp Dangerous Problems] , Science News Online, Jul. 13, 2002.] and for finding hard instances for resolution theorem proving. ["Many hard examples for resolution" (with E. Szemerédi), J. ACM, 1988: 241 citations in Google Scholar.]

Books

*cite book
author = Chvátal, V.
title = Linear Programming
publisher = W.H. Freeman
year = 1983
id = ISBN 978-0716715870

*cite book
author = Berge, C. and Chvátal, V. (eds.)
title = Topics on Perfect Graphs
publisher = Elsevier
year = 1984
id = ISBN 978-0444865878

*cite book
author = Applegate, D. L.; Bixby, R. E.; Chvátal, V.; Cook, W. J.
title = The Traveling Salesman Problem: A Computational Study
publisher = Princeton University Press
year = 2007
id = ISBN 978-0691129938

External links

* [http://users.encs.concordia.ca/~chvatal/ Chvátal's home page]

References