Discrete Rearrangements and the Polya-Szego Inequality on Graphs

For any $f:{\mathbb{R}}^n\to {\mathbb{R}}_{\ge 0}$ the symmetric decreasing rearrangement $f^{\ast }$ satisfies the Polya-Szegő inequality $\mathrm{\parallel }\mathrm{\nabla }{f}^{\ast }{\mathrm{\parallel }}_{L^p}\le \mathrm{\parallel }\mathrm{\nabla }f{\mathrm{\parallel }}_{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 Polya-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 $\mathrm{\parallel }\mathrm{\nabla }{f}^{\ast }{\mathrm{\parallel }}_{L^1}\le \mathrm{\parallel }\mathrm{\nabla }f{\mathrm{\parallel }}_{L^1}$. The $L^{\mathrm{\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 Polya-Szegő inequality for all $1\le p\le \mathrm{\infty }$.