Department of Mathematics, University of South Carolina

Fri 24 Oct 2014, 3:00pm
Department Colloquium
MATX 1100

A new asymptotic enumeration technique: the Lovasz Local Lemma

MATX 1100
Fri 24 Oct 2014, 3:00pm4:00pm
Abstract
The lopsided version of the Lovasz Local Lemma gives asymptotically tight lower boundsfor a number of enumeration problems. In the configuration model matching upper bounds are available. In this way a number of asymptotic enumeration results, mostly due to Wormald and McKay, can be proved in an alternative way. A new result is asymptotic enumeration of graphs with respect to degree sequence and girth. A classical probabilistic result of Paul Erdos showed the existence of graphs with arbitrary large girth and chromatic number. If the degree sequence satisfies some mild conditions, we show that almost all graphs with this degree sequence and prescribed girth have high chromatic number.
This is joint work with Lincoln Lu.
hide

Seminar Information Pages

Note for Attendees
Refreshments will be served at 2:45pm in the Math Lounge area, MATH 125 before the colloquium.