# Combinatorics Seminar

When: Sunday, February 16, 10am

Where: Schreiber 309

Speaker: Danny Vilenchik, Weizmann

Title: Chasing the k-colorability threshold

## Abstract:

In this talk I will present a substantially improved lower bound on
the $k$-colorability threshold of the random graph $G(n,m)$ with $n$
vertices and $m$ edges. The new lower bound is 1.39 less than the
$2k\ln k-\ln k$ first-moment upper bound (and 0.39 less than the 2k\ln
k-\ln k-1 physics conjecture). By comparison, the best previous bounds
left a gap of about 2+\ln k, unbounded in terms of the number of colors
[Achlioptas, Naor: Annals of Mathematics 2005]. Furthermore, we prove
that, in a precise sense, our lower bound marks the so-called condensation
phase transition predicted on the basis of physics arguments. Our proof
technique is a novel approach to the second moment method, inspired by
physics conjectures on the geometry of the set of $k$-colorings of the
random graph.

Joint work with Amin Coja-Oghlan. Paper appeared in FOCS 2013.

redesigned by barak soreq