The ACO Seminar (2025–2026)

Classical results by Jerrum (1995) and Salas-Sokal (1997) show the possibility of efficient approximate counting and uniform sampling of proper colorings with q > 2Delta colors in graphs of maximum degree Delta. For colorings with fixed color class sizes, Kierstand and Kostochka (2007) reproved the existence of equitable coloring (colorings where class sizes differ by at most 1) and provided a polynomial algorithm which produces such a coloring and requires only q > Delta colors. In this paper we provide efficient approximate counting and uniform sampling algorithms for colorings with fixed color class sizes that are equitable or close to equitable. The proof uses techniques such as zero-freeness of partition functions, Local Central Limit Theorems, and cluster expansion. We hope our result adds to the growing evidence of the possibility to efficiently sample fundamental combinatorial objects, such as colorings, with global constraints. Joint work with Will Perkins and Xavier Povill.

This talk will not assume any knowledge of statistical physics or sampling!