Efthymiou, Charilaos (2014) MCMC sampling colourings and independent sets of G(n,d/n) near the uniqueness threshold. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms, Portland, Oregon, USA, 5-7 Jan 2014. Published in: SODA '14 Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms pp. 305-316. ISBN 9781611973389. doi:10.1137/1.9781611973402.22

Preview	PDF WRAP-MCMC-sampling-colourings-independent-sets-Efthymiou-2019.pdf - Published Version - Requires a PDF viewer. Download (796Kb) | Preview
	PDF WRAP-MCMC-sampling-colourings-independent-sets-Efthymiou-2015.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (765Kb)

Request Changes to record.

Abstract

Sampling from the Gibbs distribution is a well studied problem in computer science as well as in statistical physics. In this work we focus on the k-colouring model and the hard-core model with fugacity \lambda when the underlying graph is an instance of Erdos-Renyi random graph G(n,p), where p=d/n and d is fixed.

We use the Markov Chain Monte Carlo method for sampling from the aforementioned distributions. In particular, we consider Glauber (block) dynamics. We show a dramatic improvement on the bounds for rapid mixing in terms of the number of colours and the fugacity for the corresponding models. For both models the bounds we get are only within small constant factors from the conjectured ones by the statistical physicists.

We use Path Coupling to show rapid mixing. For k and \lambda in the range of our interest the technical challenge is to cope with the high degree vertices, i.e. vertices of degree much larger than the expected degree d. The usual approach to this problem is to consider block updates rather than single vertex updates for the Markov chain. Taking appropriately defined blocks the effect of high degree vertices diminishes. However devising such a block construction is a non trivial task.

We develop for a first time a weighting schema for the paths of the underlying graph. Only, vertices which belong to "light" paths can be placed at the boundaries of the blocks. The tree-like local structure of G(n,d/n) allows the construction of simple structured blocks.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Graph coloring, Markov processes, Monte Carlo method, Random graphs
Journal or Publication Title:	SODA '14 Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms
Publisher:	Society for Industrial and Applied Mathematics (SIAM)
ISBN:	9781611973389
Official Date:	5 January 2014
Dates:	Date Event 5 January 2014 Published 15 September 2013 Accepted
Page Range:	pp. 305-316
DOI:	10.1137/1.9781611973402.22
Status:	Peer Reviewed
Publication Status:	Published
Reuse Statement (publisher, data, author rights):	Copyright © 2014. by the Society for Industrial and Applied Mathematics
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	21 March 2019
Date of first compliant Open Access:	26 March 2019
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID EP/G039070/2 [EPSRC] Engineering and Physical Sciences Research Council http://dx.doi.org/10.13039/501100000266
Conference Paper Type:	Paper
Title of Event:	25th Annual ACM-SIAM Symposium on Discrete Algorithms
Type of Event:	Conference
Location of Event:	Portland, Oregon, USA
Date(s) of Event:	5-7 Jan 2014

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads