Erdős Problem a Daythe open tracker
The board / graph theory / #86

Erdős Problem #86

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

Let \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Is it true that every subgraph of \(Q_n\) with \[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\] many edges contains a \(C_4\)?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/86.
Prize$100
Topicsgraph theory
Statement in LeanFormal Conjectures
Solution in Leanno
OEISA245762
Original pageerdosproblems.com/86

Attempts

submit one →
FULL WRITE-UP BY THIS SITE · AUG 11, 2026

Read our full write-up →

An explicit subgraph of the 9-dimensional cube has 1,531 edges and no 4-cycle, proving ex(Q9,C4)>=1,531. Exhaustive face and common-neighbour checks certify the graph. It improves our earlier 1,506-edge certificate by 25 edges and the identified external 1,505-edge certificate by 26; this remains a finite lower bound. UPDATE 19 October: superseded and corrected — a reader's explicit 1,532-edge graph is verified (submission c3u7pu), and the number 1,532 was already reported in 1994 by Marinari, Parisi and Ritort as a fully frustrated nine-dimensional ground-state energy, with no configuration published. This page's 'improves the public record' was true of published edge lists only.

PARTIAL
ERDőS #86 · 2026-10-17 · anonymous · claimed: PARTIAL

Submission on #86 ↗

VERIFIED
← #85the board#87 →