An asymptotic isoperimetric inequality
type: Item
instance of: scholarly article
title: An asymptotic isoperimetric inequality
zbMATH Open document ID: 0907.60018
published in: Geometric and Functional Analysis. GAFA
publication date: 1999-03-02T00:00:00Z
review text: For a finite metric space \(V\) with a metric \(\rho\) and probability measure \(\mu\), let \(V^n\) be the product metric space in which the distance between \(a= (a_1,\dots, a_n)\) and \(b= (b_1,\dots, b_n)\) is \(\rho_n(a,b)= \sum_i\rho(a_i, b_i)\) and the measure \(\mu_n(a_1,\dots, a_n)= \prod_i\mu(a_i)\). For any \(d\geq 0\) the \(d\)-neighbourhood of \(S\subseteq V^n\) is \[ B[S,d]= \{u\in V^n: \exists v\in S,\;\rho_n(u,v)\leq d\}. \] The authors are interested in maximizing \(\mu_n(V^n\setminus B[S,d])\) over all sets \(S\) with \(\mu_n(S)\geq 1/2\). Their central result provides an asymptotic formula for the logarithm of the corresponding maximum when \(n\to\infty\) and \(d/\sqrt n\to\infty\). The authors provide self-contained probabilistic proofs of their results. As they note, the formulations of results are closely related to the probabilistic theory of large deviations.
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05D99
Mathematics Subject Classification ID: 60F10
zbMATH DE Number: 1197113
zbMATH Keywords: large deviation
zbMATH Keywords: finite metric space
zbMATH Keywords: discrete isoperimetric inequality
author: Noga Alon
author: Ravi B. Boppana
author: Joel Spencer
reviewed by: Ilya S. Molchanov
MaRDI profile type: Publication
full work available at URL: s000390050062
OpenAlex ID: W2091690227
DOI: 10.1007/S000390050062
description: scientific article; zbMATH DE number 1197113