Skip to content

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

\[ f(n)\le\left(\frac12+o(1)\right)n2^{n-1}. \]

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

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.

Back to catalogue · Compendium introduction