evidence boundary
supportsfrontiers / frontier
Erdős problems frontier
- id
- vfr_37aec80d874a0239
- license
- CC-BY-4.0
- findings
- 1,256
- accepted core
- 6
- contested
- 0
- links
- 17
- sources
- 1,234
- evidence
- 1,256
- avg conf
- 0.98
e1271/1271 · statement.attested · reviewer:will-blair · 2026-06-10 · null→null
Evidence atom
back to sources{"artifact_id":"va_9bc926d75e4e3881","artifact_packet_id":"cap_61973ee16b553d57","candidate_claim_id":"vc_d3acac56ca207093"}
- id
- vea_46ae4e2902eedb0b
- frontier
- Erdős problems frontier
- source
- vs_65c0ec4034c749f3
- finding
- vf_b9e7b2d1475382f3
finding binding
boundopen_question
Erdős Problem #1080 has status 'disproved (lean)'. Statement: Let $G$ be a bipartite graph on $n$ vertices such that one part has $\lfloor n^{2/3}\rfloor$ vertices. Is there a constant $c>0$ such that if $G$ has at least $cn$ edges then $G$ must contain a $C_6$? The answer is no, as shown by De Caen and Székely [DeSz92], who in fact show a stronger result. Let $f(n,m)$ be the maximum number of edges of a bipartite graph between $n$ and $m$ vertices which does not contain either a $C_4$ or $C_6$. A positive answer to this question would then imply $f(n,\lfloor n^{2/3}\rfloor)\ll n$. De Caen and Székely prove $n^{10/9}\gg f(n,\lfloor n^{2/3}\rfloor) \gg n^{58/57+o(1)}$ for $m\sim n^{2/3}$. They also prove more generally that, for $n^{1/2}\leq m\leq n$, $f(n,m) \ll (nm)^{2/3},$ which was also proved by Faudree and Simonovits. This was formalized in Lean by Alexeev using Aristotle. Topics: graph theory. Erdős prize: no. Statement is machine-verified in Lean (formal-conjectures). OEIS: possible.
source binding
source-boundcap_61973ee16b553d57 · vc_d3acac56ca207093
vs_65c0ec4034c749f3
review context
unverified1 events
1 reviewable changes and 0 evaluation records target this atom or its bound objects.
statement
{"artifact_id":"va_9bc926d75e4e3881","artifact_packet_id":"cap_61973ee16b553d57","candidate_claim_id":"vc_d3acac56ca207093"}
locator
span:0
extraction method
artifact_to_state_import
support relation
supports
condition refs
vcnd_1a469c6e98381340
caveats
No caveats recorded.
Review, event, and evaluation records
2events
vev_5dfd37ed307fd749finding.assertedCandidate claim vc_d3acac56ca207093 imported from artifact packet cap_61973ee16b553d57
reviewer:erdos-db-trust · 2026-05-30
reviewable changes
vpr_183bf46b361af53ffinding.addCandidate claim vc_d3acac56ca207093 imported from artifact packet cap_61973ee16b553d57
applied · agent:erdos-spine-ingest · 2026-05-30
evaluations
No evaluation rows are attached.