Sensitivity and Hamming Graphs

ABSTRACT For any we show that the Hamming graph admits an imbalanced partition into sets, each inducing a subgraph of low maximum degree. This improves previous results by Tandya and by Potechin and Tsang, and disproves the Strong ‐ary Sensitivity Conjecture of Asensio, García‐Marco, and Knauer. On the other hand, we prove their weaker ‐ary Sensitivity Conjecture by showing that the sensitivity of any ‐ary function is bounded from below by a polynomial expression in its degree.