BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Improved bounds for sampling colorings of sparse random graphs - C
 haris Efthymiou (Frankfurt)
DTSTART:20171128T161500Z
DTEND:20171128T171500Z
UID:TALK86481@talks.cam.ac.uk
CONTACT:Perla Sousi
DESCRIPTION:We study the mixing properties of the single-site Markov chain
  known\nas the Glauber dynamics for sampling k-colorings of a sparse rando
 m\ngraph G(n\,d/n) for constant d.  The best known rapid mixing results\nf
 or general graphs  are in terms of the maximum degree \\Delta of the\ninpu
 t graph G and hold when k>11\\Delta/6 for all G.  Improved results\nhold w
 hen k>\\alpha\\Delta for graphs with girth =>5 and \\Delta\nsufficiently l
 arge where \\alpha\\approx 1.7632...  is the root of\n\\alpha=\\exp(1/\\al
 pha)\; further improvements on the constant \\alpha\nhold with stronger gi
 rth and maximum degree assumptions.\n\nFor sparse random graphs the maximu
 m degree is a function of n and the\ngoal is to obtain results in terms of
  the expected degree d.  The\nfollowing rapid mixing results for G(n\,d/n)
  hold with high probability\nover the choice\nof the random graph  for suf
 ficiently large constant d.  Mossel and\nSly (2009) proved rapid mixing fo
 r constant k\, and Efthymiou (2014)\nimproved this to k linear in~d. The c
 ondition was improved to k>3d by\nYin and Zhang (2016) using non-MCMC meth
 ods.\n\nHere we prove rapid mixing when k>\\alpha d where $\\alpha\\approx
 \n1.7632... is the same constant as above. Moreover we obtain O(n^{3})\nmi
 xing time of the Glauber dynamics\, while in previous rapid mixing results
 \nthe exponent was an increasing function in d. As in previous results\nfo
 r random graphs our proof analyzes an appropriately defined block\ndynamic
 s to ``hide'' high-degree vertices.  One new aspect in our\nimproved  appr
 oach is utilizing so-called local uniformity properties\nfor the analysis 
 of block dynamics. To analyze the ``burn-in'' phase\nwe  prove a concentra
 tion inequality for the number of disagreements\npropagating in large bloc
 ks.\n\nThis is a joint work with Tom Hayes\, Daniel Stefankovic and Eric V
 igoda.
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR