Document Type

Article

Language

eng

Format of Original

17 p.

Publication Date

5-2012

Publisher

Elsevier

Source Publication

Journal of Combinatorial Theory, Series B

Source ISSN

0095-8956

Original Item ID

doi: 10.1016/j.jctb.2011.12.004

Abstract

For graphs G and H, an H-colouring of G (or homomorphism from G to H) is a function from the vertices of G to the vertices of H that preserves adjacency. H-colourings generalize such graph theory notions as proper colourings and independent sets. For a given H, k∈V(H) and G we consider the proportion of vertices of G that get mapped to k in a uniformly chosen H-colouring of G. Our main result concerns this quantity when G is regular and bipartite. We find numbers 0⩽a−(k)⩽a+(k)⩽1 with the property that for all such G, with high probability the proportion is between a−(k) and a+(k), and we give examples where these extremes are achieved. For many H we have a−(k)=a+(k) for all k and so in these cases we obtain a quite precise description of the almost sure appearance of a randomly chosen H-colouring. As a corollary, we show that in a uniform proper q-colouring of a regular bipartite graph, if q is even then with high probability every colour appears on a proportion close to 1/q of the vertices, while if q is odd then with high probability every colour appears on at least a proportion close to 1/(q+1) of the vertices and at most a proportion close to 1/(q−1) of the vertices. Our results generalize to natural models of weighted H-colourings, and also to bipartite graphs which are sufficiently close to regular. As an application of this latter extension we describe the typical structure of H-colourings of graphs which are obtained from n-regular bipartite graphs by percolation, and we show that p=1/n is a threshold function across which the typical structure changes. The approach is through entropy, and extends work of J. Kahn, who considered the size of a randomly chosen independent set of a regular bipartite graph.

Comments

Accepted version. Journal of Combinatorial Theory, Series B, Vol. 102, No. 3 (May 2012): 726-742. DOI.

NOTICE: this is the author’s version of a work that was accepted for publication in Journal of Combinatorial Theory, Series B. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Journal of Combinatorial Theory, Series B, VOL 102, ISSUE 3, (May 2012). DOI.

Download

Share

COinS