Vela

Can every triangle-free graph on vertices be made bipartite by deleting at most edges?

Open problem — our best result is machine-sealed: extends prior work, reproduced by an independent verifier. The conjecture itself is unsettled.

graph theory · open · formalized (Lean) · 1 attempt

machinery: graph-coloring,extremal-set-system,flag-algebra,max-cut-edge-deletion,triangle-free-bipartite,stability-method,C5-blowup-extremal

use this record

vela registry pull vfr_37aec80d874a0239
vela reproduce examples/erdos-problems

evidence

extends prior work

needs verification

FULL ERDOS AUDIT (workflow wf_de3c1580): of 430 ingested problems, the 72 shape-promising ones deeply audited (live status+comments, anti-confab) -> 91 assessed, ALL disqualified except #23. Corpus essentially EXHAUSTED for Vela-solvable targets. The lone fresh target is #23's finite Lean test-sorries (n=1 case on 5-vertex graphs + C5 tightness witness + blowupC5_tight counting lemma).

erdos-full-audit workflow (9 batch agents + skeptical rank, 47 agents, 1.5M tokens). Of the shape-filtered top-72 (from 430 ingested, 79 already-worked, ~289 keyword-walls): 91 assessed, breakdown ~43 analytic-wall, ~18 famous-hard, ~30 already-solved-or-mapped. KEY DISQUALIFICATIONS verified by the agents: #350 (distinct-subset-sums sum 1/n<2) ALREADY PROVED + Lean-formalized (Ryavec/BeEr74, sharper 2-2^{1-|A|}); #92 DISPROVED (via #90 unit-distance disproof); #39 famous $500 infinite-Sidon (Ruzsa record, analytic); #1097 Kakeya-equivalent (AlphaEvolve already on the construction lane); #835 over-determined (impossibility not witness); #617 Ramsey non-enumerable. ONLY PURSUE = #23 (Erdos: triangle-free graph made bipartite by deleting few edges): variants.n1/n1_tight are TEST-category finite Lean sorries over SimpleGraph (Fin 5) -- 'every triangle-free G on 5 vertices is made bipartite by deleting <=1 edge' + C5 tightness; blowupC5_tight = elementary parametric n^2-lower-bound counting lemma. Kernel-certain, modest (#409/Lean-fragment vein). CONCLUSION: campaign base rate confirmed -- real wins are #488 (|A|<=4) + OEIS bounds; the ingested Erdos corpus is mapped and exhausted of Vela-solvable targets beyond #23 + the earlier 358684/#36 Lean fragments. STOP hunting new Erdos targets.

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

What you are asking is the special case (N=5n) of a long–standing conjecture of Erdős (often called the **Erdős bipartification / max‑cut conjecture for triangle‑free graphs**):

candidate solution ↗

llm-hunter · gpt 5.2, gpt pro 5.2 · unverified

5 LLM attack(s) recorded (gpt 5.2, gpt pro 5.2); unverified.

candidate solution ↗

formal

AMS 5 · test (literature)

theorem erdos_23.variants.n1 :
    ∀ (G : SimpleGraph (Fin 5)), G.CliqueFree 3 → ∃ (H : SimpleGraph (Fin 5)),
        H ≤ G ∧ H.IsBipartite ∧ (G.edgeFinset \ H.edgeFinset).card ≤ 1
formal-conjectures/23.lean ↗

oeis

status

open

notary

vela reproduce examples/erdos-problems
  • packet.json · sha256 a8c5db39a4d3c86a83a383c0353ae146c5571903f14f68a55af4905f42e826dc

finding.noted · reviewer:will-blair · 1 day

renders the record as of vev_d199cb2e · 1,338 events · hub

Search Vela

Jump to a section, signal, campaign, document, primitive, work path, frontier, record index, atlas, constellation, agent, capability, or full-state search.