Random weighting,asymptotic counting,and inverse isoperimetry

For a family X of k-subsets of the set {1, …, n}, let |X| be the cardinality of X and let Γ(X, μ) 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 μ on ℝ. We consider the inverse isoperimetric problem of finding μ for which Γ(X, μ) gives the best estimate of ln |X|. We prove that the optimal choice of μ is the logistic distribution, in which case Γ(X, μ) provides an asymptotically tight estimate of ln |X| as k ⁻¹ ln |X} grows. Since in many important cases Γ(X, μ) can be easily computed, we obtain computationally efficient approximation algorithms for a variety of counting problems. Given μ, we describe families X of a given cardinality with the minimum value of Γ(X, μ), thus extending and sharpening various isoperimetric inequalities in the Boolean cube. The research of the first author was partially supported by NSF Grants DMS 9734138 and DMS 0400617. The research of the second author was partially supported by ISF Grant 039-7165 and by GIF grant I-2052.