Erdős·erdos:81
Erdős Problem 81
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 workPartial result (Lean)
Reasoning and sources
Autonomy
AI collaborating with humans
Sources
Claimed on erdosproblems.com
4Proof 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.
Fidelity
How fidelity is gradedF2 declared. The correspondence is declared through an alignment table and written divergences.
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
-
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
-
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
-
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
-
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
-
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
-
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
Declared by the projects
7As each project's formalization.yaml states it.
Clique partitions of chordal graphs: quantitative stability and sharp eventual bounds
- 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 relaxations
- 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 graphs
- 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 graphs
- 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 perturbations
- 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 stability
- 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 graphs
- 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 discussionFollow this problem
An email when it has a new claim, check, bounty or discussion. You confirm once and can stop with one click.
Discussion and bounties for this problem load here.
Seen recently
What the monitors picked up in the last thirty days, not yet graded.
Something wrong or missing here? Request a correction or add a claim, with its sources.
Claims and corrections from readers
All of themFormal 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
- palomar — Clique partitions of chordal graphs: quantitative stability and sharp eventual bounds
- palomar — Colorability and realizability defects in resource-dominated packing relaxations
- palomar — Optimal clique partitions under local perturbations
- palomar — Linear-error clique partitions of split graphs
- palomar — Complete-split extremizers for the fractional triangle-cover deficit on chordal graphs
- palomar — Affine profile reduction for fractional triangle packings in split graphs
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.