Sensitivity and Hamming graphs
This resolves open conjectures in graph theory and Boolean function analysis, with implications for computational complexity and combinatorial optimization.
The paper disproves the Strong m-ary Sensitivity Conjecture by showing Hamming graphs admit imbalanced partitions into low-degree subgraphs, and proves the weaker m-ary Sensitivity Conjecture by bounding sensitivity polynomially in degree for m-ary functions.
For any $m\geq 3$ we show that the Hamming graph $H(n,m)$ admits an imbalanced partition into $m$ sets, each inducing a subgraph of low maximum degree. This improves previous results by Tandya and by Potechin and Tsang, and disproves the Strong $m$-ary Sensitivity Conjecture of Asensio, GarcÃa-Marco, and Knauer. On the other hand, we prove their weaker $m$-ary Sensitivity Conjecture by showing that the sensitivity of any $m$-ary function is bounded from below by a polynomial expression in its degree.