{"id":"arxiv/2609.32903","url":"https://arxiv.org/abs/2609.32903","tags":["math.CO"],"score":0,"title":"On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs","domain":"math.CO","source":"arxiv","authors":["Elizaveta Popova"],"reviews":0,"subject":"math.CO","summary":"The following is a natural and fundamental question for a graph $G$: if an induced subgraph $H$ of $G$ has $x$ more vertices than a maximum independent set, what can be said about the maximum degree of $H$ as a function of $x$? The case $x=1$ is already of considerable interest. For example, in his celebrated proof of the sensitivity conjecture, Hao Huang showed that every induced subgraph of the hypercube $Q_n$ on more than $2^{n-1}$ vertices has maximum degree at least $\\sqrt{n}$. Chung, Fúredi, Graham, and Seymour proved that this bound is tight. In this paper, we study this question when…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{}}