H-colouring bipartite graphs

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.