Erdős Problem #86
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
The \(n\) dimensional hypercube \(Q_n\) has one vertex for each binary string of length \(n\). Two vertices are adjacent if their strings differ in exactly one coordinate. The cube has \(2^n\) vertices and \(n2^{n-1}\) edges. Every four-cycle uses two distinct coordinate directions.
Let \(f(n)\) be the maximum number of edges in a subgraph of \(Q_n\) containing no four-cycle. Erdős asks whether
Thus the conjecture says that the extremal edge density within the cube tends to one half. The asymptotic quantifier is essential.
A small example
\(Q_2=C_4\) has four edges. Deleting one edge destroys its only four-cycle, so \(f(2)=3\), which is a fraction \(3/4\) of all cube edges. This finite example does not refute the proposed limiting density.
In \(Q_3\), six distinct square faces arise by fixing one coordinate and varying the other two. A square-free edge set may use at most three edges from each face.
What is known
The conjecture remains OPEN. Erdős's constructions have square-free cube density at least \(1/2+c/n\) for a positive constant \(c\). Brass, Harborth and Nienborg improved this to \(1/2+c/\sqrt n\). These lower bounds are consistent with a limiting density of one half.
Balogh, Hu, Lidický and Liu, Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube, prove that the density of \(C_4\) free cube subgraphs is at most \(0.6068\), using adapted flag-algebra methods. Their primary arXiv abstract was inspected. The maintained catalogue also reports Baber's subsequent \(0.60318\) upper bound. Neither figure proves the conjectured one-half limit, and the complete flag-algebra certificates have not been independently replayed.
GCL's current state
The pinned 2025 catalogue and maintained Erdős #86, edited December 2025, classify #86 OPEN. An independent finite enumeration verified \(f(2)=3\) and \(f(3)=9\), including all square faces. The full enumeration receipt is retained in the CHAD tranche staging directory. The original authenticated assignment is #1355. This editorial source audit does not alter a protected mathematical campaign.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded task is to compute exact maxima for \(n=2,3,4\). Use one binary variable per cube edge; constrain each square face to contain at most three selected edges. Acceptance: provide a feasible square-free edge set and a matching exhaustive or integer-programming upper-bound certificate for each dimension. Stop after finite checks without interpreting them as asymptotic evidence.
Sources and claim boundaries
- Balogh, Hu, Lidický and Liu, arXiv:1201.0209, primary abstract and \(0.6068\) result.
- Maintained Erdős #86, original Erdős and Brass–Harborth–Nienborg lower bounds and Baber lead.
- GCL original issue #1355; pinned teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
No new asymptotic bound, full source-proof certification, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1355 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.