Delphi.science

Erdős Problem 1017: clique partitions of graphs of given size

Source: github.com/plasma-ai/erdos-1017/tree/cf808826d555289332becd…

Ryan Pettry

Palomar Registrypalomar/PALOMAR-2026-11-11-000003Nov 11, 2026math.COscore 0

A Lean proof that f(n, k), the least number such that the edges of every graph with n vertices and k edges can be partitioned into at most f(n, k) cliques, satisfies f(n, k) = n² B(k/n²) + o(n²) uniformly in 0 ≤ k ≤ n(n − 1)/2, for an explicit continuous piecewise-algebraic function B on [0, 1/2]. B(d) = d for d ≤ 1/4; above 1/4 it is the larger of two curves built from explicit dual certificates on split, mixed and two-head graphs. This provides an asymptotic resolution of Erdős Problem 1017, as posed by Erdős and as stated by Bloom, who asks for an estimate of f(n, k) for k > n²/4. The…

RepositoryJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-11-11-000003
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-11-000003/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-11-000003/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'