test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works
       

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9457

Title: The Glauber dynamics on colorings of a graph with high girth and maximum degree
Authors: Molloy, M.
Keywords: rapidly mixing Markov chains
Glauber dynamics
colorings
Issue Date: 2004
Publisher: Society for Industrial and Applied Mathematics
Citation: Molloy, M. (2004). The glauber dynamics on colorings of a graph with high girth and maximum degree. SIAM Journal on Computing, 33, 721-737.
Abstract: We prove that the Glauber dynamics on the C-colorings of a graph G on n vertices with girth g and maximum degree Delta mixes rapidly if (i) C=qDelta and q>q*, where q*=1.4890... is the root of (1-e(-1/q))(2) + qe(-1)/(q)=1; and (ii) Deltagreater than or equal toD log n and ggreater than or equal toD log Delta for some constant D=D(q). This improves the bound of roughly 1.763Delta obtained by Dyer and Frieze [Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 2001] for the same class of graphs. Our bound on this class of graphs is lower than the bound of 11Delta/6approximate to1.833Delta obtained by Vigoda [J. Math. Phys., 41 (2000), pp. 1555-1569] for general graphs.
Description: Copyright © 2003 SIAM. All rights reserved.
URI: http://hdl.handle.net/1807/9457
ISSN: 0097-5397
Rights: IMPORTANT NOTICE: TO USERS OF THIS DATA ALL DATA WAS COLLECTED THROUGH THE CONSIDERABLE EFFORTS OF THE RESEARCHERS CONTRIBUTING TO IT. WHILE THE DATA CAN BE USED FOR NEW ANALYSES, Contact should be main to the collector of this data prior to publication and ACKNOWLEDGEMENT MUST BE EXPLICITLY MADE AS TO THE COLLECTOR AND CONTRIBUTOR OF THESE DATA.
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
post print - the glauber dynamics....pdf301.24 kBAdobe PDF
View/Open

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

uoft