I've found and read a considerable amount about the density of cliques on non-random graphs, notably the paper "The Clique Density Theorem" by Reiher. I was wondering if there was any analogous work on the density of cliques on random graphs? I would love to learn about any results out there.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If by "density" you do not strictly restrict your question to quantitative results (in the sense of results about the numerical value of the clique density), but rather also more qualitative/structural/topological results, then the work of Matthew Kahle is very relevant to your question.
In particular, Kahle investigated the clique complex of $G(n,p)$. (Synonyms: flag complex, Vietoris--Rips complex). This is the abstract finite simplicial complex whose $d$-dimensional independent sets are precisely the $(d+1)$-cliques in the graph.
However, if you really mean "analogous work", in particular, analogous to theorems of Reiher, and of Razborov, in particular "work discovering a globally-convex-yet-piecewise-concave-dependency between $K^2$-density and $K^r$-density", then I think there simply does not exist anything analogous seen through the lens of (the measure of) $G(n,p)$. The dependency between $p$ and $K^r$-density appears convex.
answered Jul 21, 2017 at 18:07
$\begingroup$
$\endgroup$
A good start is Bollobos and Erdös (2008), which discusses a lower bound on the minimum number of cliques given statistics of the number of vertexes and edges.
answered Jul 21, 2017 at 16:24