Skip to main content
Post Made Community Wiki
Source Link
Greg Kuperberg
  • 56.6k
  • 10
  • 203
  • 282

Since Gjergji brings up isoperimetric inequalities, there is a lot of attention in combinatorial geometry devoted to combinatorial versions. For instance, if $f$ is a Boolean function $f$ on $n$ bits, define its "instability" to be the number of ways that $f(\vec{x}) \ne f(\vec{y})$ when $\vec{x}$ and $\vec{y}$ differ in one bit. If half of the values of $f$ are 0 and half are 1, then the theorem is that the most stable choice of $f$ is a function $f(\vec{x}) = x_k$ that only depends on one bit.

On the theme of one-step proofs in geometry that depend on another theorem, there is a one-step proof of this fact using the standard spherical isoperimetric inequality.