8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There are trivial necessary conditions $a_k \le \binom{a_0}{k+1}$ $\endgroup$ – Steve Huntsman May 31 '16 at 20:08
  • 1
    $\begingroup$ @SteveHuntsman Yes, sure. There are also not that trivial, e.g., $\binom{a_0}{3}-a_2\le (\binom{a_0}{2}-a_1)(a_0-2)$ (the number of non-triangles is less or equal the number of non-edges times $a_0-2$) $\endgroup$ – Yury Ustinovskiy May 31 '16 at 20:13
  • $\begingroup$ Nice question. A $k$-clique is normally defined as a clique with $k$ vertices, so you should probably adjust your indexing. $\endgroup$ – Tony Huynh May 31 '16 at 21:15
  • $\begingroup$ @Tony Thanks! Yes, my bad. I updated the notation. $\endgroup$ – Yury Ustinovskiy May 31 '16 at 21:21
  • 1
    $\begingroup$ @DanielSoltész Yes, thank you for the comment. $\endgroup$ – Yury Ustinovskiy May 31 '16 at 22:31
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the linked paper. I have looked at the references in it and they mostly answer my questions. $\endgroup$ – Yury Ustinovskiy Jun 1 '16 at 18:59
2
$\begingroup$

The case $n=3$ was addressed in Razborov's On the Minimal Density of Triangles in Graphs, where he used his Flag Algebra technique to provide an asymptotically tight lower bound on the number of triangles contained in a graph with a given number of vertices and edges.

Let $\rho=\frac{a_2}{\binom{a_1}{2}}$ be the density of edges in the graph. If $\rho=1-\frac{1}{t}$ for some integer $t$, then the minimum number of triangles comes from a balanced, complete $t$-partite graph. If $\rho \in (1-\frac{1}{t}, 1-\frac{1}{t+1})$, then the optimal graph ends up being a complete $(t+1)$-partite graph, with $t$ equal sized parts, and one part smaller than the rest. Optimizing over the size of the parts gives the (complicated) bound in Razborov's paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.