Random Weighting, Asymptotic Counting, and Inverse Isoperimetry
| dc.creator | Barvinok, Alexander | |
| dc.creator | Samorodnitsky, Alex | |
| dc.date | 2003-02-14 | |
| dc.date | 2003-06-04 | |
| dc.date.accessioned | 2026-07-07T04:55:18Z | |
| dc.date.available | 2026-07-07T04:55:18Z | |
| dc.description | 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. | |
| dc.description | The revision contains a new isoperimetric theorem, some other improvements and extensions; 29 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/math/0302177 | |
| dc.identifier | http://arxiv.org/abs/math/0302177 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/66532 | |
| dc.subject | Combinatorics | |
| dc.subject | Metric Geometry | |
| dc.subject | Probability | |
| dc.subject | 05A16, 60C05, 60D05, 51F99, 68W20 | |
| dc.title | Random Weighting, Asymptotic Counting, and Inverse Isoperimetry | |
| dc.type | text |