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

Speaker: Yuval Wigderson (ETH-ITS)

Thursday 24th October, 3:00 in Fine Hall 224.

Title: Spectral bounds on the independence number

Spectral graph theory provides us with a wide array of surprising results
which relate graph-theoretic parameters to linear-algebraic parameters of
associated matrices. Among the most well-known and useful of these is
Hoffman's ratio bound, which gives an upper bound on the independence number
of a graph in terms of its eigenvalues.

A closely related result is Cvetković's inertia bound, another inequality
relating the independence number and the eigenvalues of a graph. Despite its
similarity to the ratio bound, the inertia bound is much less
well-understood — until a few years ago, it was unknown whether this simple
inequality is always an equality! In this talk, I will survey what is known
about these two bounds, and will present a powerful new approach to
answering such questions.

Joint work with Matthew Kwan.

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

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