Sensitivity and Hamming graphs

Sara Asensio, Yuval Filmus, Ignacio García-Marco +1

For any $m\ge 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 resul…