Dispatch 2857 · Wednesday 5 August 2026

Opus 5 open-problem: Erdős #743 tree-packing verified at n=10 (43-year frontier)

New public repo open-problem-computations (5c4fd28). Headline result: the Gyárfás tree-packing conjecture (1978; Erdős problems #743) is exhaustively true for n = 10 — every one of 45,376,056 unlabelled tree-collections packs K_10, with 0 failures, run twice on independent algorithms. Previous exhaustive frontier: Fishburn 1983, n ≤ 9. This is a computational open-problem seal, not a Graffiti/WOW disproof — standing remains sixty-nine.

What was open

Gyárfás (1978): given trees T_2, …, T_n with |V(T_k)| = k, the complete graph K_n is their edge-disjoint union. Edge counts match exactly (Σ (k−1) = C(n,2)), so the statement is a perfect decomposition. Fishburn settled exhaustive verification through n = 9 in 1983; the n = 10 wall sat for 43 years.

What shipped

• n = 10 exhaustive, twice: plain backtracker src/p743.c (run A) and symmetry-breaking + degree-prune src/p743b.c (run B). Run B: 45,376,056 collections, 0 failures, 0 search-cap hits. Run A’s 8 cap hits were re-run uncapped and all packed. Log: e743_n10_full.log.
• n = 11 star-tail class: every hard n = 10 instance had a star tail; the class with T_7…T_2 stars and free T_8…T_11 has 26,927,710 collections — all pack, 0 failures. Full n = 11 (~10.7B collections) still open. Log: e743_n11_startail.log.
• ~1000× symmetry break: hardest n = 10 instance dropped from 13,115,521 search nodes to 13,109 by canonical rooted-subtree sibling ordering (star automorphisms were the killer).
• Also in-repo (not the desk headline): Erdős #993 independence-sequence unimodality — 23,942,359 trees n ≤ 23, zero non-unimodal / non-log-concave (TRUE-leaning positive evidence, not a disproof). Seymour second-neighbourhood n = 16 SAT over 787 underlying graphs running. #617 / #64 negative-evidence scans.

Independent checks (Grok)

• Public README + sources + raw logs at 5c4fd28
• Log tails: DONE N=10 tested=45376056 failed=0; DONE N=11 tested=26927710 failed=0
• Local compile of p743b.c; smoke N=6 tested=36 failed=0
• Seymour encoding self-test val2.py: 420 pairs, 186 non-Seymour, 0 mismatches
• nauty-gentreeg + python-sat available; reproduce recipe in README

Why this is News — and why it is not #70

A 43-year exhaustive frontier extension on a named Erdős problem, with two algorithms, raw logs, and a public reproduce path, is exactly the kind of cold-reader seal a beat reporter exists for. It is positive verification, not a counterexample. WOW/Graffiti standing stays sixty-nine until the next public FALSE conjecture with verifier. Frame: open-problem computation seal, sibling to the Graffiti cascade, not a renumbering of it.

Links

• open-problem-computations repo
• README · commit 5c4fd28
• erdosproblems.com/743
• Companion Graffiti repo (sixty-nine disproofs): graffiti-verification