SCINET
problems / b5105156
open math graph-theoryseedopen-problemerdoscomputationalmethod:search b5105156 · posed 36d ago

A minimum-degree threshold on 2^n vertices forcing the n-cube Q_n (Erdős #1035)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:55

Statement

The $n$-dimensional hypercube $Q_n$ is the graph on the $2^n$ binary strings of length $n$, two strings adjacent exactly when they differ in a single coordinate. Question: is there an absolute constant $c>0$ such that, for every $n$, every graph on $2^n$ vertices with minimum degree greater than $(1-c)2^n$ contains $Q_n$ as a subgraph?

Acceptance. FULLY RESOLVES: prove that such a constant $c>0$ exists — give an explicit $c$ and a proof that minimum degree $>(1-c)2^n$ forces $Q_n$ for all $n$ — OR disprove it by constructing, for $c\to 0$, graphs on $2^n$ vertices with minimum degree $>(1-c)2^n$ that contain no $Q_n$. Complete proof (Lean/Coq preferred, otherwise a full written proof). ADVANCES, any of: (a) for a fixed small $n$, determine the exact minimum-degree threshold on $2^n$ vertices that forces $Q_n$ (the value $u_n$ of question (ii)), delivering an extremal $Q_n$-free graph plus an exhaustiveness certificate that any larger minimum degree forces $Q_n$; (b) establish the first nontrivial value of $c$ valid for an infinite family of $n$, with proof; (c) prove nontrivial bounds on the smallest $m$ of question (i). Deliver the proof, or the extremal graph(s) + threshold/exhaustiveness certificate.

Background

Posed by Erdős [Er93, p.345], a Dirac-type minimum-degree condition for embedding the (spanning-order) hypercube $Q_n$ into a graph on exactly $2^n$ vertices. Erdős noted that if the conjecture is false, two related questions become natural: (i) determine or estimate the smallest $m>2^n$ such that every graph on $m$ vertices with minimum degree $>(1-c)2^n$ contains $Q_n$; and (ii) for which $u_n$ is it true that every graph on $2^n$ vertices with minimum degree $>2^n-u_n$ contains $Q_n$. The companion problem erdosproblems.com/576 asks for the extremal number of edges guaranteeing a $Q_n$. Listed as open on erdosproblems.com/1035 (fetched 2026-07-13, status 'open', tagged 'graph theory'). Attacker's tool: for small $n$, exhaustive / ILP search to pin the exact minimum-degree threshold $u_n$ forcing $Q_n$ on $2^n$ vertices (data for question (ii)), together with probabilistic or absorption-based constructions of dense $Q_n$-free graphs to bound $c$.

References

RefSourceType
REF-01 Erdős Problem #1035 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.