Václav Chvátal | |
---|---|

Václav Chvátal (2007) | |

Born | |

Nationality | Canadian, Czech |

Alma mater | University of Waterloo Charles University |

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) |

**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.^{ [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.

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] }

- 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.CS1 maint: extra text: authors list (link) - 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. - Vašek Chvátal (ed.) (2011).
*Combinatorial Optimization: Methods and Applications*. IOS Press. ISBN 978-1-60750-717-8.CS1 maint: extra text: authors list (link)

**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.

- ↑ Past Winners of The Beale-Orchard-Hays Prize.
- ↑ Frederick W. Lanchester Prize 2007, retrieved 2017-03-19.
- ↑ John von Neumann Theory Prize 2015, retrieved 2017-03-19.
- 1 2 3 4 5 6 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. - 1 2 Vasek Chvátal is ‘the travelling professor’, Concordia's Thursday Report, Feb. 10, 2005.
- ↑ The Mathematics Genealogy Project – Václav Chvátal
- ↑ Vasek Chvatal awarded Canada Research Chair, Concordia's Thursday Report, Oct. 23, 2003.
- ↑ Chvátal, Vašek (1997), "In praise of Claude Berge",
*Discrete Mathematics*, 165-166: 3–9, doi:10.1016/s0012-365x(96)00156-2 , - ↑ Chvátal, Václav (1965), "On finite and countable rigid graphs and tournaments",
*Commentationes Mathematicae Universitatis Carolinae*,**6**: 429–438. - ↑ Weisstein, Eric W. "Chvátal Graph".
*MathWorld*. - ↑ 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 , - ↑ Chvátal, V. (1973), "Tough graphs and hamiltonian circuits",
*Discrete Mathematics*,**5**(3): 215–228, doi:10.1016/0012-365x(73)90138-6 , - ↑ Lesniak, Linda,
*Chvátal's t*(PDF)_{0}-tough conjecture - ↑ Mathematical Reviews MR0369170
- ↑ 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 - ↑ Chvátal, Vašek,
*A conjecture in extremal combinatorics* - ↑ "A greedy heuristic for the set-covering problem", Mathematics of Operations Research, 1979
- ↑ Chvátal, Václav (1973), "Edmonds polytopes and weakly hamiltonian graphs",
*Mathematical Programming*,**5**: 29–40, doi:10.1007/BF01580109 , - ↑ 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 , - ↑ Chvátal, Václav (1975), "Some linear programming aspects of combinatorics" (PDF),
*Congressus Numerantium*,**13**: 2–30, - ↑ 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 . - ↑ Math Problem, Long Baffling, Slowly Yields. New York Times, Mar. 12, 1991.
- ↑ Artful Routes, Science News Online, Jan. 1, 2005.
- ↑ Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William (1998), "On the Solution of Traveling Salesman Problems",
*Documenta Mathematica*, Extra Volume ICM III - ↑ Weisstein, Eric W. "Art Gallery Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ArtGalleryTheorem.html
- ↑ Diagonals: Part I 4. Art gallery problems, AMS Feature Column by Joseph Malkevitch
- ↑ Chvatal's Art Gallery Theorem in Alexander Bogomolny's Cut the Knot
- ↑ Obsession, Numb3rs, Episode 3, Season 2
- ↑ Chvátal, Vašek (1993), "Notes on the Kolakoski Sequence",
*DIMACS Technical Reports*, TR: 93-84 - ↑ Dangerous Problems, Science News Online, Jul. 13, 2002.
- ↑ 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 . - ↑ 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 .

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.