Mathematics – Combinatorics
Scientific paper
2003-02-14
Mathematics
Combinatorics
The revision contains a new isoperimetric theorem, some other improvements and extensions; 29 pages, 1 figure
Scientific paper
For 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.
Barvinok Alexander
Samorodnitsky Alex
No associations
LandOfFree
Random Weighting, Asymptotic Counting, and Inverse Isoperimetry does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Random Weighting, Asymptotic Counting, and Inverse Isoperimetry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Weighting, Asymptotic Counting, and Inverse Isoperimetry will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-306937