qedbot

Erdős·erdos:81

Erdős Problem 81

conjecture formal record: mixed source: open 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 an alignment table and written divergences.

graph theory·Source

AI activity

How grades work
Aristotle, GPT-5.5 Pro

19 Jun 2026·with Wouter van Doorn

Partial result (Lean)

partial A1 V2
Reasoning and sources

Autonomy

AI collaborating with humans

Claimed on erdosproblems.com

4

Proof claims posted on erdosproblems.com, which says that listing a claim “is no guarantee of proof correctness”. The register records who claims what, with which systems, and links to each claim there. Nobody has examined them, and none counts in the register's totals.

F2 declared. The correspondence is declared through an alignment table and written divergences.

declares divergences from its source reviewed by an agent

Checks

7
  • verified·Palomar

    Registered by Palomar at 39104cff: Comparator confirmed 21 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-11-03·commit 39104cffdbc2

    PALOMAR-2026-11-01-000021 — names this problem; not counted as a check of the claim

  • verified·Palomar

    Registered by Palomar at 0c2f7dff: Comparator confirmed 18 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-11-01·commit 0c2f7dff52e5

    PALOMAR-2026-11-01-000020 — names this problem; not counted as a check of the claim

  • verified·Palomar

    Registered by Palomar at 7961c3ab: Comparator confirmed 2 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-29·commit 7961c3aba606

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

  • verified·Palomar

    Registered by Palomar at f8690bcb: Comparator confirmed 7 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-29·commit f8690bcba57b

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

  • verified·Palomar

    Registered by Palomar at 719e39ba: Comparator confirmed 12 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-11-01·commit 719e39baf9d0

    PALOMAR-2026-11-01-000006 — names this problem; not counted as a check of the claim

  • verified·Palomar

    Registered by Palomar at 01be11e3: Comparator confirmed 7 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-11-01·commit 01be11e33fc4

    PALOMAR-2026-11-01-000022 — names this problem; not counted as a check of the claim

  • verified·Palomar

    Registered by Palomar at a98dfa41: Comparator confirmed 2 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-29·commit a98dfa413428

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

Declared by the projects

7

As each project's formalization.yaml states it.

Clique partitions of chordal graphs: quantitative stability and sharp eventual boundsjtraverso/erdos81-chordal-quantitative-stability · joined by names · Palomar

Read formalization.yaml

authors
Juan Pablo Traverso Gianini
method
agent — Aristotle (Harmonic), Certo, ChatGPT/Codex (OpenAI), Claude (Anthropic), Claude Opus 5.5, Jacobian
review
agent-reviewed (Claude Opus 5.5 (AI agent in Claude Code, acting for the author))
sorry
0 unproved goals declared
sources
Clique partitions with rooted simplicial defect: quantitative stability and sharp eventual bounds — formalizes, authors participated; Clique partitions and bounded simplicial defect — background, authors not-contacted; Clique partitions of chordal graphs with linear error — background, authors not-contacted; Clique partitions of chordal graphs — background, authors n/a
related
PALOMAR-2026-10-15-000011 v2 (jtraverso/asymptotic-triangle-packing @ 760e503) — builds-on; PALOMAR-2026-10-18-000006 (jtraverso/chordal-split-threshold-graphs @ ed65dcd) — builds-on; PALOMAR-2026-10-29-000004 (jtraverso/erdos81-complete-split-extremizers, Paper II) — other
divergences
Graphs are SimpleGraphs on Fin n. A clique partition is a finite family of cliques with at least two vertices, pairwise edge-disjoint and covering every edge; c₄ is expressed through partitions of order at most four (no minimum function is defined: the statements supply witnesses or quantify over all partitions), and cp(G) = t through CliqueCoverEq. Theorem B's maximum is stated as the existence, for each large n, of a chordal graph with an order-four partition of size M(n) that is optimal among all clique partitions, together with the upper bound. Theorem 6.1 uses the explicit constants of the formal companion (117/1825, 12687/20000, 16) and γ = 10⁻¹⁶/4. Rooted simplicial defect, the templates and Q_s(n) follow the paper's definitions as written in the Challenge; c₄ = Q_s(n) and cp = Q_s(n) are expressed by witnesses and lower bounds over all partitions; Theorem 6.5 is stated for sequences of graphs with Filter.atTop and little-o (Asymptotics). In Theorem 3.1 the gains are 2 for a triangle and 5 for a K₄, a fractional packing has load at most 1 on every edge of G, and a physical packing is a family of edge-disjoint triangles and K₄'s of G.
checked by
Palomar
Colorability and realizability defects in resource-dominated packing relaxationsjtraverso/erdos81-colorability-realizability-defects · joined by names · Palomar

Read formalization.yaml

authors
Juan Pablo Traverso Gianini
method
agent — Aristotle (Harmonic), ChatGPT/Codex (OpenAI), Claude Opus 5.5
review
agent-reviewed (Claude Opus 5.5 (AI agent in Claude Code, acting for the author))
sorry
0 unproved goals declared
sources
Colorability and Realizability Defects in Resource-Dominated Packing Relaxations — formalizes, authors participated; The list chromatic index of a bipartite multigraph — background, authors n/a; List edge and list total colourings of multigraphs — background, authors n/a
related
PALOMAR-2026-10-18-000029 v2 (jtraverso/galvin-dinitz @ 84dcda4) — builds-on; PALOMAR-2026-10-16-000003 v2 (jtraverso/brooks @ b99e6f5) — builds-on; PALOMAR-2026-10-15-000011 v2 (jtraverso/asymptotic-triangle-packing) — other; PALOMAR-2026-10-29-000006 (jtraverso/erdos81-split-clique-partitions, Paper III) — other
divergences
Multisets are multiplicity functions X : O → ℕ and the conflict graph lives on the copies Σ o, Fin (X o). Theorems 3.3 and 3.4 take the optimum as an explicit maximizing point of a resource-dominated relaxation (a structure recording the resources, the feasible region inside the resource-capacity polyhedron and the characterization of its 0/1 points; convexity is not used) and assume all its coordinates are at most one. Theorem 4.4 and Example 5.5 state the realizability defect for the admissibility classes of identity and host realizers. In Corollary 5.3 the host system restricted to B has the triangles (e, h) with e ∈ B as objects. Theorems 6.2 and 7.3 (integral) hold for arbitrary maximum (maximum-weight) packings P' of G_{v→u} and P'' of G_{u→v}, given as feasible sets of the conflict systems: the multiset is their image in G (mappedTri, mappedMixed), each member of P' and P'' counted at its image under the copy map. ν₃* is a supremum over fractional triangle packings (registered definition), proved equal to the library's linear-programming form.
checked by
Palomar
Complete-split extremizers for the fractional triangle-cover deficit on chordal graphsjtraverso/erdos81-complete-split-extremizers · joined by names · Palomar

Read formalization.yaml

authors
Juan Pablo Traverso Gianini
method
agent — Aristotle (Harmonic), Claude Opus 5.5
review
agent-reviewed (Claude Opus 5.5 (AI agent in Claude Code, acting for the author))
sorry
0 unproved goals declared
sources
Complete-Split Extremizers for a Fractional Triangle-Cover Functional on Chordal Graphs — formalizes, authors participated
related
PALOMAR-2026-10-18-000006 (jtraverso/chordal-split-threshold-graphs) — other; PALOMAR-2026-10-15-000011 (jtraverso/asymptotic-triangle-packing) — other
divergences
τ₃* is the real infimum of the total weight ∑ over all of Sym2 V of fractional triangle covers (weights off the edges only increase the total, so the infimum is the usual one); triangles are the 3-cliques of G. Chordality is the absence of chordless cycles of length at least four, phrased with Mathlib walks. The complete-split graph is built with SimpleGraph.fromRel on Fin p ⊕ Fin q.
checked by
Palomar
Affine profile reduction for fractional triangle packings in split graphsjtraverso/erdos81-fractional-split-profiles · joined by names · Palomar

Read formalization.yaml

authors
Juan Pablo Traverso Gianini
method
agent — Aristotle (Harmonic), Claude Opus 5.5
review
agent-reviewed (Claude Opus 5.5 (AI agent in Claude Code, acting for the author))
sorry
0 unproved goals declared
sources
Affine Profile Reduction for Fractional Triangle Packings in Split Graphs — formalizes, authors participated; Colorability and Realizability (Erdős #81 series, Paper V) — adapts, authors participated; Theorie der einfachen Ungleichungen — background, authors n/a
related
PALOMAR-2026-10-18-000006 (jtraverso/chordal-split-threshold-graphs) — other; PALOMAR-2026-10-15-000011 (jtraverso/asymptotic-triangle-packing) — other; PALOMAR-2026-10-17-000009 (jtraverso/erdos-girth-chromatic) — other
divergences
ν₃* is a real supremum over feasible packings; in the finite model triangles and edges are explicit subtypes of index triples and pairs, and in the SimpleGraph form triangles are the 3-cliques and weights live on vertex sets. The two forms are related by a proved bridge. The duality statements are written with explicit finite sums over finite index types; over ℚ the Farkas alternative is for systems M x ≤ b with free variables, and the packing LP has capacities 1 and requires every item to use some resource with coefficient at least 1.
checked by
Palomar
Optimal clique partitions under local perturbationsjtraverso/erdos81-optimal-clique-partitions · joined by names · Palomar

Read formalization.yaml

authors
Juan Pablo Traverso Gianini
method
agent — Aristotle (Harmonic), ChatGPT/Codex (OpenAI), Claude Opus 5.5
review
agent-reviewed (Claude Opus 5.5 (AI agent in Claude Code, acting for the author))
sorry
0 unproved goals declared
sources
Optimal Clique Partitions under Local Perturbations — formalizes, authors participated; Clique partitions and clique coverings — background, authors n/a
related
PALOMAR-2026-10-15-000004 v2 (jtraverso/vizing @ 33b2de8) — builds-on; PALOMAR-2026-10-15-000003 (jtraverso/haggkvist-janssen @ 807e08b) — builds-on; PALOMAR-2026-10-29-000006 (jtraverso/erdos81-split-clique-partitions, Paper III) — other; PALOMAR-2026-10-15-000011 v2 (jtraverso/asymptotic-triangle-packing) — other
divergences
The vertex set is a finite type and the core a Finset P; the exterior is its complement, of size q = n − p. The modification parameter is the maximum degree of the symmetric difference of G and the reference graph. C and A are integers. Clique partitions in the library have blocks of order at least two; the registered cp allows any cliques and is proved equal. Theorem A's partition is described by block types (core size, exterior size); Theorem C's by its exterior blocks and the counts of blocks of each order. In Theorem D the fractional optimum is over nonnegative weights on vertex sets, supported on cliques of order at least two, with total weight exactly one on every edge, and the triangle packing values are those of the registered definitions. N(G) counts Finsets of blocks (partitions as families of vertex sets).
checked by
Palomar
Two application notes of the Erdős #81 series: realizability transfer and exact chordal stabilityjtraverso/erdos81-series-notes · joined by names · Palomar

Read formalization.yaml

authors
Juan Pablo Traverso Gianini
method
autonomous — Aristotle (Harmonic), ChatGPT/Codex (OpenAI), Claude Opus 5.5
review
agent-reviewed (Claude Opus 5.5 (AI agent in Claude Code, acting for the author))
sorry
0 unproved goals declared
sources
From realizability certificates to the Erdős 81 bound — formalizes, authors participated; Exact stability for nearly extremal chordal clique partitions — formalizes, authors participated
related
Paper IV: jtraverso/erdos81-chordal-quantitative-stability @ 0e1cd91 (Palomar submission under review) — builds-on; Paper V: jtraverso/erdos81-colorability-realizability-defects (Palomar submission under review) — builds-on; Paper VI: jtraverso/erdos81-optimal-clique-partitions (Palomar, registration requested) — builds-on; PALOMAR-2026-10-29-000006 (jtraverso/erdos81-split-clique-partitions, Paper III) — other
divergences
Graphs are SimpleGraphs (on Fin n in the asymptotic statements). Note I: conflict systems, certificates and costs are Paper V's definitions; the physical system has as objects the copies of K₃ and K₄ in G; a clique partition has pieces of order at least two whose edge sets partition E(G); a certified fractional optimum is a pair of a feasible fractional packing and a feasible dual of the same rational value; the near branch states its hypothesis as the negation of the strict far inequality with η = 10⁻¹⁶. Note II: cp is the registered clique partition number (cliques covering every edge exactly once), cp_{≤4} uses blocks of order between two and four, B(n,p) = p(n − p) − C(p,2) and A, m are integers counted from the root, and the edit distance is the number of edges of G △ (K_P ∨ I_O); the natural subtraction M(n) − cp(G) in the hypothesis is justified by cp(G) ≤ M(n).
checked by
Palomar
Linear-error clique partitions of split graphsjtraverso/erdos81-split-clique-partitions · joined by names · Palomar

Read formalization.yaml

authors
Juan Pablo Traverso Gianini
method
agent — Aristotle (Harmonic), Claude Opus 5.5
review
agent-reviewed (Claude Opus 5.5 (AI agent in Claude Code, acting for the author))
sorry
0 unproved goals declared
sources
Linear-Error Clique Partitions of Split Graphs via Structured Triangle Packing — formalizes, authors participated
related
PALOMAR-2026-10-15-000011 (jtraverso/asymptotic-triangle-packing) — builds-on; PALOMAR-2026-10-21-000009 (jtraverso/nash-williams-lean) — builds-on; PALOMAR-2026-10-18-000006 (jtraverso/chordal-split-threshold-graphs) — other
divergences
Graphs are Mathlib simple graphs on finite vertex types in universe 0. A split graph is one with a SplitPartition (a clique part and an independent part covering the vertices, disjoint). The quantity |E(G)| − 2ν₃(G) is taken in ℝ. A clique partition is a finset of vertex sets, each a clique, such that every edge lies in exactly one of them; this allows one-vertex and empty cliques, which do not change the minimum. ν₃ and cp are defined as the natural-number supremum and infimum of the corresponding sizes.
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 · 1
Cited proofs · 0

No proof artifact cited by the formal record.

Recorded elsewhere

Compare the registries
  • palomar — Two application notes of the Erdős #81 series: realizability transfer and exact chordal stability

    checked·their labels: registered

  • palomar — Clique partitions of chordal graphs: quantitative stability and sharp eventual bounds

    checked·their labels: registered

  • palomar — Colorability and realizability defects in resource-dominated packing relaxations

    checked·their labels: registered

  • palomar — Optimal clique partitions under local perturbations

    checked·their labels: registered

  • palomar — Linear-error clique partitions of split graphs

    checked·their labels: registered

  • palomar — Complete-split extremizers for the fractional triangle-cover deficit on chordal graphs

    checked·their labels: registered

  • palomar — Affine profile reduction for fractional triangle packings in split graphs

    checked·their labels: registered

Also known as · 3
  • https://www.erdosproblems.com/81
  • https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/81.lean
  • FormalConjectures/ErdosProblems/81.lean

Cite this record

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

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