Induced subgraphs of product graphs and a generalization of Huang's theorem

Zhen-Mu Hong, Hong-Jian Lai, Jian-Bing Liu

Recently, Huang showed that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional hypercube has maximum degree at least $\sqrt{n}$ in [Annals of Mathematics, 190 (2019…