Paper detail

Partition functions for dense instances of combinatorial enumeration problems

Given a complete graph with positive weights on its edges, we define the weight of a subset of edges as the product of weights of the edges in the subset and consider sums (partition functions) of weights over subsets of various kinds: cycle covers, closed walks, spanning trees. We show that if the weights of the edges of the graph are within a constant factor, fixed in advance, of each other then the bulk of the partition function is concentrated on the subsets of a particularly simple structure: cycle covers with few cycles, walks that visit every vertex only few times, and spanning trees with small degree of every vertex. This allows us to construct a polynomial time algorithm to separate graphs with many Hamiltonian cycles from graphs that are sufficiently far from Hamiltonian.