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

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), 949–955]. In this paper, we discuss the induced subgraphs of Cartesian product graphs and semi-strong product graphs to generalize Huang’s result. Let ${\mathrm{\Gamma }}_1$ be a connected signed bipartite graph of order $n$ and ${\mathrm{\Gamma }}_2$ be a connected signed graph of order $m$. By defining two kinds of signed product of ${\mathrm{\Gamma }}_1$ and ${\mathrm{\Gamma }}_2$, denoted by ${\mathrm{\Gamma }}_1\tilde{\mathrm{\square }}{\mathrm{\Gamma }}_2$ and ${\mathrm{\Gamma }}_1\tilde{\bowtie }{\mathrm{\Gamma }}_2$, we show that if ${\mathrm{\Gamma }}_1$ and ${\mathrm{\Gamma }}_2$ have exactly two distinct adjacency eigenvalues $\pm {\theta }_1$ and $\pm {\theta }_2$ respectively, then every $(\frac{1}{2}mn+1)$-vertex induced subgraph of ${\mathrm{\Gamma }}_1\tilde{\mathrm{\square }}{\mathrm{\Gamma }}_2$ (resp. $\Gamma_1\widetilde{\bowtie} \Gamma_2$)hasmaximumdegreeatleast$\sqrt{\theta_1^2+\theta_2^2}$(resp\mathrm{.}$\sqrt{(\theta_1^2+1)\theta_2^2}$)\mathrm{.}Moreover,wediscusstheeigenvaluesof$\Gamma_1\widetilde{\Box} \Gamma_2$and$\Gamma_1\widetilde{\bowtie} \Gamma_2$andobtainasufficientandnecessaryconditionsuchthatthespectrumof$\Gamma_1\widetilde{\Box}\Gamma_2$and$\Gamma_1\widetilde{\bowtie}\Gamma_2$ are symmetric, from which we obtain more general results on maximum degree of the induced subgraphs.