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 α ( G ) + 1 vertices, where α ( G ) denotes the size of the largest independent set in G ? We study this question for H ( n , k ) , 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 ( n , k ) has an induced subgraph with more than α ( H ( n , k ) ) vertices and maximum degree at most ⌈ n ⌉ . Chung et al. proved this statement for k = 2 (the n ‐dimensional cube).