Erdős Problem 86 · C₄-free hypercube subgraphs

Finite and asymptotic bounds by setting

Square-free subgraphs of Qₙ across finite dimensions Q₇ and Q₈ and the asymptotic edge-density limit Q∞.

Run: MathRSI v3 + primal–dual coevolution → methods inform v6.

Results by setting

SettingBoundVerification scope
Q₇ (n = 7)304304-edge construction verified; 304 upper bound as reported in the source package, not re-verified in this pass.
Q₈ (n = 8)682 ≤ ex(Q₈, C₄) ≤ 683Four 682-edge constructions & C++17 Q₄ replay verified; Theorem B reviewed in the same model family (independent refereeing pending); ex(Q₈, C₄) ≤ 682 open.
Q∞ (asymptotic)≤ 0.5912405943T3 (≤ 0.5912405943) and T4 with m = 1024 degree potential (≤ 0.5912405942) proved and rechecked in 128-bit C++20. Conjecture 1/2 open.

Q₇ · 128 vertices

304

Two explicit 304-edge C₄-free subgraphs (A.edges, B.edges) are checked directly in-repo (ex(Q₇, C₄) ≥ 304); 304 upper bound as reported in the source package, not re-verified in this pass.

Q₈ · 256 vertices

682–683

Four 682-edge constructions establish ex(Q₈, C₄) ≥ 682. Theorem B rules out 684 edges using 83 active cuts and 25 imported Q₆ DRAT certificates (checked computationally and reviewed in the same model family; independent refereeing pending).

Closing the remaining 1-edge gap to ex(Q₈, C₄) ≤ 682 is still open.

Asymptotic density Q∞: exact rationals T3 and T4

Both unconditional bounds improve the v3 certificate (< 0.59155154) and the 0.60318 reference, and both were rechecked in 128-bit C++20:

Five-line unconditional hypergeometric tower for T4 (all n ≥ 1024): (1) Sampling a uniform Q₄ face F ⊆ Qₙ and uniform v ∈ V(F) has the exact same joint law as sampling uniform v ∈ V(Qₙ), uniform S ∈ C([n], 1024), and uniform T ∈ C(S, 4) spanning F through v. (2) The local degree degG[F](v) depends only on (v, T). (3) Conditioning on (v, S) with retained degree dS(v) ∈ {0,…,1024}, hypergeometric expectation gives E[∑k=04 bk 1deg=k | v, S] = Φ1024(dS(v)) / C(1024, 4) ≥ μ1024 / C(1024, 4). (4) Summing over the 16 vertices of F by linearity of expectation requires no independence and holds identically for every n ≥ 1024. (5) Standard O(1/n) flag sampling collision error on Qₙ yields T4 unconditionally.

Exploratory notes & open questions
The exploratory value 0.5907 is an approximate completely positive fit with residual about 3.9 × 10⁻⁴, and an earlier Q₅ 0.5899 claim was refuted by a valid C₄-free graph (0x69966996699616682994, scoring 0.5922454) and withdrawn. Both ex(Q₈, C₄) ≤ 682 and Erdős’s asymptotic conjecture π□(C₄) = 1/2 remain open.

Primal–dual coevolution & same-graph finite pullback

Lower searchmutates Python builders under 4-channel signed residuals
Archive filterverifies C₄-freeness & tests cuts across all archived graphs
Full-domain checkexports surviving cuts to C++17 Q₄ & Q₆ pullback

Cuts that survive the archive filter are exported to the C++17 full-domain verifier; only inequalities that pass that check are used in Theorem B.

In Q₈, the coevolution engine separates the open proof goal (≤ 682) from the adversarial search target (683) and focuses parent selection on near-extremal graphs (≥ 680 edges) while testing candidate inequalities against every archived graph. Validated cuts feed Theorem B, which couples three probability measures on the same candidate subgraph H ⊆ Q₈ (uniform marked Q₄ completions, 3-degree edge incidences and global vertex degrees), yielding exact rational margin 782808475930428709 / 4209067950080000000000 > 0 and integer maximum −37440 across all 13,150,453 legal marked Q₄ completions.

Methods distilled into v6

  1. Separate the open proof goal from the adversarial search target, rotate normalized signed residuals, and test candidate cuts against the full graph archive.
  2. Stop outer floating-point SDP/CP loops once gains drop to the rounding-repair residual, recording any nonzero residual beside approximate fits.
  3. Couple local and global observables on the same finite candidate graph before invoking subcube imports.

Checks and archive layout

Both 128-bit C++20 verifiers for T3 and m = 1024 T4 recompile and check all 3,212,821 Q₄ orbits from repository files, alongside the two 304-edge Q₇ constructions, four 682-edge Q₈ constructions, exact Q₈ rational combination, C++17 13,150,453-completion enumeration, v3 Q₄ baseline replay and all 18 cube_coevolve unit tests.

Large solver traces stay in external archives to fit normal Git limits: the 21 Q₇ .cnf/.drup files were omitted in the upstream 2026-10-31 compilation, while Q₈’s 25 Q₆ DRAT traces (about 555 MiB) and .npz discovery pools live in the Q8_C4_upper683_20261116 archive; each INVENTORY.json lists filenames and hashes so those certificates can be replayed with drat-trim.

Historical v3 Q₄ report (< 0.59155154) ↗中文 · Case study & verification table ↗ · Hypercube extremal plugin ↗ · v6 workflow changes ↗

Back to evolution ↑ · Back to results ↑

MathRSI · GitHub ↗