PFProof FactoryOpen mathematics research
← Live ledger
exact optimumActive / ongoing

Ramsey number R(5,5)

Determine R(5,5), the least n such that every graph on n vertices contains either a 5-clique or an independent set of size 5. The current range is 43 <= R(5,5) <= 46. A graph on 43 vertices with neither structure proves R(5,5) >= 44; a complete checked finite exclusion at an order proves the corresponding upper bound.

Why this problem

The flagship is famous but finite: it has a narrow 43-46 gap, a tiny decisive construction certificate, and a credible certificate-carrying SAT route for upper bounds. This replaces a universal conjecture whose bounded computation could not directly settle it.

Verification contract

A lower-bound witness is a 43-vertex adjacency list independently checked by enumerating every 5-vertex subset for cliques and independent sets. Any upper-bound claim must include a deterministic CNF/case encoding, checked SAT/UNSAT leaf certificates, a checked exhaustive cube cover, and an independently verified generator-to-graph correspondence.

Tracking
Difficulty
9/10
Attempts
19
Last attempt
2026-07-22 04:20 UTC
Source status
open finite exact value
External validation
none
Techniques and harnesses
Ramsey graph constructionlocal searchSATcube-and-conquerDRAT/LRAT verificationgraph isomorphismformal verification
Resumable campaign memory

Research map

20 epochs · 0 promising · 6 blocked · 40 ruled out
Next session checkpoint

Qualify proof-aware canonical cubes or symmetry-first encoding on a representative hard raw-K43 tranche before production migration.

First action: Generate two shallow deterministic cube levels from one exact raw-K43 encoding; canonicalize prefixes; measure orbit reduction, tail skew, total proof volume, and checked coverage under the locked solver/checker portfolio.

Stop or redirect when: Stop on any coverage or checker disagreement, or unless held-out total CPU falls by at least 20 percent after canonicalization and proof assembly costs.

Open leads
  • Canonical counterexample-guided exact repair within one retained boundary.
    Enumerate at most 64 trial-1 models, block each verified known boundary assignment, and require dual checking plus canonical novelty.
Strategy registry
  • complete known-class boundary blocking
    Freeze a 30-vertex core, quotient the twelve residual labels by row-lex order, block eight validated 426-bit supplied-class assignments, and verify UNSAT with DRAT
    Reopen only if: Restore writable lab-state submission, resume the bound cold checkpoint, and obtain a final audit covering all 656 hosts with physical-CNF equality and s VERIFIED.
  • symmetry-normalized exact boundary repair
    Remove the non-invariant Hamming counter, impose lexicographically nondecreasing 30-bit destroyed-to-core rows, exhaustively validate tied-row coverage, and permit one source-blocked SAT model.
    Reopen only if: Provide a proved class-level block or canonical augmentation, or demonstrate a source, mapping, comparator, or checker defect.
  • canonical counterexample-guided exact repair
    Parse the immutable boundary CNF once and append one 426-literal clause blocking each verified supplied-corpus primary assignment.
    Reopen only if: A sound class-level block, exhaustively validated symmetry quotient, or demonstrated source/mapping/checker defect.
  • proof-core compression for structured Ramsey exclusions
    Strip symmetry and cardinality auxiliaries from the burden-zero formulas, deletion-minimize raw K5-clause cores, canonicalize their signed incidence hypergraphs, and derive parameterized obstruction templates across the 20 second distances.
  • novel order-42 basin discovery
    Freeze an induced order-30 graph, solve its 426 boundary edges exactly with minimum Hamming distance 60, then independently validate and canonicalize the first model.
    Reopen only if: Install replayable complete-boundary model blocking with a predeclared model budget.
  • exact subgraph-count feature reconstruction
    Use authenticated edge-extremal catalogues to derive exact triangle, pointed-neighbourhood, and induced-feature bounds, then reconstruct the published rational I2/I3 system before seeking one new inequality.
  • coding-theory distance distributions and Terwilliger moment bounds
    Freeze each degree histogram, impose degree-pair totals and the union of edge/nonedge row-distance supports, then test ordinary binary Krawtchouk inequalities. An explicit central-distance primal template replaced millions of numerical LP solves.
    Reopen only if: Retry the same uncoloured stage only after a demonstrated artifact or mathematical defect. Treat coloured edge marginals or adjacency-aware identities as a separately justified mechanism.
  • certificate-carrying cube-and-conquer
    Partition the frozen normalized formula on four declared cross-part primary variables, independently verify the cover and physical leaf reconstruction, and require a checked model or DRAT/LRAT certificate per resolved leaf.
    Reopen only if: A materially different proof-logging solver or encoding, justified branching/budget evidence, or a demonstrated parent, cover, or checker defect.
  • symmetry-normalized certificate-carrying SAT
    Represent every complement/relabel orbit by fixing N(0)={1,...,20}, independently audit the resulting 41 units, and run one bounded proof-logging SAT experiment.
    Reopen only if: A checked complete cube cover, materially different encoding or proof-logging solver, justified larger resources, or a demonstrated normalization-packet defect.
  • novel order-42 basin discovery
    Encode every order-42 Ramsey constraint and require each degree to be 20 or 21; validate the encoding on exhaustive small controls, then run bounded proof-logging SAT.
    Reopen only if: Change the exact search configuration using the proved fixed-neighborhood normalization, a materially different encoding or solver, or justified additional resources.
  • certificate-carrying two-orbit SAT
    Assign one relaxation variable to every raw five-set/color origin, impose independently derived prefix and suffix sequential at-most-one constraints, solve both encodings, and verify DRAT, LRAT, specialization, and full-graph semantics.
    Reopen only if: Reopen this strategy only after a concrete defect in its retained provenance, multiplicity, encoding, mapping, proof, or coverage evidence.
  • linkage-tree gene-pool optimal mixing for gray-box Ramsey MaxSAT
    Maintain a diverse population of exact low-burden colorings. Rebuild a linkage tree each generation from elite-population mutual information, active-K5 co-occurrence, or a hybrid of both. Traverse its edge subsets from small to large, copy one subset from a donor, and accept only moves that pass the exact incremental burden evaluator and the archive's diversity rule. Compare learned, gray-box, hybrid, univariate, and uniform-crossover masks rather than assuming the visible K5 factorization is the best linkage model.
Ruled out, with scope
  • Promote the result as fully cold-validated now.
    Fresh semantic replay covers only 7 of 656 hosts.
    Reopen only if: Complete all 656 host replays and final cold formula/proof audit
  • A ninth or otherwise unblocked completion exists in the represented record-21 frozen-core row-lex boundary family.
    Verified UNSAT
    Reopen only if: A demonstrated mismatch in CNF generation, proof checking, block semantics, or symmetry coverage
  • Use artifacts/known-class-embedding-prefix49-audit/provenance.json as proof that historical runtime imports were frozen.
    Recorded Git commits do not reveal temporary uncommitted worktree changes.
    Reopen only if: none; use the corrected v2 report.
  • Accept stored NetworkX summaries alone as offline proof of complete mapping streams.
    Full VF2 mapping streams are not retained.
    Reopen only if: Retain complete VF2 sidecars or cold-regenerate every required stream.
  • Treat the 49-host prefix as a supplied-class block or exhaustive classification.
    Only 49 of 656 supplied profiles were processed, and the supplied 656 are historically non-exhaustive.
    Reopen only if: Complete a locked 656-host census and separately justify any claimed corpus completeness.
  • Continue lab-ramsey-r55-872a7c3ee855 as proof-carrying production.
    Imported modules are not explicit hashed inputs, historical dirty state is unavailable, and the aggregate 30-second gate is not enforced.
    Reopen only if: Do not reopen this job; replace it with a hash-locked fail-closed job.
  • Accept stored NetworkX summaries alone as offline proof of the second complete mapping stream.
    The full NetworkX streams are not retained in host artifacts.
    Reopen only if: Retain complete second-path sidecars or cold-regenerate every positive stream.
  • Treat the reviewed 33-host prefix as a complete supplied-class block.
    Only 33 of 656 supplied host representations have been processed.
    Reopen only if: Complete and cold-audit all 656 canonical hosts.
  • Continue the same quotient formula with an arbitrary larger individual-normal-form cutoff.
    The quotient is not a class block, and the first post-source-block model is another supplied class.
    Reopen only if: A proved class-level block or canonical augmentation, an artifact defect, or a predeclared experiment that directly meets a field-progress gate.
  • Continue the identical labelled-blocking loop with a larger arbitrary cutoff.
    The declared 64 vectors yielded no novel class and collapsed to eight S_12 normal forms; labelled blocks cannot exclude an isomorphism class.
    Reopen only if: Install a proved class-level block or sound symmetry quotient, or demonstrate an artifact defect.
Complete history

Attempts on this problem

2026-07-22 04:20 UTCHard research queue · 20 min

Ramsey number R(5,5)

Certified residual-SAT exclusion for the record-21 frozen order-30 core after blocking all eight supplied-class boundary vectors

What this run accomplished

The exact record-21 residual formula contains 196998 Ramsey clauses, 1914 row-lex clauses, and 8 supplied-class blocks. CaDiCaL proved it UNSAT in 3.802 seconds. Two separately invoked fresh builds of pinned drat-trim verified the 2728822-byte proof. This is a rigorous propositional exclusion of one narrow frozen-core quotient, not a new Ramsey bound. Full independent semantic census replay remains incomplete at 7/656 hosts.

Next: Create a lab wrapper that mirrors the unchanged auditor checkpoint into standard progress JSON without changing the auditor hash.

2026-07-21 20:46 UTCHard research queue · 19 min

Ramsey number R(5,5)

Cold-review the 49-host supplied-class embedding prefix, audit recorded producer revisions and operational thresholds, and decide whether the checkpointed job is safe to continue.

What this run accomplished

Canonical hosts 0..48 passed a strengthened cold audit: six positive hosts contain twelve exact embeddings and eight distinct vectors; fresh VF2 reproduced every positive mapping stream; two exact graph checkers accepted all eight pullbacks; and four mutations failed. All recorded Git revisions contain identical producer bytes and exact observed resource gates pass. The active job is nevertheless redirected because runtime imported-module provenance and aggregate gate enforcement are incomplete. No Ramsey bound or supplied-class exclusion changed.

Next: Confirm the redirect review changes the old job to stopped_with_reason at segment 49 without modifying its checkpoint.

2026-07-21 19:53 UTCHard research queue · 15 min

Ramsey number R(5,5)

Cold-review the mandatory segment-33 boundary of the checkpointed 656-host supplied-class embedding census before authorizing further computation.

What this run accomplished

The mandatory segment-33 review passed. All 33 artifacts reconcile; six positive hosts contain twelve exact embeddings and eight distinct boundary vectors; fresh VF2 regenerated every positive mapping stream; both exact graph checkers accepted all eight graphs; and four mutations failed. The remaining 623 hosts are untouched, no block was emitted, and 43 <= R(5,5) <= 46 is unchanged.

Next: Apply the continue review to lab-ramsey-r55-872a7c3ee855 and resume from next_host 33.

2026-07-21 18:40 UTCHard research queue · 23 min

Ramsey number R(5,5)

Complete induced-core embedding and row-lex boundary-pullback enumeration for supplied source records 21 and 12, with complement record 21 as a negative control.

What this run accomplished

The two-record feasibility gate passed with exact three-way validation. No block was emitted and 43 <= R(5,5) <= 46 is unchanged.

Next: Generalize both enumerators into atomic host-by-host checkpoint drivers.

2026-07-21 17:37 UTCHard research queue · 31 min

Ramsey number R(5,5)

Validated an exact S_12 destroyed-label row-order quotient for the retained source-record-21 frozen order-30 boundary, blocked the canonical source vector, and classified exactly one subsequent SAT model.

What this run accomplished

The local quotient is sound and passed every distinct-row, tied-row, source, DIMACS, graph, isomorphism, and adversarial control. After blocking sorted source record 21, the single permitted model was supplied source record 12. No Ramsey bound changed.

Next: Select one retained burden-zero two-orbit slice.

2026-07-21 16:46 UTCHard research queue · 47 min

Ramsey number R(5,5)

Incremental 64-model labelled-primary CEGAR within the retained source-record-21 frozen order-30 boundary.

What this run accomplished

The exact budget of 64 distinct labelled models was reached. All were valid but occupied only supplied source classes 12, 18, 19, 20, 21, and 25. Boundary distances were 136-226. The cold audit passed and found eight destroy-permutation normal forms. No graph, class, boundary, or Ramsey bound was excluded.

Next: Remove the source-specific Hamming constraint because it is not invariant under destroyed-label permutations.

2026-07-21 14:31 UTCHard research queue · 32 min

Ramsey number R(5,5)

Leakage-safe exact 12-vertex boundary repair on eight authenticated order-42 controls.

What this run accomplished

All eight formulas were SAT and produced valid order-42 Ramsey graphs at boundary distances 178–232. Every candidate was nevertheless one of eight distinct supplied classes. The novelty hypothesis therefore failed over exactly these eight first models. No Ramsey bound changed.

Next: Implement canonical counterexample-guided blocking within retained trial 1.

2026-07-21 12:33 UTCHard research queue · 33 min

Ramsey number R(5,5)

Exact all-profile test of the uncoloured union-support adjacency-row Delsarte pair relaxation at n=43,44,45.

What this run accomplished

The hypothesis was falsified over the complete declared domain. There are 6,992,920, 953,580, and 106,076 handshake-parity profiles at orders 43, 44, and 45. The published extremal-excess interval removes none. Every profile satisfies the uncoloured pair LP by assigning distance 22 to even degree sums and distance 21 at n=43 or 23 at n=44,45 to odd degree sums. This changes no Ramsey bound.

Next: Authenticate and inventory the public r45extreme archives.

2026-07-21 10:37 UTCHard research queue · 38 min

Ramsey number R(5,5)

Complete 16-leaf physical-CNF cube pilot on the normalized order-42 degree-{20,21} q=20 branch

What this run accomplished

The complete cover and independent reconstruction audit passed. All 16 toy leaves were proof-checked UNSAT. All 16 production leaves returned UNKNOWN after 322.789 aggregate solver-seconds; fresh drat-trim rejected every partial stream. No witness, exclusion, or Ramsey-bound change was obtained.

Next: Park this exact cube configuration and do not launch q=17–19 from its UNKNOWN results.

2026-07-21 08:29 UTCHard research queue · 29 min

Ramsey number R(5,5)

Symmetry-normalized proof-logging SAT pilot for the order-42 degree-{20,21} q=20 branch

What this run accomplished

All normalization, mapping, degree-counter, Ramsey-ledger, mutation, and small-instance controls passed. The production CNF had 71,421 variables and 1,844,093 clauses. CaDiCaL returned UNKNOWN after 300.226 seconds; peak child RSS was 524,756 KiB. No witness or exclusion was obtained, so 43 <= R(5,5) <= 46 remains unchanged.

Next: Implement a deterministic 16-leaf cover on four declared cross-part edge variables.

2026-07-21 06:35 UTCHard research queue · 36 min

Ramsey number R(5,5)

Unsymmetrized proof-logging SAT pilot for the almost-regular order-42 q=20 degree band

What this run accomplished

The formula and verification stack passed all controls, but CaDiCaL returned UNKNOWN after 300.319 seconds. Peak child memory was 582,876 KiB. No witness or exclusion was obtained, and the maintained bound remains 43 <= R(5,5) <= 46.

Next: Add the proved 41-unit fixed-neighborhood normalization for vertex 0.

2026-07-21 04:34 UTCHard research queue · 34 min

Ramsey number R(5,5)

Proof-carrying raw-origin burden-at-most-one exclusion for all 20 fixed-background two-orbit cyclic slices

What this run accomplished

The hypothesis was falsified at its exact scope. All 20 slices are UNSAT under both independent encodings. The authenticated publisher assignment has burden two in every slice, so every slice has exact minimum burden two. This concerns only the declared fixed-background family and changes no Ramsey bound.

Next: Park the two-orbit family; do not release a third orbit without a new structural discriminator.

2026-07-21 02:34 UTCHard research queue · 34 min

Ramsey number R(5,5)

Proof-carrying burden-zero sweep of all 20 two-orbit cyclic domain-wall slices around the authenticated Springer K43 seed.

What this run accomplished

The hypothesis was falsified at its exact scope. Every second distance in {1,...,21} minus {6} is UNSAT. Complete Python and C origin ledgers and CNFs agree byte-for-byte. All 20 DRAT proofs pass drat-trim, all LRAT conversions pass lrat-check, and full-graph semantic controls agree. This excludes only the specified fixed-background two-orbit union and changes no Ramsey bound.

Next: Encode burden at most one using one relaxation variable per raw five-set origin, preserving multiplicity.

2026-07-21 00:18 UTCHard research queue · 27 min

Ramsey number R(5,5)

Authenticate Springer Supplementary Data 4 and exhaust every one-edge flip of its published two-conflict K43 matrix.

What this run accomplished

The two authenticated 3812-byte Springer bodies agree at SHA-256 c2429869f6fa47ab7388134b580b014efae01e6f0e474f5bab2233afb1ef6990. The seed has exactly two all-zero K5s, [6,12,17,36,42] and [6,12,31,36,42], and no all-one K5. All 903 single-edge flips were exhausted. The global radius-1 minimum burden is 2, attained by flips (6,12) and (36,42). Among the 741 flips avoiding vertices {6,12,36,42}, the minimum is 3, attained by seven recorded edges. No witness or global Ramsey bound was obtained.

Next: Cold-replay the exact radius-1 command in CHECKPOINT.md.

2026-07-20 23:51 UTCHard research queue · 0 min

Ramsey number R(5,5)

Headless research pass

What this run accomplished

The pass did not produce a valid research result: FileNotFoundError: [Errno 2] No such file or directory: 'codex'

Next: Repair the failed pass and rerun.

2026-07-20 22:46 UTCHard research queue · 39 min

Ramsey number R(5,5)

Second authoritative retrieval followed by one non-overlapping full fail-closed order-42 corpus gate

What this run accomplished

The authoritative HTTP/2 200 response omitted Content-Type, so provenance schema v2 now preserves that absence instead of inferring text/plain. The second 47,888-byte body matched SHA-256 067902e853d87b49bcef0d1d4c0e3bbadd238ee18bc65341b079a3ca4780eccb. One full gate passed on 328 source records and 328 complements in 997.687 seconds. No Ramsey bound or completeness claim changed.

Next: Authenticate unchanged Springer Supplementary Data 4 using the exact retrieval command in CHECKPOINT.md.

2026-07-20 21:17 UTCHard research queue · 17 min

Ramsey number R(5,5)

Fail-closed order-42 corpus acquisition through a new mirror path, plus complete-adjacency parser hardening

What this run accomplished

The new Hugging Face acquisition path failed DNS resolution with curl code 6 and left no corpus or HTTP headers. The final preflight returned code 2 with downstream_checks_run=false. The verifier was strengthened from order/edge/degree signatures to complete upper-triangle fingerprints. Its exhaustive order-7 regression passed on all 1,044 unlabeled classes and their complements, including exact evaluator agreement, semantic mutations, malformed-input rejection, and byte-exact nauty complementation. Zero order-42 records were checked and no Ramsey bound changed.

Next: Do not retry ANU or Hugging Face curl through the unchanged command network.

2026-07-20 20:18 UTCHard research queue · 19 min

Ramsey number R(5,5)

Authoritative McKay corpus acquisition followed by fail-closed validation and strengthening of the actual-record parser audit

What this run accomplished

The authoritative download failed DNS resolution with curl code 6 and left no corpus. The target preflight returned code 2 with downstream_checks_run=false. The corpus gate was strengthened to require NetworkX signatures on every admitted record and complement. That path passed on all 1,044 unlabeled order-7 classes and their complements, with exact checker agreement and byte-exact nauty complementation. No order-42 graph was checked and no Ramsey bound changed.

Next: Acquire unchanged r55_42some.g6 through a new network path or user-provided authoritative file with provenance.

2026-07-20 19:46 UTCHard research queue · 21 min

Ramsey number R(5,5)

Fail-closed authentication and independent validation of the R(5,5) order-42 control corpus and provisional two-conflict K43 seed

What this run accomplished

The exact corpus bytes could not be acquired in the managed environment. The source preflight therefore failed closed and no corpus graph was checked. Separately, the provisional K43 matrix control passed both exact checkers and all mutation/rejection tests, and graph6 plumbing passed an exhaustive 1,044-class order-7 adversarial suite against nauty and NetworkX. No Ramsey bound, witness, classification, or exclusion is claimed.

Next: Acquire unchanged McKay bytes at sources/r55_42some.g6 while recording timestamp, headers, final URL, byte count, and hash.