Václav Chvátal (2007)
|Alma mater|| University of Waterloo |
|Awards|| Beale–Orchard-Hays Prize (2000) |
Docteur Honoris Causa, Université de la Méditerranné (2003)
Frederick W. Lanchester Prize (2007)
John von Neumann Theory Prize (2015)
|Fields||Mathematics, Computer Science, Operations Research|
|Doctoral advisor||Crispin Nash-Williams|
|Doctoral students|| David Avis (Stanford 1977)|
Bruce Reed (McGill 1986)
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. He 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, where he studied under the supervision of Zdeněk Hedrlín.He fled Czechoslovakia in 1968, three days after the Soviet invasion, 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. 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 at Concordia (2004-2011) and the Canada Research Chair in Discrete Mathematics (2011-2014) till his retirement.
Chvátal first learned of graph theory in 1964, on finding a book by Claude Berge in a Pilsen bookstoreand much of his research involves 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.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. At Stanford in the 1970s, he began writing his popular textbook, Linear Programming, which was published in 1983.
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.The team was awarded The Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming in 2000 for their ten-page paper 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,for researching a self-describing digital sequence, for his work with David Sankoff on the Chvátal–Sankoff constants controlling the behavior of the longest common subsequence problem on random inputs, and for his work with Endre Szemerédi on hard instances for resolution theorem proving.
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if we have:
In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.
In combinatorics, the Dinitz theorem is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin.
The "happy ending problem" is the following statement:
In mathematics, the Erdős–Burr conjecture was a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Paul Erdős and Stefan Burr, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph.
Claude Jacques Berge was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory.
In 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 independent graphs.
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch.
In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph is 1-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum t for which it is t-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness.
In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.
Discrete Mathematics is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West.
In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal (1970).
John Adrian Bondy, a dual British and Canadian citizen, was a professor of graph theory at the University of Waterloo, in Canada. He is a faculty member of Université Lyon 1, France. Bondy is known for his work on Bondy–Chvátal theorem together with Václav Chvátal. His coauthors include Paul Erdős.
Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.
Paul Allen Catlin was a mathematician, professor of mathematics and Doctor of Mathematics, known for his valuable contributions to graph theory and number theory. He wrote one of the most cited papers in the series of chromatic numbers and Brooks' theorem, titled Hajós graph coloring conjecture: variations and counterexamples.
William John Cook is an American operations researcher and mathematician, and Professor of Applied Mathematics and Statistics at Johns Hopkins University, where he joined the faculty in 2018. He is a member of the National Academy of Engineering. He is known for his work on the traveling salesman problem and is one of the authors of the Concorde TSP Solver.
In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if G is a 2-vertex-connected graph, then the square of G is Hamiltonian. it is named after Herbert Fleischner, who published its proof in 1974.