Print Friendly printer friendly
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:00pm-4:00pm


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.

Note for Attendees

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