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

Improve this question
$\endgroup$
7
  • $\begingroup$ There are trivial necessary conditions $a_k \le \binom{a_0}{k+1}$ $\endgroup$
    – Steve Huntsman
    Commented May 31, 2016 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
    Commented May 31, 2016 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
    Commented May 31, 2016 at 21:15
  • $\begingroup$ @Tony Thanks! Yes, my bad. I updated the notation. $\endgroup$
    – Yury Ustinovskiy
    Commented May 31, 2016 at 21:21
  • 1
    $\begingroup$ @DanielSoltész Yes, thank you for the comment. $\endgroup$
    – Yury Ustinovskiy
    Commented May 31, 2016 at 22:31

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the linked paper. I have looked at the references in it and they mostly answer my questions. $\endgroup$
    – Yury Ustinovskiy
    Commented Jun 1, 2016 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .