The number of cliques in graphs of given order and size

By Vladimir Nikiforov. 2007

118 citations recorded by the source corpus.

Let kr (n, m) denote the minimum number of r-cliques in graphs with n vertices and m edges. We give a lower bound on kr (n, m) that approximates kr (n, m) with an error smaller than n r / n 2 − 2m � . This essentially solves a sixty year old problem. The solution is based on a constraint minimization of certain multilinear forms. In our proof, a combinatorial strategy is coupled with extensive analytical arguments.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/ba531ecf49a49c9bb32740a4ac008023551b336e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Two Approaches to Sidorenko's Conjecture (2013, background): “Razborov [16] proved the conjecture for r = 3 in 2008, and Nikiforov [14] proved it for r = 4 in 2011.”
Sidorenko's conjecture for blow-ups (2018, methodology): “His result was then extended to K4 by Nikiforov [11] and to all Kr by Reiher [14] using further ideas.”
The clique density theorem (2012, methodology): “The next important step is due to Nikiforov [9], who found an independent proof for the case r = 3 and settled the case r = 4 as well.”
On the KŁR conjecture in random graphs (2013, background): “Finally, Reiher [70] recently resolved the general case.”
Large Networks and Graph Limits (2012, methodology): “With a convenient parametrization suggested by Nikiforov [2011], they can be written as (1 + u)/k, .”