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

Speaker: Liana Yepremyan (Emory U.)

Thursday 16th April, 3:00 in Fine Hall 224.

Title: Graphs with large fractional chromatic number and small Hall ratio

The Hall ratio of a graph G is the maximum of |V (H)|/\alpha(H) over
all subgraphs H of G. It is easy to see that the Hall ratio of a graph
is a lower bound for the fractional chromatic number. It has been asked
whether conversely, the fractional chromatic number is upper bounded by a
function of the Hall ratio, and this has been disproved. We prove a
conjecture of Walczak that there are graphs with arbitrarily large
fractional chromatic number and Hall ratio arbitrarily close to 2. The proof
uses probabilistic construction together with structural analysis. This is
best possible since odd cycles have Hall ratio greater than 2. 

Joint work with James Davies and  Meike Hatzel.

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

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