Václav Chvátal
Encyclopedia
Václav Chvátal (born 20 July 1946) (ˈvaːtslaf ˈ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.
Chvátal has published extensively on topics in graph theory
, combinatorics
, and combinatorial optimization
.
in 1946 and educated in mathematics at Charles University in Prague, where he studied under the supervision of Zdeněk Hedrlín. He and his wife Jarmila fled Czechoslovakia
in 1968, three days after the Soviet 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
. 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
.
in a Pilsen bookstore, and much of his research concerns graph theory:
Some of Chvátal's work concerns families of sets, or equivalently hypergraph
s, 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, 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.
Chvátal is also known for proving the art gallery theorem, for researching self-describing digital sequences, and for finding hard instances for resolution theorem proving
.
Canada Research Chair in Combinatorial Optimization.
Chvátal has published extensively on topics in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, and combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
.
Biography
Chvátal was born in PraguePrague
Prague is the capital and largest city of the Czech Republic. Situated in the north-west of the country on the Vltava river, the city is home to about 1.3 million people, while its metropolitan area is estimated to have a population of over 2.3 million...
in 1946 and educated in mathematics at Charles University in Prague, where he studied under the supervision of Zdeněk Hedrlín. He and his wife Jarmila fled Czechoslovakia
Czechoslovakia
Czechoslovakia or Czecho-Slovakia was a sovereign state in Central Europe which existed from October 1918, when it declared its independence from the Austro-Hungarian Empire, until 1992...
in 1968, three days after the Soviet invasion
Prague Spring
The Prague Spring was a period of political liberalization in Czechoslovakia during the era of its domination by the Soviet Union after World War II...
. He completed his Ph.D. in Mathematics at the University of Waterloo
University of Waterloo
The University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
, in only a single year, under the supervision of Crispin St. J. A. Nash-Williams
Crispin St. J. A. Nash-Williams
Crispin St. John Alvah Nash-Williams was a British and Canadian mathematician. His research interest was in the field of discrete mathematics, especially graph theory....
. Subsequently he took positions at McGill University
McGill University
Mohammed Fathy is a public research university located in Montreal, Quebec, Canada. The university bears the name of James McGill, a prominent Montreal merchant from Glasgow, Scotland, whose bequest formed the beginning of the university...
, the Université de Montréal
Université de Montréal
The Université de Montréal is a public francophone research university in Montreal, Quebec, Canada. It comprises thirteen faculties, more than sixty departments and two affiliated schools: the École Polytechnique and HEC Montréal...
, Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
, and Rutgers University
Rutgers University
Rutgers, The State University of New Jersey , is the largest institution for higher education in New Jersey, United States. It was originally chartered as Queen's College in 1766. It is the eighth-oldest college in the United States and one of the nine Colonial colleges founded before the American...
, 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
Alexander von Humboldt Foundation
The Alexander von Humboldt Foundation is a foundation set-up by the government of the Federal Republic and funded by the German Foreign Office, the Ministry of Education and Research, the Ministry of Economic Cooperation and Development and others for the promotion of international co-operation...
, and, in 2000, the Beale–Orchard-Hays Prize for Excellence in Computational Mathematical Programming, an annual best-paper award from the Mathematical Programming Society
Mathematical Programming Society
Known as the Mathematical Programming Society until 2010, the Mathematical Optimization Society is an international association of researchers active in optimization...
.
Research
Chvátal first learned of graph theory in 1964, on finding a book by Claude BergeClaude Berge
Claude Berge was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. He is particularly remembered for his famous conjectures on perfect graphs and for Berge's lemma, which states that a matching M in a graph G is maximum if and only if there is in...
in a Pilsen bookstore, and much of his research concerns graph theory:
- His first mathematical publication, at the age of 19, concerned directed graphDirected graphA directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s that cannot be mapped to themselves by any nontrivial graph homomorphismGraph homomorphismIn the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.-Definitions:...
. - In a 1973 paper, Chvátal introduced the concept of graph toughnessGraph toughnessIn graph theory, toughness is a measure of the connectivity of a graph. A graph is said to be -tough for a given real number if, for every integer , cannot be split into different connected components by the removal of fewer than vertices...
, 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 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-connectedK-vertex-connected graphIn graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
and has no (s + 1)-vertex independent set, the graph must be Hamiltonian. Avis et al. tell the story of Chvátal and ErdősPaul ErdosPaul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
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 graphTriangle-free graphIn the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
that is both 4-chromatic and 4-regularRegular graphIn graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
, now known as the Chvátal graphChvátal graphIn the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by .It is triangle-free: its girth is four. It is 4-regular: each vertex has exactly four neighbors. And its chromatic number is 4: it can be colored using four colors, but...
,
Some of Chvátal's work concerns families of sets, or equivalently hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
s, a subject already occurring in his Ph.D. thesis, where he also studied Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
.
- In 1979, he studied a weighted version of the set cover problemSet cover problemThe set covering problem is a classical question in computer science and complexity theory.It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms...
, and proved that a greedy algorithmGreedy algorithmA greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
provides good approximationsApproximation algorithmIn computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
to the optimal solution, generalizing previous unweighted results by David S. JohnsonDavid S. JohnsonDavid Stifler Johnson is a computer scientist specializing in algorithms and optimization. He is currently the head of the Algorithms and Optimization Department of AT&T Labs Research. He was awarded the 2010 Knuth Prize....
(J. Comp. Sys. Sci. 1974) and László LovászLászló LovászLászló Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
(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 subsetSubsetIn mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s, 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
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
through the influence of Jack Edmonds
Jack Edmonds
Jack R. Edmonds is a mathematician, regarded as one of the most important contributors to the field of combinatorial optimization...
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
George Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....
. It is also during this time that he wrote his popular textbook, Linear Programming. In 1984, he investigated the cutting-plane method
Cutting-plane method
In mathematical optimization, the cutting-plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts...
, based on linear programming for computing maximum independent sets. His later implementations of efficient solvers for the traveling salesman problem also use this method.
Chvátal is also known for proving the art gallery theorem, for researching self-describing digital sequences, and for finding hard instances for resolution theorem proving
Resolution (logic)
In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic...
.