ECCC-Report TR05-065https://eccc.weizmann.ac.il/report/2005/065Comments and Revisions published for TR05-065en-usSun, 26 Jun 2005 22:21:29 +0300
Paper TR05-065
| Random Weighting, Asymptotic Counting, and Inverse Isoperimetry |
Alexander Barvinok,
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/2005/065For a family X of k-subsets of the set 1...n, let |X| be the cardinality of X and let Gamma(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 R. We consider the inverse isoperimetric problem of finding mu for which Gamma(X, mu) gives the best estimate of ln |X|.
We prove that the optimal choice of mu is the logistic distribution, in which case Gamma(X, mu) provides an asymptotically tight estimate
of ln |X| as k^{-1} ln |X| grows. Since in many important cases Gamma(X, mu) can be easily computed, we obtain computationally efficient approximation algorithms for a variety of counting problems.
Given mu, we describe families X of a given cardinality with the minimum value of Gamma(X, mu), thus extending and sharpening various isoperimetric inequalities in the Boolean cube.
Sun, 26 Jun 2005 22:21:29 +0300https://eccc.weizmann.ac.il/report/2005/065