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.
Erdős Problem 86 · C₄-free hypercube subgraphs
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.
| Setting | Bound | Verification scope |
|---|---|---|
| Q₇ (n = 7) | 304 | 304-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₄) ≤ 683 | Four 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.5912405943 | T3 (≤ 0.5912405943) and T4 with m = 1024 degree potential (≤ 0.5912405942) proved and rechecked in 128-bit C++20. Conjecture 1/2 open. |
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.
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.
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.
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.
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 ↗