BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Probability
SUMMARY:Improved bounds for sampling colorings of sparse r
andom graphs - Charis Efthymiou (Frankfurt)
DTSTART;TZID=Europe/London:20171128T161500
DTEND;TZID=Europe/London:20171128T171500
UID:TALK86481AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/86481
DESCRIPTION:We study the mixing properties of the single-site
Markov chain known\nas the Glauber dynamics for sa
mpling k-colorings of a sparse random\ngraph G(n\,
d/n) for constant d. The best known rapid mixing
results\nfor general graphs are in terms of the m
aximum degree \\Delta of the\ninput graph G and ho
ld when k>11\\Delta/6 for all G. Improved results
\nhold when k>\\alpha\\Delta for graphs with girth
=>5 and \\Delta\nsufficiently large where \\alpha
\\approx 1.7632... is the root of\n\\alpha=\\exp(
1/\\alpha)\; further improvements on the constant
\\alpha\nhold with stronger girth and maximum degr
ee assumptions.\n\nFor sparse random graphs the ma
ximum degree is a function of n and the\ngoal is t
o 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 sufficiently 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 condition was improved to k
>3d by\nYin and Zhang (2016) using non-MCMC method
s.\n\nHere we prove rapid mixing when k>\\alpha d
where $\\alpha\\approx\n1.7632... is the same cons
tant as above. Moreover we obtain O(n^{3})\nmixing
time of the Glauber dynamics\, while in previous
rapid mixing results\nthe exponent was an increasi
ng function in d. As in previous results\nfor rand
om graphs our proof analyzes an appropriately defi
ned block\ndynamics to ``hide'' high-degree vertic
es. One new aspect in our\nimproved approach is
utilizing so-called local uniformity properties\nf
or the analysis of block dynamics. To analyze the
``burn-in'' phase\nwe prove a concentration inequ
ality for the number of disagreements\npropagating
in large blocks.\n\nThis is a joint work with Tom
Hayes\, Daniel Stefankovic and Eric Vigoda.
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0W
B
CONTACT:Perla Sousi
END:VEVENT
END:VCALENDAR