Phase Transition for the mixing time of Glauber Dynamics on Regular Trees at Reconstruction

Juan Vera Tilburg

Description

Phase Transition for the mixing time of Glauber Dynamics on Regular Trees at Reconstruction: Colorings and Independent Sets. Juan Vera Tilburg University, Netherlands JOINT WORK WITH Ricardo Restrepo†, Daniel Stefankovic‡, Eric Vigoda†, Linji Yang†, Prasad Tetali† †Georgia Tech, ‡Rochester LIPN: CALIN Seminaire de combinatoire, April 12, 2011 Juan Vera (Tilburg) Phase Transition at Reconstruction LIPN: CALIN, Apr 2010 1 / 23

• random colorings


• efficient sampler yields


• ferromagnetic potts model


• given xt


• maximum degree ∆

Sujets

• Tilburg

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 6
• Langue: English

Extrait

PhaseTransitionforthemixingtimeofGlauber DynamicsonRegularTreesatReconstruction: ColoringsandIndependentSets. uJna JuanVera TilburgUniversity,Netherlands J OINTWORKWITH RicardoRestrepo † ,DanielStefankovic ‡ ,EricVigoda † , LinjiYang † ,PrasadTetali † eVarT(liubgr) † GeorgiaTech, ‡ Rochester LIPN:CALIN Se ´ minairedecombinatoire, April12,2011 hPsaerTnaisitnotaeRocsnrtcuitnoILNP:ACIL,NpAr02011/32

Coloringgraphs neviG AgraphG =( V , E ) onnverticesandmaximumdegree Δ Asetofkcolors Ak-coloringofGisanassignmentf : V→{1 ,..., k}suchthat forall(u,v) ∈ E,f(u) 6 =f(v) GivenagraphwithmaximumdegreeΔ Howtoconstructk-colorings I Trivialfork>Δ Howtosample(uniformlyat)randomk-colorings I Non-trivialevenfork>Δ uJnaeVarT(liubgr)hPsaerTnaisitnotaeRocsnrtcuitnoILNP:ACIL,NpAr02012/32

Coloringgraphs iGnev AgraphG =( V , E ) onnverticesandmaximumdegree Δ Asetofkcolors Ak-coloringofGisanassignmentf : V→{1 ,..., k}suchthat forall(u,v) ∈ E,f(u) 6 =f(v) GivenagraphwithmaximumdegreeΔ Howtoconstructk-colorings I Trivialfork>Δ Howtosample(uniformlyat)randomk-colorings I Non-trivialevenfork>Δ uJnaeVarT(liubgr)hPsaerTnaisitnotaeRocsnrtcuitnoILNP:ACIL,NpAr02012/32

RandomColoringgraphs Whyareweinterested? Howtosample(uniformlyat)randomk-colorings? Howdorandomk-coloringslook? RandomcoloringsistheGibbsdistributionfor(zero-temperature) anti-ferromagneticPottsmodel. Efficientsampleryieldsapproximationalgorithmforcounting colorings,whichis#P-complete. uJnaeVarT(liubgr)hPsaerTnaisitnotaeRocsnrtcuitnoILNP:ACIL,NpAr02013/32