0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I don't understand. You just said they do come from a larger clique, namely $K_n$. $\endgroup$ Apr 18, 2019 at 22:28
  • $\begingroup$ @RobertIsrael I mean they come from an $a$-vertex clique which satisfies $t$ is around $\binom{a}{s}$, so they “intersect” a lot. $\endgroup$
    – Connor
    Apr 18, 2019 at 22:31
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 19, 2019 at 4:32

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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$? $\endgroup$
    – Connor
    Apr 19, 2019 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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