Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am try to find a rigorous way to prove that given a graph that has exactly 10 3 cliques(triangles), the maximum number of 4 cliques that can be formed is 3. Or more generally if there is connection with the number of (k-1) cliques and the maximum number of k cliques.

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

I don't think the question is correct. Consider $K_5$ (complete graph on $5$ vertices). It has $\binom{5}{3} = 10$ $3$-cliques and $\binom{5}{4}=5$ $4$-cliques.

A crude bound for general case can be obtained as shown below. But I don't think is a good bound, i.e., the bounds might not be tight for any graph.

Each $k$ clique contains $k$ number of $k-1$ cliques in it. And any two $k$ cliques can have at most one $k-1$ clique common. Using these two observations we can get some crude bound.

Suppose the number of $k$ cliques is $r$. Then the first $k$ clique has $k$ number of $k-1$ cliques in it. The next $k$ clique again has $k$ number of $k-1$ cliques, but at most one of them is common with the first $k$ clique. So it has at least $k-1$ new $k-1$ cliques. Similarly the third one will have at least $k-2$ new $k-1$ cliques and so on.

Now, we get a lower bound for number of $k-1$ cliques (say $R$) in terms of $r$ as,

if $r \geq k$,

$$ R \geq k(k-1)/2 $$

if $r < k$

$$ R \geq k+(k-1)+ \ldots +(k-r+1) = rk - r(r-1)/2 $$

share|improve this answer
    
Good answer. In my question I was thinking the clique number of graph to be 4, so I said 3 4 cliques is the max. But I don't really need this restriction. –  epinephelus Mar 6 '13 at 14:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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