Every problem here was open when it entered the pool.
Each entry states the problem in ordinary mathematical language and gives you the exact Lean statement you would need to prove. Nothing is paraphrased, so what you read is what gets checked.
Combinatorics
Erdős problem 579
Let δ>0. If n is sufficiently large and G is a graph on n vertices with no
K2,2,2
(the octahedron) and at least
δn2
edges, must
G
contain an independent
set of size
≫δn
?
This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83]. It is **open**; they proved
the statement for
δ>1/8
(see
erdos_579.variants.ehss_large_delta
), and the
difficulty is to push the edge-density threshold down to an arbitrary
δ>0
.
Here
K2,2,2
is the complete tripartite graph with all parts of size
2
, encoded as
completeMultipartiteGraph (fun _ : Fin 3 => Fin 2)
; "contains no
K2,2,2
" is expressed
via
SimpleGraph.Free
.
$3,898 bounty·nobody has started
week of 1 Oct 2025 · nothing publishedweek of 8 Oct 2025 · nothing publishedweek of 15 Oct 2025 · nothing publishedweek of 22 Oct 2025 · nothing publishedweek of 29 Oct 2025 · nothing publishedweek of 5 Nov 2025 · nothing published
Solve it
Nobody has attempted this. A complete proof or refutation takes the whole bounty.
1 Oct 2025nothing published against this one yet23 Sept 2026
erdosproblems.com/579
[EHSS83] P. Erdős, A. Hajnal, V. T. Sós and E. Szemerédi, More results on Ramsey–Turán type problems, Combinatorica 3 (1983), 69–81.
Something wrong with this formalization?
A statement that does not faithfully capture the original conjecture is the one real risk here, so we would rather hear about it early - before someone spends weeks on it.
Our channel is in the Bittensor Discord server. Join the server first, then open the channel to send your report.