Clique partitions above the Turán threshold

A clique is a set of mutually adjacent vertices in a graph. A clique partition divides all edges into cliques without overlap. Among graphs with n vertices and k edges, how large can the smallest such partition be?

Why it matters and what counts as progress

Why it matters: Erdős, Goodman and Pósa proved that at most floor(n2/4n^{2}/4) cliques always suffice. Erdős asked how this bound improves when a graph has more than n2/4n^{2}/4 edges.

What counts as progress: Determine the worst-case partition size as a function of both n and k. An asymptotic formula should state its error and whether it holds uniformly as the edge density varies.

How the problem developed

  1. 1966 · Universal clique-partition bound [3][1]

    Paul Erdős, A. W. Goodman and Lajos Pósa Proved that every n-vertex graph admits a partition into at most floor(n2/4n^{2}/4) cliques.

  2. 1971 · Dense-graph question [3][1]

    Paul Erdős Asked for a sharper estimate when the number of edges exceeds n2/4n^{2}/4.

  3. 11 Nov 2026 · Uniform asymptotic formula [1][2]

    Plasma AI Registered a Lean-checked formula for the worst-case partition size at every edge density.

AI contribution

An asymptotic formula for clique partitions above the Turán threshold

Plasma AI

Let f(n,k)f(n,k) be the largest minimum clique-partition size among simple graphs with n vertices and k edges. Plasma AI reports f(n,k)=n2B(k/n2)+o(n2)f(n,k) = n^{2}B(k/n^{2}) + o(n^{2}), uniformly for 0≤k≤n(n−1)/20 \le k \le n(n-1)/2, with an explicit continuous piecewise algebraic function B.

AI involvementAI-led
ImportanceNotable
Technical verificationFormal (Lean 4)
Human understandingFew
Reported

Sources

  1. Plasma AI, An asymptotic formula for clique partitions above the Turán threshold
  2. Theorem scope, AI provenance and kernel checks
  3. Erdős Problem 1017
Publication history