Skip to main content
Clarified and discussion in comments
Source Link
John Machacek
  • 7.9k
  • 1
  • 23
  • 40

What you are asking for is possible $f$-vectors of Clique Complexes. The Kruskal-Katona Theorem characterizes $f$-vectors of simplicial complexes; so, it applies here but is no longer a complete characterization. Your problem is open according to this paper. The linked paper and references there in contain partial results.

Edit: This answer assumes the number of $k$-cliques of $G$ is $a_k$ for $1 \leq k \leq n$ and $0$ for $k > n$. Another interpretation of the question would be that the number of $k$-cliques of $G$ is $a_k$ for $1 \leq k \leq n$ and there is no restriction on the number of $k$-cliques for $k > n$. The OP has expressed interest in both variations in the comments.

What you are asking for is possible $f$-vectors of Clique Complexes. The Kruskal-Katona Theorem characterizes $f$-vectors of simplicial complexes; so, it applies here but is no longer a complete characterization. Your problem is open according to this paper. The linked paper and references there in contain partial results.

What you are asking for is possible $f$-vectors of Clique Complexes. The Kruskal-Katona Theorem characterizes $f$-vectors of simplicial complexes; so, it applies here but is no longer a complete characterization. Your problem is open according to this paper. The linked paper and references there in contain partial results.

Edit: This answer assumes the number of $k$-cliques of $G$ is $a_k$ for $1 \leq k \leq n$ and $0$ for $k > n$. Another interpretation of the question would be that the number of $k$-cliques of $G$ is $a_k$ for $1 \leq k \leq n$ and there is no restriction on the number of $k$-cliques for $k > n$. The OP has expressed interest in both variations in the comments.

Source Link
John Machacek
  • 7.9k
  • 1
  • 23
  • 40

What you are asking for is possible $f$-vectors of Clique Complexes. The Kruskal-Katona Theorem characterizes $f$-vectors of simplicial complexes; so, it applies here but is no longer a complete characterization. Your problem is open according to this paper. The linked paper and references there in contain partial results.