Any results concerning the numbers of vertices and edges to form fixed number of cliques in $K_n$?

Question

Given a complete graph $K_n$, and if we know there are $t$ $K_s$ ($s\ge 2$) in it, what can we say about the possible number $a$ of vertices and the number $b$ edges to form these $t$ cliques? We can assume $n\gg 1$ and $t(n)\gg 1$. So any asymptotical bounds would be helpful.

(There was a typo, $k(n)$ should be $t(n)$.)

For example, if all these $t$ cliques are vertex-disjoint, then $a=st$ and $b=\binom{s}{2}t$. If all of these $t$ cliques come from a larger clique, then $t\approx\binom{a}{s}$ and $b=\binom{a}{2}$. But what can we say about other cases? Do we have some relations between $a$, $b$, and $t$?

Answer 1

It might be clearer to say that you have a set of points and $t$ blocks each of size $s$ (I suppose no two totally identical).

What can be said about the range of possible quadruples $(s,t,a,b)$ where $a$ is the size of the union of the blocks and $b$ is the number of point pairs which are in at least one block? Specifically, fix one or more and ask what the range is for the other(s).

I didn’t name the number of points since you don’t use it. I’m not sure what you mean by $k(n).$

I’ll look at this question since you mention it : Certainly $b \leq \binom{a}2.$

Q: What is the range on $t$ be given that $b = \binom{a}2?$

It turns out that the answer is

$$\frac{a(a-1)}{s(s-1)} \leq t \leq \binom{a}{s}=\frac{a}{s}\frac{a-1}{s-1}\frac{a-2}{s-2}\cdots\frac{a-s+1}{1}$$

The lower bound occurs in the event that every pair is in exactly one block (which of course requires $\frac{a(a-1)}{s(s-1)}$ to be an integer.) One also sees that the number of blocks containing a given point is $$\frac{a-1}{s-1}$$ which must also be an integer.

Then we have what is called a Balanced Incomplete Block Design BIBD with parameters $(v,k,\lambda)=(a,s,1)$ Also called a $2-(a,s)$ Steiner System. It turns out that, for fixed $s,$ this is possible provided $a$ is large enough and the two integrality conditions are met.

A BIBD$-(a,3,1)$ is called a Steiner Triple System and exists for $a \equiv 1,3 \bmod 6.$

Projective planes are BIBD$-(q^2+q+1,q+1,1)$ and Affine planes are $BIBD-(q^2,q,1)$

So this was a matter of fixing $a$ and $s$, letting $b=\binom{a}{2}$ and looking at the possible sizes of $t.$

---

A question which might be easy, but isn't obvious to me is:

Given $s,t$, how small can $a$ and/or $b$ be?

It might , in fact be tricky, I didn't think about it too much.

If $t=2$ then we can have $a=s+1$ in which case $b=\binom{s}2+s-1=\frac{(s+2)(s-1)}2$ which are both minimums.

For $3 \le t \le s+1$ we can have $a=s+1$ and $b=\binom{s+1}2.$

The minimum $a$ is $a=s+c$ with $c$ minimal subject to $\binom{s+c}s \ge t$ and then one has $\binom{s+c-1}2 \lt b \le \binom{s+c}2.$