Václav Chvátal

Václav (Vašek) Chvátal (Czech: [ˈvaːtslaf ˈxvaːtal]; born 20 July 1946^[1]) 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.^[2][3]

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,^[1] where he studied under the supervision of Zdeněk Hedrlín.^[4] He and his first wife Jarmila fled Czechoslovakia in 1968, three days after the Soviet invasion.^[3] 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.^[4][5] 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.^[1][3] 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,^[1][2] and, in 2000, the Beale–Orchard-Hays Prize for Excellence in Computational Mathematical Programming, an annual best-paper award from the Mathematical Programming Society.^[2][6]

Research

The Chvátal graph

Chvátal first learned of graph theory in 1964, on finding a book by Claude Berge in a Pilsen bookstore, and much of his research concerns graph theory:

• His first mathematical publication, at the age of 19, concerned directed graphs that cannot be mapped to themselves by any nontrivial graph homomorphism.^[4]
• 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.^[4]
• Another work on Hamiltonian cycles, relating them to the connectivity and maximum independent set size of a graph, earned Chvátal his Erdős number of 1. Specifically, if there exists an s such that a given graph is s-vertex-connected and has no (s + 1)-vertex independent set, the graph must be Hamiltonian. Avis et al.^[4] 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,^[4][7]

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,^[8] 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.^[4]

Chvátal first became interested in linear programming through the influence of Jack Edmonds while Chvátal was a student at Waterloo,^[4] and quickly recognized its importance for attacking combinatorial optimization problems; at Stanford in the 1970s, he worked on these problems with George Dantzig.^[4] 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.^[9]

Chvátal is also known for proving the art gallery theorem, for researching self-describing digital sequences,^[10] for his work with David Sankoff on the Chvátal–Sankoff constants controlling the behavior of the longest common subsequence problem on random inputs,^[11] and for finding hard instances for resolution theorem proving.^[12]

Books

• Chvátal, V. (1983). Linear Programming. W.H. Freeman. ISBN 978-0-7167-1587-0. 
• Berge, C. and Chvátal, V. (eds.) (1984). Topics on Perfect Graphs. Elsevier. ISBN 978-0-444-86587-8.  CS1 maint: Multiple names: authors list (link)
• Applegate, D. L.; Bixby, R. E.; Chvátal, V.; Cook, W. J. (2007). The Traveling Salesman Problem: A Computational Study. Princeton University Press. ISBN 978-0-691-12993-8.  CS1 maint: Multiple names: authors list (link)

References

External links

• Chvátal's home page