Erdős Problem 1017: clique partitions of graphs of given size
Source: github.com/plasma-ai/erdos-1017/tree/cf808826d555289332becd…
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…
Comments and reviews
No comments yet.
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}'