A Higher-Order Clique Density Theorem

Abstract

Reiher's clique density theorem determines the sharp lower envelope for the density of $K_r$ at fixed edge density. We prove a higher-order version in which the prescribed quantity is itself a clique density. For every $3\le s<r$, we determine the minimum possible $K_r$-density among graphons with prescribed $K_s$-density. For $s\ge3$ the constraint is genuinely nonlinear and leaves the edge density undetermined; nevertheless, on the positive range the sharp lower boundary is the classical multipartite edge-to-clique profile, reparametrised by $K_s$-density. We also prove stability on the positive branches of this profile: at every interior point, near extremality forces cut-distance closeness to the corresponding extremal family at the induced edge density.

Disclosure

“oped by the authors, inspired by the variational-and-link philosophy of Kim, Liu, Pikhurko and Sharifzadeh [9]. The authors used generative AI tools to help check and simplify routine technical computations in several auxiliary lemmas. All AI-assisted suggestions and computations were independently checked and verified by the authors. References [1] G. Blekherman and A. Raymond. Ubiquity of power sums in graph profiles. Electron. J. Combin., 33(1):Paper No. 1.24, 14, 2026. [2]”

PDF page 14

Classification

Computational experiments or data processing

Multiplier

3

Verified

2026-08-24T00:34:12.480Z

Structural counts