***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Yuval Wigderson (ETH Zurich)

Thursday 5th March, 3:00 in Fine Hall 224.

Title: Triangle-free graphs and the odd Hadwiger conjecture

Hadwiger's conjecture, first formulated in 1943, is a vast generalization of the
four-color theorem, and remains one of the central open problems in graph
theory. An even stronger statement, known as the odd Hadwiger conjecture, was
proposed in 1993 by Gerards and Seymour. For many decades, progress on one
problem was quickly followed by progress on the other, and recent developments
indicate that Hadwiger's conjecture and its odd variant are very closely linked.

However, as it turns out, the odd Hadwiger conjecture is false. The key
ingredient to the counterexamples is a new random model of triangle-free graphs,
which arose in the recent breakthrough work of Hefty et al. on off-diagonal
Ramsey numbers. In this talk, I will describe this construction, and sketch how
it can be used to disprove the odd Hadwiger conjecture. 

Based on joint work with Marcus Kühn, Lisa Sauermann, and Raphael Steiner. 

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)