Václav Chvátal

Václav (Vašek) Chvátal (Czech: [ˈvaːtslaf ˈxvaːtal]) is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada, and a visiting professor at Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.

Václav Chvátal
Václav Chvátal (2020)
Born	(1946-07-20) 20 July 1946 (age 78) Prague
Nationality	Canadian, Czech
Alma mater	University of Waterloo Charles University
Known for	Chvátal graph Chvátal–Sankoff constants Bondy–Chvátal theorem Crossing number inequality Graph toughness
Awards	Beale–Orchard-Hays Prize (2000) [1] Docteur Honoris Causa, Université de la Méditerranné (2003) Frederick W. Lanchester Prize (2007) [2] John von Neumann Theory Prize (2015) [3]
Scientific career
Fields	Mathematics, Computer Science, Operations Research
Institutions	Concordia University
Doctoral advisor	Crispin Nash-Williams
Doctoral students	David Avis (Stanford 1977) Bruce Reed (McGill 1986)

Biography

Chvátal was born in 1946 in Prague and educated in mathematics at Charles University in Prague, where he studied under the supervision of Zdeněk Hedrlín.^[4] He fled Czechoslovakia in 1968, three days after the Soviet invasion,^[5] and completed his Ph.D. in Mathematics at the University of Waterloo, under the supervision of Crispin St. J. A. Nash-Williams, in the fall of 1970.^[4][6] Subsequently, he took positions at McGill University (1971 and 1978–1986), Stanford University (1972 and 1974–1977), the Université de Montréal (1972–1974 and 1977–1978), and Rutgers University (1986-2004) before returning to Montreal for the Canada Research Chair in Combinatorial Optimization ^[7][5] at Concordia (2004-2011) and the Canada Research Chair in Discrete Mathematics (2011-2014) till his retirement.

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 ^[8] and much of his research involves 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^[9]
• 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][10]
• A 1972 paper ^[11] relating Hamiltonian cycles to 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."
• In a 1973 paper,^[12] 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, for every k greater than 1, the removal of fewer than tk vertices leaves fewer than k connected components in the remaining subgraph. For instance, in a graph with a Hamiltonian cycle, the removal of any nonempty 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.^[13]

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 a 1972 conjecture that Erdős called "surprising" and "beautiful",^[14] and that remains open (with a $10 prize offered by Chvátal for its solution) ^[15][16] 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.
• In 1979,^[17] 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).

Chvátal first became interested in linear programming through the influence of Jack Edmonds while Chvátal was a student at Waterloo.^[4] He quickly recognized the importance of cutting planes for attacking combinatorial optimization problems such as computing maximum independent sets and, in particular, introduced the notion of a cutting-plane proof.^{[18][19][20][21]} At Stanford in the 1970s, he began writing his popular textbook, Linear Programming, which was published in 1983.^[4]

Cutting planes lie at the heart of the branch and cut method used by efficient solvers for the traveling salesman problem. Between 1988 and 2005, the team of David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook developed one such solver, Concorde.^[22][23] The team was awarded The Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming in 2000 for their ten-page paper ^[24] enumerating some of Concorde's refinements of the branch and cut method that led to the solution of a 13,509-city instance and it was awarded the Frederick W. Lanchester Prize in 2007 for their book, The Traveling Salesman Problem: A Computational Study.

Chvátal is also known for proving the art gallery theorem,^{[25][26][27][28]} for researching a self-describing digital sequence,^[29][30] for his work with David Sankoff on the Chvátal–Sankoff constants controlling the behavior of the longest common subsequence problem on random inputs,^[31] and for his work with Endre Szemerédi on hard instances for resolution theorem proving.^[32]

Books

• Vašek Chvátal (1983). Linear Programming. W.H. Freeman. ISBN 978-0-7167-1587-0.. Japanese translation published by Keigaku Shuppan, Tokyo, 1986.
• C. Berge and V. Chvátal (eds.) (1984). Topics on Perfect Graphs. Elsevier. ISBN 978-0-444-86587-8. {{cite book}}: |author= has generic name (help)
• David L. Applegate; Robert E. Bixby; Vašek Chvátal; William J. Cook (2007). The Traveling Salesman Problem: A Computational Study. Princeton University Press. ISBN 978-0-691-12993-8.^[33]
• Vašek Chvátal, ed. (2011). Combinatorial Optimization: Methods and Applications. IOS Press. ISBN 978-1-60750-717-8. Archived from the original on 2017-03-21. Retrieved 2017-03-22.
• Vašek Chvátal (2021). Discrete Mathematical Charms of Paul Erdős. A Simple Introduction. Cambridge University Press. ISBN 978-1-108-92740-6.

See also

• List of University of Waterloo people

References

1. Past Winners of The Beale-Orchard-Hays Prize.
2. Frederick W. Lanchester Prize 2007 Archived 2016-08-20 at the Wayback Machine, retrieved 2017-03-19.
3. John von Neumann Theory Prize 2015 Archived 2016-08-20 at the Wayback Machine, retrieved 2017-03-19.
4. Avis, D.; Bondy, A.; Cook, W.; Reed, B. (2007). "Vasek Chvatal: A Short Introduction" (PDF). Graphs and Combinatorics. 23: 41–66. CiteSeerX 10.1.1.127.5910. doi:10.1007/s00373-007-0721-4. S2CID 11121944.
5. Vasek Chvátal is ‘the travelling professor’, Concordia's Thursday Report, Feb. 10, 2005.
6. The Mathematics Genealogy Project – Václav Chvátal
7. Vasek Chvatal awarded Canada Research Chair, Concordia's Thursday Report, Oct. 23, 2003.
8. Chvátal, Vašek (1997), "In praise of Claude Berge", Discrete Mathematics, 165–166: 3–9, doi:10.1016/s0012-365x(96)00156-2,
9. Chvátal, Václav (1965), "On finite and countable rigid graphs and tournaments", Commentationes Mathematicae Universitatis Carolinae, 6: 429–438.
10. Weisstein, Eric W. "Chvátal Graph". MathWorld.
11. V. Chvátal; P. Erdős (1972), "A note on Hamiltonian circuits" (PDF), Discrete Mathematics, 2 (2): 111–113, doi:10.1016/0012-365x(72)90079-9,
12. Chvátal, V. (1973), "Tough graphs and hamiltonian circuits", Discrete Mathematics, 5 (3): 215–228, doi:10.1016/0012-365x(73)90138-6,
13. Lesniak, Linda, Chvátal's t₀-tough conjecture (PDF)
14. Mathematical Reviews MR0369170
15. V. Chvátal; David A. Klarner; D.E. Knuth (1972), "Selected combinatorial research problems" (PDF), Computer Science Department, Stanford University, Stan-CS-TR-72-292: Problem 25
16. Chvátal, Vašek, A conjecture in extremal combinatorics
17. "A greedy heuristic for the set-covering problem", Mathematics of Operations Research, 1979
18. Chvátal, Václav (1973), "Edmonds polytopes and weakly hamiltonian graphs", Mathematical Programming, 5: 29–40, doi:10.1007/BF01580109, S2CID 8140217,
19. Chvátal, Václav (1973), "Edmonds polytopes and a hierarchy of combinatorial problems", Discrete Mathematics, 4 (4): 305–337, doi:10.1016/0012-365x(73)90167-2,
20. Chvátal, Václav (1975), "Some linear programming aspects of combinatorics" (PDF), Congressus Numerantium, 13: 2–30,
21. Chvátal, V. (1975), "On certain polytopes associated with graphs", Journal of Combinatorial Theory, Series B, 18 (2): 138–154, doi:10.1016/0095-8956(75)90041-6.
22. Math Problem, Long Baffling, Slowly Yields. New York Times, Mar. 12, 1991.
23. Artful Routes, Science News Online, Jan. 1, 2005.
24. Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William (1998), "On the Solution of Traveling Salesman Problems", Documenta Mathematica, Extra Volume ICM III, archived from the original on 2020-07-27, retrieved 2017-03-22
25. Weisstein, Eric W. "Art Gallery Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ArtGalleryTheorem.html
26. Diagonals: Part I 4. Art gallery problems, AMS Feature Column by Joseph Malkevitch
27. Chvatal's Art Gallery Theorem in Alexander Bogomolny's Cut the Knot
28. Obsession Archived 2017-03-20 at the Wayback Machine, Numb3rs, Episode 3, Season 2
29. Chvátal, Vašek (1993), "Notes on the Kolakoski Sequence", DIMACS Technical Reports, TR: 93-84
30. Dangerous Problems, Science News Online, Jul. 13, 2002.
31. Chvátal, Václav; Sankoff, David (1975), "Longest common subsequences of two random sequences", Journal of Applied Probability, 12 (2): 306–315, doi:10.2307/3212444, JSTOR 3212444, S2CID 250345191.
32. Chvátal, Vašek; Szemerédi, Endre (1988), "Many hard examples for resolution", Journal of the ACM, 35 (4): 759–768, doi:10.1145/48014.48016, S2CID 2526816.
33. Borchers, Brian (March 25, 2007). "Review of The Traveling Salesman Problem: A Computational Study". MAA Reviews, Mathematical Association of America. Archived from the original on April 23, 2023. Retrieved June 21, 2021.

External links

• Chvátal's home page