Random weighting, asymptotic counting, and inverse isoperimetryAlexander BarvinokUniversity of Michigan, Ann Arbor
February 27,

ABSTRACT


Let X be a family of ksubsets 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. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

