qedbot

Erdős·erdos:575

Erdős 575

problem formal record: unclassified source: disproved F2 declared

No independent check recorded yet. A formal artifact, declaration or published object is attached, but no rebuild of it is recorded here.

A Palomar registration names this problem. It is shown below but not counted as a check of the claim.

Fidelity F2: The correspondence is declared through a Comparator challenge, an alignment table and written divergences.

graph theory, turan number·Source

AI activity

How grades work
OpenAI internal model

1 Aug 2026

Disproved: a finite family of connected bipartite graphs, each containing a cycle, with ex(n; G) ≫ n^(4/3) for every member but ex(n; F) ≪ n^(4/3 − 1/48) for the family.

full A? V1 F0
Reasoning and sources

Autonomy

The page credits an internal model at OpenAI and does not say how it was directed.

Details

attribution: This was disproved by an internal model at OpenAI, which constructed a finite family $\mathcal{F}$ of connected bipartite graphs, every member of which contains a cycle, such that\[\mathrm{ex}(n;G)\gg n^{4/3}\]for all $G\in \mathcal{F}$ and\[\mathrm{ex}(n;\mathcal{F})\ll n^{4/3-c}\]where $c=1/48$.

GPT

14 Jan 2026·supporting task

Paper identifying a misstatement to the problem found

partial A1 V1 F0
Reasoning and sources

Autonomy

Secondary contribution: literature search

F2 declared. The correspondence is declared through a Comparator challenge, an alignment table and written divergences.

declares divergences from its source reviewed by an agent source authors not contacted

Checks

1
  • verified·Palomar

    Registered by Palomar at b135fd8f: Comparator confirmed 9 theorems prove the recorded statement within Palomar's axiom policy, replayed through Lean's kernel and the independent nanoda kernel. The project names this problem, which does not establish that it proves the result claimed here, so it is not counted as a check of it

    project registered at a pinned commit·2026-10-06·commit b135fd8f6e5e

    PALOMAR-2026-10-06-000004 — names this problem; not counted as a check of the claim

Declared by the projects

1

As each project's formalization.yaml states it.

Erdős 575: bipartite extremal-graph compactnesslinrock/math-proofs/erdos-575 · joined by names · Palomar

Read formalization.yaml

authors
Linmiao Xu
method
agent
review
agent-reviewed
axioms
Classical.choice, Quot.sound, propext
sorry
0 unproved goals declared
results
9 main results named, checked with Comparator, with an alignment table
sources
Ten advances in mathematics and theoretical computer science — formalizes, authors not-contacted; The Erdős–Simonovits Compactness Conjecture Needs More Assumptions — formalizes, authors not-contacted; Compactness results in extremal graph theory — background, authors not-contacted; Erdős Problem 575: bipartite extremal-graph compactness — background
divergences
None. Both the cycle-containing formulation (erdos_575 / CyclicBipartiteCompactnessStatement) and the literal unrestricted formulation (erdos_575_unrestricted / BipartiteCompactnessStatement) preserve the exact mixed-order finite-family quantifier, the ContainsBipartiteMember hypothesis, and the requirement that the controlling graph H in F be bipartite (IsBipartiteCompactFamily).
checked by
Palomar

Follow and discuss

All discussion

Discussion and bounties for this problem load here.

Something wrong or missing here? Request a correction or add a claim, with its sources.

Formal material

Formal statements · 0

No formal statement located.

Cited proofs · 0

No proof artifact cited by the formal record.

Recorded elsewhere

Compare the registries
  • palomar — Erdős 575: bipartite extremal-graph compactness

    checked·their labels: registered

Also known as · 1
  • https://www.erdosproblems.com/575

Cite this record

qed.bot, “Erdős 575”, https://qed.bot/s/erdos-575, as of 20 Nov 2026.

This record as plain text, with each claim, its grades and its sources.