Enumerative combinatorics

Wednesday, November 12, 2014 - 9:00am - 9:50am
Alexander Barvinok (University of Michigan)
As is well known, many interesting problems of combinatorial enumeration are computationally hard (for example, it is hard to approximate the number of independent sets of a given size in a given graph within any non-trivial factor). A smoothed version of a counting problem consists in computing the corresponding partition function (for example, we compute the weighted sum over all subsets of vertices of a given size in a given graph, where the weight of a subset is exponentially small in the number of edges that it spans).
Subscribe to RSS - Enumerative combinatorics