\(\lambda_{\infty}\), vertex isoperimetry and concentration (Q5928566): Difference between revisions

This article develops several inequalities involving graph constants, following the line suggested by \textit{N. Alon} [Combinatorica 6, No. 2, 83-96 (1986; Zbl 0661.05053)], which looked at a constant \(\lambda_2\), definable in terms of the Laplacian of a graph. This article looks at a similar constant. Given a graph \(G=(V,E)\) and a probability measure \(\pi\) on \(G\), we can let \(\lambda_{\infty}\) be the infimum, over all \(f:V\to R\), of \(\sum_{x\in V}\pi(x)\sup_{y:E(x,y)}[f(x)-f(y)]^2\). Several inequalities involving \(\lambda_{\infty}\) are developed. These inequalities involve graph functions like \(\rho(A,x)=\min_{y\in A} \text{dist}(x,y)\), and constants such as \[ h=\min_{A\subseteq V} \{|\{x \not\in A:\rho(A,x)=1\}|/|A|:0<|A|\leq |V|/2\}. \] The inequalities give bounds and a concentration result about \(\lambda_{\infty}\).