The University of Michigan Combinatorics Seminar
Winter 2003
February 7, 4:10-5:00, 3866 East Hall

Random weighting, asymptotic counting and inverse isoperimetry

Alexander Barvinok

University of Michigan


Let mu be a symmetric probability measure on R. For a family X of k-subsets of the set {1,...,n}, let G(X, mu) be the expected maximum weight of a subset from X when the weights of 1,...,n are chosen independently at random from the distribution mu and let |X| be the cardinality of X. In a sense, G(X, mu) measures how large X is and it can easily be computed for a variety of combinatorially defined X, such as matchings, bases in matroids, etc. via standard combinatorial optimization algorithms. Thus we consider what we call the inverse isoperimetric problem of constructing mu for which G(X, mu) provides the best approximation for |X|. We present a measure mu with the following property: for any a>1 there exists b=b(a)>0 such that G(X, mu) approximates ln |X| within a factor of b provided |X|>a^k, and, moreover, b approaches 1 as a grows to infinity. Connections to isoperimetric inequalities in the Boolean cube will also be discussed.

This is a joint work with Alex Samorodnitsky.