{"id":"palomar/PALOMAR-2026-11-11-000003","url":"https://github.com/plasma-ai/erdos-1017/tree/cf808826d555289332becdf4fd86de962ca00dfa","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-11-000003-v1.json","repo":"https://github.com/plasma-ai/erdos-1017","tags":["math.CO","msc:05C35","msc:05C70"],"score":0,"title":"Erdős Problem 1017: clique partitions of graphs of given size","trust":"high","domain":"math.CO","source":"palomar","authors":["Ryan Pettry"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-11","reactions":{},"formalized":true}