Clique counting from iterated shadows

ID: clique-counting-from-iterated-shadows

For the uniform set family of vertex sets of -cliques, its -fold lower shadow consists of graph edges. Repeated use of the Kruskal-Katona theorem bounds clique count from edge count. Sixteen four-cliques have at least twenty-three triples in their shadow and at least eighteen edges in their second shadow, by the expansions and . Hence a graph with fifteen edges has at most fifteen four-cliques, attained by the complete graph on six vertices.

New to topics? Read the docs here!