Local Maxima of Quadratic Boolean Functions

Abstract

How many strict local maxima can a real quadratic function on $\{0,1{\}}^n$ have? Holzman conjectured a maximum of $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. The aim of this paper is to prove this conjecture. Our approach is via a generalization of Sperner's theorem that may be of independent interest.

arXiv comment6 pages, 1 figure