Return to Question

Let $(a_1,a_2,\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_1$ vertices, $a_2$ edges, $a_3$ 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}$. There are also more complicated inequalities like $$ \binom{a_1}{3}-a_3\le \bigl(\binom{a_1}{2}-a_2\bigr)(a_1-2). $$

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

Q. When does there exists a simple graph $G$ such that its number of $k$-cliques is $a_k$ (that is $G$ has $a_1$ vertices, $a_2$ edges, $a_3$ 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}$. There are also more complicated inequalities like $$ \binom{a_1}{3}-a_3\le \bigl(\binom{a_1}{2}-a_2\bigr)(a_1-2). $$

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). $$

Let $(a_1,a_2,\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_1$ vertices, $a_2$ edges, $a_3$ 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}$. There are also more complicated inequalities like $$ \binom{a_1}{3}-a_3\le \bigl(\binom{a_1}{2}-a_2\bigr)(a_1-2). $$

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\}$.

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). $$