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

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
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/9527

Title: Very rapidly mixing Markov chains for 2 Delta-colorings and for independent sets in a graph with maximum degree 4
Authors: Molloy, M.
Keywords: colorings
Issue Date: 2001
Publisher: John Wiley & Sons
Citation: Molloy, M. (2001). Very rapidly mixing markov chains for 2 delta-colorings and for independent sets in a graph with maximum degree 4. Random Structures & Algorithms, 18(2), 101-115.
Abstract: We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 Delta -colorings of a graph with maximum degree Delta mixes in O(n log n) time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random, Structures Algorithms 13, 285-317 (1998)) on independent sets of graphs with maximum degree 4. (C) 2001 John Wiley & Sons, Inc.
Description: This is a preprint of an article published in the journal Random Structures & Algorithms, 18(2), 101-115. The journal is located at the following Wiley URL: http://www3.interscience.wiley.com/cgi-bin/jhome/38107
URI: http://hdl.handle.net/1807/9527
ISSN: 1042-9832
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
Very rapidly mixing.pdf264.93 kBAdobe PDF

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