Random Weighting, Asymptotic Counting, and Inverse Isoperimetry

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-306937

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.