Conjectura
Beta.Proofs cannot be submitted yet. The corpus is open to read, and we are looking for researchers to maintain a subject area.Maintaining a field →
← problemsGT002openMathematics/ Combinatorics/ Graph theory

Is the Ramsey number R(5,5) equal to 43?

Maintainer — open

How many people must be at a party before five of them are all mutual friends or all mutual strangers? Known to be between 43 and 46.

Motivation

R(4,4) = 18 has been known since 1955. R(5,5) is not known, and the search space is far beyond exhaustive checking.

Erdős' remark is the standard framing: if aliens demanded R(5,5) we should marshal all our computers to find it, but if they demanded R(6,6) we should attack them instead. The lower bound 43 has stood since 1989; the upper bound was reduced to 46 in 2024.

This problem is here partly to be honest about limits: a proof would be an enormous computation, and a computation is exactly what a kernel-checked corpus is well suited to record.

Lower bound Exoo 1989; upper bound 46 by Angeltveit and McKay 2024.

Lean API
import Conjectura.Defs.Mathematics.Combinatorics.GraphTheory.RamseyArrow

namespace Conjectura.GT002

/-- Is `R(5,5) = 43`? Erdős' remark that an alien civilisation demanding `R(6,6)`
should be fought rather than answered gives the flavour: the values are bounded but
essentially uncomputable, and this is the smallest unknown diagonal case. -/
def goal : Prop :=
  Conjectura.GraphTheory.ArrowsTo 43 5 5 ∧ ¬ Conjectura.GraphTheory.ArrowsTo 42 5 5

end Conjectura.GT002
Definition3
Ramsey arrowConjectura.GraphTheory.ArrowsTo

The Ramsey arrow n → (s, t): every two-colouring of the edges of the complete graph on n vertices contains either an s-set with all edges the first colour or a t-set with all edges the second. Ramsey's theorem says such an n always exists; the least one is the Ramsey number, and almost none are known.

def ArrowsTo (n s t : ℕ) : Prop :=
  ∀ c : Fin n → Fin n → Bool, (∀ x y, c x y = c y x) →
    (∃ S : Finset (Fin n), S.card = s ∧ ∀ x ∈ S, ∀ y ∈ S, x ≠ y → c x y = true) ∨
    (∃ T : Finset (Fin n), T.card = t ∧ ∀ x ∈ T, ∀ y ∈ T, x ≠ y → c x y = false)
FinsetFinset

structure

cardS.card

theorem

Related work1
  • R(5,5) ≤ 46Vigleik Angeltveit, Brendan McKay · 2024

    The current upper bound, by extensive computation.

For your AI
Download as .md
I am proving a theorem in Lean 4 and submitting it to Conjectura.

## Problem GT002 — Is the Ramsey number R(5,5) equal to 43?

How many people must be at a party before five of them are all mutual friends or all mutual strangers? Known to be between 43 and 46.

## Environment (fixed — do not assume anything newer)

- Lean toolchain: `leanprover/lean4:v4.33.0-rc1`
- Mathlib: `v4.33.0-rc1`

If a lemma you want does not exist in that Mathlib, prove it inline instead of
importing something newer.

## The exact statement I must prove

```lean
theorem solution : ArrowsTo 43 5 5 ∧ ¬ ArrowsTo 42 5 5 := by
  sorry
```

## The file I submit

```lean
import Conjectura.Problems.GT002.Statement

namespace Submission

theorem solution : Conjectura.GT002.goal := by
  sorry

end Submission

```

## The Lean definitions of every term in this problem

These are the actual definitions your proof will be checked against. Do not
substitute your own version of any of them.

### Ramsey arrow

The Ramsey arrow `n → (s, t)`: every two-colouring of the edges of the complete graph on `n` vertices contains either an `s`-set with all edges the first colour or a `t`-set with all edges the second. Ramsey's theorem says such an `n` always exists; the least one is the Ramsey number, and almost none are known.

```lean
Conjectura.GraphTheory.ArrowsTo
-- unfolds to:
def ArrowsTo (n s t : ℕ) : Prop :=
  ∀ c : Fin n → Fin n → Bool, (∀ x y, c x y = c y x) →
    (∃ S : Finset (Fin n), S.card = s ∧ ∀ x ∈ S, ∀ y ∈ S, x ≠ y → c x y = true) ∨
    (∃ T : Finset (Fin n), T.card = t ∧ ∀ x ∈ T, ∀ y ∈ T, x ≠ y → c x y = false)
```
Defined in this corpus.

### Finset

structure

```lean
Finset
```
Defined in Mathlib.

### card

theorem

```lean
S.card
```
Defined in Mathlib.

## Rules — submissions violating these are rejected automatically

1. **Do not change the name or type of `solution`.** It must satisfy the
   statement above exactly.
2. **Do not redefine or shadow anything from the problem's Statement module.**
   Declaring your own `goal`, or redefining a name it depends on, produces a
   proof of a *different* statement and is rejected. This is the single most
   common rejection.
3. **No `sorry`** anywhere, including in helper lemmas. It surfaces as the
   axiom `sorryAx` and is detected transitively through imports.
4. **No `native_decide`** — it surfaces as `Lean.ofReduceBool` and is not
   accepted, because it trusts compiled code rather than the kernel.
5. Only these axioms are permitted: `propext`, `Classical.choice`,
   `Quot.sound`.
6. Follow Mathlib style: hypotheses left of the colon, explicit types,
   `snake_case` theorem names, `UpperCamelCase` types.

## What I want from you

Here is my argument in informal mathematics:

> [PASTE YOUR PROOF SKETCH HERE]

Turn it into Lean 4 that compiles under the environment above and satisfies the
statement exactly. Where you are unsure a lemma exists in this Mathlib version,
say so explicitly rather than guessing a name.

Submissions are not open yet

Conjectura is in beta. You can read every statement, every definition and the Lean behind them, and download the exact files the checker uses — but proofs are not being accepted yet.

The reason is a deliberate order of operations. Accepting a proof means running a stranger’s code and standing behind a verdict, and no statement here yet carries a researcher’s name. A machine-checked answer to a question nobody has vouched for is worth very little, so the vouching comes first.

The English write-ups are also switched off during the beta. Nothing on this page is generated by a model.

Discussion

  • Nothing yet.

Sign in to take part.