Skip to main content
3 of 5
deleted 7 characters in body

Graphs with prescribed numbers of k-cliques

Let $(a_0,a_1,\dots, a_n)$ be a sequence of non-negative integers.

Q. When does there exists a graph $G$ such that its number of $k$-cliques is $a_k$ (that is $G$ has $a_0$ vertices, $a_1$ edges, $a_2$ trinagles, etc)?

Probably, it is hopeless to get a complete description of such sequences, so I am interested in any necessary or sufficient conditions on $\{a_i\}$.

Upd. As Steve Huntsman mentions in the comments there are trivial necessary conditions: $a_k\le \binom{a_0}{k+1}$. There are also more complicated inequalities like $$ \binom{a_0}{3}-a_2\le \bigl(\binom{a_0}{2}-a_1\bigr)(a_0-2). $$