Random Weighting, Asymptotic Counting, and Inverse Isoperimetry

Details Random Weighting, Asymptotic Counting, and Inverse Isoperimetry Random Weighting, Asymptotic Counting, and Inverse Isoperimetry

2003-02-14

arxiv.org/abs/math/0302177v2

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306937