Jan. 15, 3:30pm, Wean 8220

Alexander Barvinok, University of Michigan

Computing partition functions in hard problems of combinatorial optimization

Alexander Barvinok, University of Michigan

Computing partition functions in hard problems of combinatorial optimization

Abstract:

Consider an NP-complete problem, such as finding whether a given graph *G* on *n* vertices contains a Hamiltonian
cycle. First, we attempt to solve an even more general problem: given an *n* × *n* non-negative matrix A, interpreted as the
matrix of weights on the edges of the complete graph *K*_{n}, we consider the sum (partition function) over all Hamiltonian
cycles in *K*_{n} of the products of weights on the edges of the cycle. Thus if *A* the adjacency matrix of *G*, we obtain the
number of Hamiltonian cycles in *G*. Next, we modify *A* by replacing all zeros with some positive epsilons. It turns out that
the partition function becomes efficiently computable, which allows us to distinguish graphs that are far from having a
Hamiltonian cycles from graphs that have many Hamiltonian cycles (even when "many" still means that the probability to hit
a Hamiltonian cycle at random is exponentially small).

In a joint work with P. Soberon, we attempt to establish the most general framework when this approach appears to work: it concerns computing the partition function of graph homomorphisms with multiplicities, which allows us to handle Hamiltonian cycles, independent sets, dense subgraphs and colorings.