google-deepmind / google-deepmind/formal-conjectures

Erdős 23: weighted cycle background special case with an external Lean proof

Open
#5,348 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Lean
Stars
1.3k
Forks
485
Avg merge
1d 20h
Merged PRs (30d)
327

Description

Propose adding a solved weighted special case to `FormalConjectures/ErdosProblems/23.lean`, with a linked external Lean proof.

In the Mycielski lift of the Clebsch graph, give each original vertex weight r, add h on the cycle (0,1,3,7,15), give the apex weight z, and give the twins arbitrary nonnegative weights b_v. For every r,h,z ≥ 0, there is a cut with monochromatic edge weight at most (16r + 5h + sum b_v + z)^2 / 25. Each undirected edge is counted once. The result includes zero weights and every boundary case.

The [proof note](https://github.com/SproutSeeds/erdos-problems/blob/68fbae4b2f6eba86f1b28d62b1b370bfabd7d92a/packs/graph-theory/problems/23/publication/cycle-background/PROOF.md) gives five closed regions and exact rational certificates. The [standalone Lean project](https://github.com/SproutSeeds/erdos-problems/blob/68fbae4b2f6eba86f1b28d62b1b370bfabd7d92a/packs/graph-theory/problems/23/publication/cycle-background/README.md) includes a complete proof of the [precise statement](https://github.com/SproutSeeds/erdos-problems/blob/68fbae4b2f6eba86f1b28d62b1b370bfabd7d92a/packs/graph-theory/problems/23/publication/cycle-background/P23CycleBackgroundSubmission.lean#L50), pinned dependencies, axiom audits and exact replay. The full Problem 23 remains open.

I plan to submit a small draft PR adding this variant, its graph and weight definitions, and three basic tests. Would this scope fit the collection?

AI assistance: OpenAI Codex developed and formalized the proof and prepared this contribution under my direction. Independent expert review and publication novelty review are still pending.

Contributor guide

Open the contributing guide

Research direction

Start with FormalConjectures/ErdosProblems/23.lean, then read the linked PROOF.md and P23CycleBackgroundSubmission.lean for the precise statement and proof structure. Add the weighted special case, graph and weight definitions, and three basic tests; the external proof should remain replayable with its pinned dependencies and audits.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.