Discrete rearrangements and the Pólya–Szegő inequality on graphs
Volume 274 / 2024
Abstract
For any $f: \mathbb R^n \rightarrow \mathbb R_{\geq 0}$ the symmetric decreasing rearrangement $f^*$ satisfies the Pólya–Szegő inequality $\| \nabla f^*\|_{L^p} \leq \| \nabla f\|_{L^p}$. The goal of this paper is to establish analogous results in the discrete setting for graphs satisfying suitable conditions. We prove that if the edge-isoperimetric problem on a graph has a sequence of nested minimizers, then this sequence gives rise to a rearrangement satisfying the Pólya–Szegő inequality in $L^1$. This shows, for example, that a specific rearrangement on the grid graph $\mathbb Z^2$, going around the origin in a spiral-like manner, satisfies $\| \nabla f^*\|_{L^1} \leq \| \nabla f\|_{L^1}$. The $L^{\infty }$-case is implied by an optimal ordering condition in vertex-isoperimetry. We use these ideas to prove that the canonical rearrangement on the infinite $d$-regular tree satisfies the Pólya–Szegő inequality for all $1 \leq p \leq \infty $.