Kannan, Ravi; Lovász, László; Simonovits, Miklos Isoperimetric problems for convex bodies and a localization lemma. (English) Zbl 0824.52012 Discrete Comput. Geom. 13, No. 3-4, 541-559 (1995). The isoperimetric coefficient of a convex body \(K \subseteq \mathbb{R}^ n\) is defined as the largest number \(\psi= \psi(K)\) such that for every measurable subset \(S \subseteq K\) for which \(\partial_ K S\) (the boundary of \(S\), relative to \(K\)) has an \((n-1)\)-dimensional Minkowski measure, \[ \text{vol}_{n-1} (\partial_ K S)\geq \psi {{\text{vol} (S)\cdot \text{vol} (K\setminus S)} \over {\text{vol} (K)}}. \] Since 1989 several attempts have been made to find a sharp lower bound of the isoperimetric coefficient; the best result was obtained by Dyer and Frieze in 1992 when they gave a lower bound of \(\psi (K)\) in terms of the diameter. However, the diameter may not be the best possible measure to use in this problem; in its application to volume algorithms and related questions, these bounds are needed in the case that the body is rather “round” and so the bounds in terms of the diameter may not be sharp. The main result of this paper gives the following lower bound for \(\psi (K)\): \[ \psi (K)\geq {{\ln 2} \over {M_ 1 (K)}}, \tag{1} \] where \(M_ 1 (K)\) denotes the average distance of a point in \(K\) from its center of gravity. The main tool to obtain this result is a variant of a general “Localization Lemma” that reduces integral inequalities over the \(n\)- dimensional space to integral inequalities in a single variable. The first version of this “Localization Lemma” was proved by two of the authors (Lovász and Simonovits) in 1993. Another lower bound for \(\psi (K)\) is also proved in this paper: \[ \psi (K)\geq {1\over {\chi(K)}}, \tag{2} \] where \(\chi(K)= {1\over {\text{vol} (K)}} \int_ K \chi(x) dx\), and \(\chi (x)\) denotes the length of the longest segment contained in \(K\) with midpoint \(x\). The two lower bounds (1) and (2) are not comparable. At the end of the paper there is also given an upper bound for \(\psi (K)\): \[ \psi (K)\leq {{10} \over {\sqrt {\alpha (K)}}}, \tag{3} \] where \(\alpha (K)\) is the largest eigenvalue of the matrix of inertia of \(K\). The authors conjecture that this upper bound is identical, up to a constant factor, to \(\psi (K)\). Reviewer: S.Gomis (Murcia) Cited in 10 ReviewsCited in 145 Documents MSC: 52A40 Inequalities and extremum problems involving convexity in convex geometry Keywords:relative isoperimetric problems; localization lemma; needles; isotropy; moment; isoperimetric coefficient PDFBibTeX XMLCite \textit{R. Kannan} et al., Discrete Comput. Geom. 13, No. 3--4, 541--559 (1995; Zbl 0824.52012) Full Text: DOI EuDML References: [1] D. Applegate and R. Kannan (1990): Sampling and integration of near log-concave functions,Proc. 23th ACM Symposium on the Theory of Computing, pp. 156-163. [2] J. Bokowski (1980): Ungleichungen für des Inhalt von Trennflächen,Arch. Math.34, 84-89. · Zbl 0445.52011 [3] J. Bokowski and E. Spencer Jr. (1979): Zerlegung Konvexen Körperdurch minimale Trennflächen,J. Reine Angew. Math.311-312, 80-100. · Zbl 0415.52008 [4] C. Borell (1975): The Brunn-Minkowski inequality in Gauss spaces,Invent. Math.30, 207-216. · Zbl 0292.60004 [5] J. Bourgain (1991):On the Distribution of Polynomials on High Dimensional Convex Sets, Lecture Notes in Mathematics, Vol. 1469, Springer-Verlag, Berlin, pp. 127-137. · Zbl 0773.46013 [6] A. Dinghas (1957): Über eine Klasse superadditiver Mengenfunktionale von Brunn-Minkowski-Lusternik-schem Typus,Math. Z.68, 111-125. · Zbl 0083.38301 [7] Dyer, M.; Frieze, A.; Bollobás, B. (ed.), Computing the volume of convex bodies: a case where randomness provably helps, No. Vol. 44, 123-170 (1992), Providence, RI [8] M. Dyer, A. Frieze, and R. Kannan (1989): A random polynomial time algorithm for approximating the volume of convex bodies,Proc. 21st ACM Symposium on Theory of Computing, pp. 375-381. [9] M. Gromov and V. D. Milman (1984): Brunn theorem and a concentration of volume of convex bodies, GAFA Seminar Notes, Tel Aviv University. · Zbl 0953.52500 [10] D. Hensley (1980): Slicing convex bodies and bounds on the slice area in terms of the body’s covariance,Proc. Amer. Math. Soc.79, 619-625. · Zbl 0439.52008 [11] John, F., Extermum problems with inequalities as subsidiary conditions, 187-204 (1948), New York [12] A. Karzanov and L. G. Khachiyan (1991), On the conductance of order Markov chains,Order8, 7-15. · Zbl 0736.06002 [13] L. Lovász and M. Simonovits (1990): Mixing rate of Markov chains, an isoperimetric inequality, and computing the volume.Proc. 31st IEEE Symposium on Foundations of Computer Science, pp. 346-355. [14] L. Lovász and M. Simonovits (1993): Random walks in a convex body and an improved volume algorithm,Random Structures Algebra4, 359-412. · Zbl 0788.60087 [15] Milman, V. D.; Pajor, A.; Milman, V. D.; Lindenstrauss, J. (ed.), Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normedn-dimensional space, No. Vol. 1376, 64-104 (1989), Berlin · Zbl 0679.46012 [16] A. Prékopa (1971): Logarithmic concave measures with applications to stochastic programming,Acta Sci. Math. (Szeged.)32, 301-316. · Zbl 0235.90044 [17] G. Sonnevend (1989): Applications of analytic centers for the numerical solution of semi-infinite, convex programs arising in control theory, DFG Report No. 170/1989, Institut für angew. Mathematik, University of Würzburg. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.