Vašek Chvátal

Professor Emeritus (since September 1, 2014)
Department of Computer Science and Software Engineering
Concordia University
1455 De Maisonneuve Blvd. West
Montréal, Québec H3G 1M8, Canada

Email: c h v a t a l (at) c s e (dot) c o n c o r d i a (dot) c a            

I am in retirement.
I am not taking on any graduate students.
I am not taking on any postdocs.
I am in retirement.


New book: The Discrete Mathematical Charms of Paul Erdős (also at Amazon)

Here is this book's preface, here is a recording of its launch, here are its errata, and here are its reviews from MathSciNet, from The Mathematical Gazette, from the Zentralblatt, from the Notices of the AMS.
Association of American Publishers has selected it as a finalist of its 2022 PROSE (Professional and Scholarly Excellence) Awards in the Mathematics category.

My research

My initial research interests were in graph theory (with an emphasis on hamiltonian cycles and later on perfect graphs) and in combinatorics (with an emphasis on extremal problems). Then they extended to analysis of algorithms (with an emphasis on cutting-plane proofs) and to operations research (with an emphasis on linear programming). Between 1988 and 2005, I was mostly preoccupied by the traveling salesman problem. In December 2004, I began learning about EEG recordings of epileptic seizures and then I gradually developed a passive interest in computational neuroscience. Eventually, this resulted in a joint paper on the relationship between McCulloch-Pitts brains and pseudorandom functions.

In 2004, I moved to Concordia as a Canada Research Chair (first CRC in Combinatorial Optimization from 2004 till 2011 and then CRC in Discrete Mathematics from 2011 till my retirement in 2014). With my friend Najiba Sbihi, I organized a Séminaire de Mathématiques Supérieures / NATO Advanced Study Institute Combinatorial Optimization: Methods and Applications which took place on 19 -- 30 June 2006 in Montreal. On my own, I organized a workshop Hybrid methods and branching rules in combinatorial optimization, which took place on 18 -- 22 September 2006 in Montreal. At the end of September 2006, I launched ConCoCO (Concordia Computational Combinatorial Optimization) research group; its last session was held on 26 June 2014. In June 2010, I ran a Concordia's summer camp in mathematics and computer science.

Right now I am most interested in the possibility of generalizing the geometrical De Bruijn-Erdős theorem to finite metric spaces .

Here are my list of publications with a few links to related web pages, my course notes, and slides for my talks.

Des chercheurs qui cherchent, on en trouve.
Des chercheurs qui trouvent, on en cherche.

Attributed to Charles de Gaulle (1890 -- 1970)