Given a graph G, a clique is a complete subgraph of G and an "anticlique" is a complete subgraph of the complement of G. When looking for Ramsey critical graphs related to R(k,k) a common objective function used in the search algorithm is the total number of cliques and anticliques of size k. In order to improve the search space of this type of search, I have been examining how various graph invariants are related to clique count and noticed that the degree variance of a random graph is correlated with the total number of cliques and anticliques in the graph.
Why is this? I know that circulant graphs (which I believe always have a degree variance of zero?) are useful for Ramsey critical graph constructions, but why? And in general, I have no intuition about why graphs with low degree variance should have less cliques and anticliques. Can anyone explain why this seems to be the case?
Best Answer
There are certainly plenty of graphs with low degree variance and many cliques and anticliques. The complete graph $K_n$ is one. Only the reverse is true: to have few cliques and anticliques, the degree variance ought to be low.
One factor is that the number of $3$-cliques and $3$-anticliques can be found directly from the degree sequence, and there you want the degrees to all be close to $\frac{n-1}{2}$. In a graph with degree sequence $d_1, \dots, d_n$, you have $$ S:=\sum_{i=1}^n \left(\binom{d_i}{2} + \binom{n-1-d_i}{2}\right). $$ pairs of edges that share a vertex plus pairs of non-edge that share a vertex. Every set of $3$ vertices spans at least one such pair, but $3$-cliques and $3$-anticliques span $3$ such pairs; therefore the number of $3$-cliques and $3$-anticliques is $$\frac12\left(S - \binom n3\right).$$ Each term of $S$ is minimized when $d_i = \frac{n-1}{2}$. The more degrees are far away from this, the worse. And in particular, if all degrees are close to $\frac{n-1}{2}$, then the degree variance is low.
(There's no similarly direct relationship to larger cliques and anticliques, but there should be a partial relationship, because if there are many $k$-cliques and $k$-anticliques, then there are many triangles and antitriangles as well.)
More vaguely, Ramsey-critical and Ramsey-good graphs tend to have various pseudorandom properties, and this leads to lower degree variance. Maybe this extends to a low count of $k$-cliques and $k$-anticliques, as well.