Isoperimetric Inequalities Made Simpler

Isoperimetric inequalities made simpler, Discrete Analysis 2025:7, 23 pp.

The famous isoperimetric inequality in the plane states that of all (sufficiently nice) shapes with a given volume, the one with the smallest boundary length is a circle. More generally, in $\mathbb R^n$, among all shapes with a given $n$-dimensional volume, the one with the smallest $(n-1)$-dimensional “surface area” is the $n$-dimensional sphere with that volume. More generally still, in any set-up where we can make sense of the notion of the volumes and surface areas of sets, one can ask which shapes of given volume have the smallest surface area.

In particular, this opens up the possibility of discrete isoperimetric inequalities. Two particularly important examples of these are the vertex- and edge-isoperimetric inequalities in the discrete cube $\{0,1\}^n$. In both cases, the volume of a set is defined to be its cardinality, but the definitions of “surface area” are different. For the vertex-isoperimetric inequality, we define the vertex-boundary of a set $A$ to be the set of all points in $\{0,1\}^n$ at Hamming distance 1 from $A$, and for the edge-isoperimetric inequality we define the edge-boundary to be the set of all edges that join a point in $A$ to a point in $A^c$. In both cases we try to minimize the size of the boundary.

Interestingly, the extremal sets for the two inequalities are quite different. For the vertex-isoperimetric inequality, if $|A|=\sum_{k=0}^r\binom nk$, then the best one can do is take a Hamming ball of radius $r$, of which the most obvious example is the collection of all points $x\in\{0,1\}^n$ with at most $r$ 1s. For the edge-isoperimetric inequality, the best one can do if $|A|=2^r$ for some $r$ is to take an $r$-dimensional face of the hypercube, of which the most obvious example is the set of points $x\in\{0,1\}^n$ that are zero except possibly in the first $r$ coordinates. It is also known what the exact extremal examples are when the cardinality is not that of a Hamming ball or of a face.

Talagrand’s inequality is a result that in a certain sense “interpolates” between these two inequalities. Let $f:\{0,1\}^n\to\{0,1\}$ be a Boolean function and define the sensitivity $s_f(x)$ of $f$ at $x$ to be the number of coordinates of $x$ such that if you change that coordinate then you change the value of $f$. More formally, if we write $x\oplus e_i$ for the vector that agrees with $x$ everywhere except at the $i$th coordinate, $s_f(x)=|\{i:f(x\oplus e_i)\ne f(x)\}|$. Then a special case of Talagrand’s inequality states that there is an absolute constant $c>0$ such that
$$\mathbb E_x[s_f(x)]\geq c\text{var}(f)\sqrt{\log_2(1/\text{var}(f))}.$$

To get some idea of what this is saying, consider the following two examples. If $A$ is a Hamming ball of size roughly $2^{n-1}$, then $s_f(x)$ will be 0 unless $x$ is on the boundary of this ball or the boundary of its complement, in which case it will be roughly $n/2$. The probability of lying on this boundary is of order $n^{-1/2}$, so the left-hand side is of order $1$. The variance of $f$ is approximately $1/2$, so the right-hand side is also of order 1. If now we take $A$ to be the codimension-1 face $\{x:x_1=0\}$, then $s_f(x)=1$ for every $x$, and the variance is 1/2, so again both sides are of order 1. Thus, the extremal sets for both the vertex- and edge-isoperimetric inequalities are (at least for sets of density roughly 1/2) extremal for this inequality too, give or take the value of the absolute constant $c$, and in fact this inequality implies approximate versions of the two isoperimetric inequalities when the density of $A$ is not too close to 0 or 1.

The proof of Talagrand’s inequality (as well as of a more general version for $p$-biased measures) uses a rather non-obvious inductive hypothesis and depends on using calculus to verify a number of inequalities.

One of the main results of this paper is to give a Fourier-analytic proof of the inequality. Very roughly the proof proceeds as follows. First the authors note that a simple argument shows that if $f$ has substantial Fourier mass on the first level (that is, the sum of $|\hat f(\chi)|^2$ over characters $\chi$ of weight 1 is large), then $\mathbb E_xs_f(x)$ is large. Not all functions have this property, but the authors next show that if $f$ has substantial mass between level $d$ and level $2d$ for some $d$, then a suitable random restriction of $f$ has large mass at level 1. This can then be used to show that $\mathbb E_x\sqrt{s_f(x)}$ is “very large”, and then the Bonami-Beckner inequality and Hölder’s inequality are used to finish off the argument.

Talagrand also made a conjecture that simultaneously generalizes his inequality and the famous theorem of Kahn, Kalai and Linial. This conjecture was proved by Eldan and Gross in 2020 using techniques from stochastic analysis. In this paper, the proof of Talagrand’s inequality is developed further, using a sharpening by Keller and Kindler of another inequality of Talagrand, to give a new and simpler proof of Talagrand’s conjecture as well.

The other main contribution of this paper is to strengthen Friedgut’s junta theorem, which is another central result in the analysis of Boolean functions and has a large number of applications. The theorem states that if $f:\{0,1\}^n\to\{0,1\}$ is a function with low average sensitivity – that is, such that $\mathbb E_x s_f(x)\leq A$ for some constant $A$ – then $f$ can be $\epsilon$-approximated by a function $g$ that depends on at most $2^{O(A/\epsilon)}$ variables (meaning that the density of $x$ for which $f(x)\ne g(x)$ is at most $\epsilon$). In this paper the authors consider the weaker condition that $\mathbb E_x (s_f(x))^p\leq A$, where $p$ is a constant in the interval $(1/2,1]$, and show that $f$ is $\epsilon$-close to a function $g$ that depends on at most $2^{O(A/\epsilon)^{1/p}}$ variables. (Note that the example considered earlier, of a Hamming ball of density approximately 1/2, shows that the condition $p>1/2$ is necessary here.)