//img.uscri.be/pth/dc68cee3715158ac55af0293303bf9995c4a998a
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

De
44 pages
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 ∆


Voir plus Voir moins
PhaseTransitionforthemixingtimeofGlauberDynamicsonRegularTreesatReconstruction:ColoringsandIndependentSets.uJnaJuanVeraTilburgUniversity,NetherlandsJOINTWORKWITHRicardoRestrepo,DanielStefankovic,EricVigoda,LinjiYang,PrasadTetalieVarT(liubgr)GeorgiaTech,RochesterLIPN:CALINSe´minairedecombinatoire,April12,2011hPsaerTnaisitnotaeRocsnrtcuitnoILNP:ACIL,NpAr02011/32
ColoringgraphsneviGAgraphG=(V,E)onnverticesandmaximumdegreeΔAsetofkcolorsAk-coloringofGisanassignmentf:V→{1,...,k}suchthatforall(u,v)E,f(u)6=f(v)GivenagraphwithmaximumdegreeΔHowtoconstructk-coloringsITrivialfork>ΔHowtosample(uniformlyat)randomk-coloringsINon-trivialevenfork>ΔuJnaeVarT(liubgr)hPsaerTnaisitnotaeRocsnrtcuitnoILNP:ACIL,NpAr02012/32
ColoringgraphsiGnevAgraphG=(V,E)onnverticesandmaximumdegreeΔAsetofkcolorsAk-coloringofGisanassignmentf:V→{1,...,k}suchthatforall(u,v)E,f(u)6=f(v)GivenagraphwithmaximumdegreeΔHowtoconstructk-coloringsITrivialfork>ΔHowtosample(uniformlyat)randomk-coloringsINon-trivialevenfork>ΔuJnaeVarT(liubgr)hPsaerTnaisitnotaeRocsnrtcuitnoILNP:ACIL,NpAr02012/32
RandomColoringgraphsWhyareweinterested?Howtosample(uniformlyat)randomk-colorings?Howdorandomk-coloringslook?RandomcoloringsistheGibbsdistributionfor(zero-temperature)anti-ferromagneticPottsmodel.Efficientsampleryieldsapproximationalgorithmforcountingcolorings,whichis#P-complete.uJnaeVarT(liubgr)hPsaerTnaisitnotaeRocsnrtcuitnoILNP:ACIL,NpAr02013/32