Random weighting, asymptotic counting, and inverse isoperimetry

Alexander Barvinok

University of Michigan, Ann Arbor

February 27,
refreshments at 3:45pm


Let X be a family of k-subsets of the set {1, ... ,n}, let |X| be the cardinality of X, and 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 a symmetric probability distribution mu on the reals. In a sense, G(X, mu) measures how large X is; it behaves somewhat similarly to ln |X|. Moreover, G(X, mu) can be easily computed for a variety of combinatorially defined X, such as matchings, bases in matroids, etc. via standard combinatorial optimization algorithms, while counting |X| can be hard. It turns out that G(X, mu) provides the best approximation for ln |X| if mu is the logistic distribution. In this case, G(X, mu) is asymptotically equivalent to ln |X| as long as (ln |X|)/k grows. Thus our results imply some weak equivalence of counting (computing |X|) and optimization (finding the maximum weight of a subset in X for a given set of weights on the ambient space).

Some old problems in probability can be recasted in terms of relations between G(X, mu) and |X|: if mu is the Bernoulli measure, we get the classical isoperimetric inequality in the Boolean cube due to Harper and if mu is the symmetric exponential measure, we get an inequality for the supremum of a stochastic process due to Talagrand. In general, we show that for any symmetric measure mu, the minimum value of G(X, mu) on X of a given cardinality is attained when X is the product of two Hamming spheres in the Boolean cube.

This is joint work with Alex Samorodnitsky.

Speaker's Contact Info: barvinok(at-sign)umich.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on January 22, 2004 at 06:16 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.