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

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$$?

## bumped to the homepage by Community♦yesterday

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

• I don't understand. You just said they do come from a larger clique, namely $K_n$. – Robert Israel Apr 18 at 22:28
• @RobertIsrael I mean they come from an $a$-vertex clique which satisfies $t$ is around $\binom{a}{s}$, so they “intersect” a lot. – Connor Apr 18 at 22:31
• See below. What you can say when $b=\binom{a}{2}$ is that $\frac{a(a-1)}{s(s-1)} \leq t \leq \binom{a}{s}.$ Both extremes are possible. – Aaron Meyerowitz Apr 19 at 4:32

## 1 Answer

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

• Sorry, there was a typo. It should be $t(n)$, not $k(n)$. So the problem is given $s\ge 2$ (a fixed constant) and $t$ (which can be a function depending on $n$ and we can assume $t(n)\gg 1$), what can we say about $a$ and $b$? – Connor Apr 19 at 17:26