proposed
reason
Candidate claim vc_d3acac56ca207093 imported from artifact packet cap_61973ee16b553d57
finding type
open_question
proposed confidence
0.99
confidence basis
agent-imported candidate claim; reviewer acceptance required
frontiers / 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
Reviewable change
back to reviewadd a finding
acceptedErdő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.
- id
- vpr_183bf46b361af53f
- frontier
- Erdős problems frontier
- kind
- finding.add
- created
- 2026-05-30
- findings
- +1
- state
- null → ba12a796
accept gate
1 of 4 on record- —
- signature
- reviewer:erdos-db-trust · no key registered on this bundle
- ✓
- chain
- null → ba12a796
- —
- witness
- no verifier attachment on record for this target
- —
- grade
- in state · unreviewed
timeline
- 2026-05-30proposeproposed · finding.addagent:erdos-spine-ingest
vpr_183bf46b361af53fCandidate claim vc_d3acac56ca207093 imported from artifact packet cap_61973ee16b553d57 - 2026-05-30acceptfinding.assertedreviewer:erdos-db-trust
null→ba12a796vev_5dfd37ed307fd749Candidate claim vc_d3acac56ca207093 imported from artifact packet cap_61973ee16b553d57
provenance
proposed by
agent:erdos-spine-ingest
actor type
agent
created at
2026-05-30
target type
finding
affected
inspect finding →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.
vf_b9e7b2d1475382f3Diff
Read-only frontier; diff not recomputed.
Review chain
- 01requestopen review →
Change request
Erdős problems frontier receives a reviewable source, finding, caveat, replication, evaluation, or proof-affecting edit.
- 02packetopen the campaign →
Diff packet
The packet names affected record objects, evidence, rationale, reviewer-facing fields, and expected proof impact.
- 03checksinspect checks →
Check output
Schema, provenance, benchmark, contradiction, and proof checks decide whether the request is ready to read.
- 04reviewread queue →
Reviewer decision
A steward accepts, rejects, caveats, revises, or retracts the request under an inspectable identity.
- 05acceptedinspect events →
Accepted event
Only the accepted event mutates frontier state. Atlases, constellations, and search update from that record state.