On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.32903
curl -X POST /api/v1/records/arxiv/2609.32903/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.32903/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'