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

Abstract.

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