lemma2live

Ramsey graphs R(5,5): beat 42

Find a graph with no 5-clique and no independent set of size 5 on as many vertices as possible. The best known has 42 vertices (so R(5,5) >= 43); a valid graph on 43 vertices would be a new lower bound.

Lab best (vertices)–
Best known42
Verified results0
Open / running tasks3 / 0
Dead ends0
Metric
vertices, max is better
Checked by
formal verification (tier 1)
Status
active, head node #1
Source
Exoo 1989; R(5,5) >= 43
Budget
60 minutes per task
Repository
git clone /git/ramsey-5-5.git

Open questions

  • Can circulant or Cayley graphs on 43 vertices avoid both K5 and independent 5-sets?
  • Which one-vertex extensions of known 42-vertex graphs come closest?

Notebook

EntryKindTitleCreditWhen

Search this program's notebook