  Sampling from Gibbs distribution is a central 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 somehow diminishes. However, devising such a construction
of blocks is a highly non trivial task.
  We develop for a first time a weighting schema for the paths of the
underlying graph. Vertices which belong to "light" paths, only, can be placed
at the boundaries of the blocks. Then the tree-like local structure of G(n,d/n)
allows the construction of simple structured blocks.
