The complexity of counting colourings and independent sets in sparse graphs and hypergraphs

We consider certain counting problems involving colourings of graphs and in dependent sets in hypergraphs. Using polynomial interpolation techniques, w e show that these problems are #P-complete. Therefore, efficient approximat e counting is the most one can realistically expect to achieve. Rapidly mix ing Markov chains which can be used for approximately solving some of these counting problems have been recently developed by the author and others.