Václav Chvátal

Václav Chvátal

Václav Chvátal (2007)
Born (1946-07-20) 20 July 1946
Nationality Czech
Fields Mathematics
Institutions Concordia University
Alma mater University of Waterloo
Charles University
Doctoral advisor Crispin Nash-Williams
Doctoral students David Avis
Ryan Hayward
Bruce Reed
Notable awards Frederick W. Lanchester Prize (2007)

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.


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]


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:

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.

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]



  1. 1 2 3 4 Biography included with abstract for talk by Chvátal at Tufts Univ., 2000.
  2. 1 2 3 Vasek Chvatal awarded Canada Research Chair, Concordia's Thursday Report, Oct. 23, 2003.
  3. 1 2 3 Vasek Chvátal is ‘the travelling professor’, Concordia's Thursday Report, Feb. 10, 2005.
  4. 1 2 3 4 5 6 7 8 9 Avis, D.; Bondy, A.; Cook, W.; Reed, B. (2007). "Vasek Chvatal: A Short Introduction" (PDF). Graphs and Combinatorics. 23: 41–66. doi:10.1007/s00373-007-0721-4..
  5. The Mathematics Genealogy Project – Václav Chvátal.
  6. The Beale-Orchard-Hays Prize: past winners.
  7. Weisstein, Eric W. "Chvátal Graph". MathWorld.
  8. "A greedy heuristic for the set-covering problem", Mathematics of Operations Research, 1979: 554 citations in Google Scholar.
  9. Math Problem, Long Baffling, Slowly Yields. New York Times, Mar. 12, 1991. Artful Routes, Science News Online, Jan. 1, 2005.
  10. Dangerous Problems, Science News Online, Jul. 13, 2002.
  11. Chvatal, Václáv; Sankoff, David (1975), "Longest common subsequences of two random sequences", Journal of Applied Probability, 12: 306–315, doi:10.2307/3212444, MR 0405531.
  12. "Many hard examples for resolution" (with E. Szemerédi), J. ACM, 1988: 241 citations in Google Scholar.
This article is issued from Wikipedia - version of the 8/19/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.