The clique density theorem
By Christian Reiher. 2012
110 citations recorded by the source corpus.
Tur an’s theorem is a cornerstone of extremal graph theory. It asserts that for any integer r > 2, every graph on n vertices with more than r 2 2(r 1) n 2 edges contains a clique of sizer, i.e.,r mutually adjacent vertices. The corresponding extremal graphs are balanced (r 1)-partite graphs. The question as to how many suchr-cliques appear at least in anyn-vertex graph with n 2 edges has been intensively studied in the literature. In particular, Lov asz and Simonovits conjectured in the 1970’s that asymptotically the best possible lower bound is given by the complete multipartite graph with n 2 edges in which all but one vertex class is of the same size while the remaining one may be smaller. Their conjecture was recently resolved for r = 3 by Razborov and for r = 4 by Nikiforov. In this article, we prove the conjecture for all values ofr.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/2b21235f31b04876e517fc59939dc8c23dda98c2
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
- 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.”