On induced subgraphs of the Hamming graph

In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph $G$ with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of $G$ with $\alpha \left(G\right)+1$ vertices, where $\alpha \left(G\right)$ denotes the size of the largest independent set in $G$? We study this question for $H\left(n,k\right)$, the $n$‐dimensional Hamming graph over an alphabet of size $k$. Generalizing a construction by Chung et al. (JCT‐A, 1988), we prove that $H\left(n,k\right)$ has an induced subgraph with more than $\alpha \left(H\left(n,k\right)\right)$ vertices and maximum degree at most $?\sqrt{n}?$. Chung et al. proved this statement for $k=2$ (the $n$‐dimensional cube).