The University of Michigan Combinatorics Seminar


Abstract 

Let mu be a symmetric probability measure on R. For a family X of ksubsets 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.
