Given a graph with $n$ vertices and $m$ edges, and fix positive integers $a+b\leq n$. What are some upper bounds on the number of (ordered) pairs of subsets of vertices $(A,B)$ such that $|A|=a,|B|=b$, and any vertex in $A$ has an edge to any vertex in $B$?

If we only use the variables $n,a,b$, then it is possible that the whole graph is complete, and so the number of such pairs is $\binom{n}{a}\cdot\binom{n-a}{b}=\frac{n!}{a!b!(n-a-b)!}$. But can we have a bound that takes into account the number of edges $m$?


All right, you already have some finite upper bound :-) I'll give exact bounds for some special cases. Let $k = k(n, m, a, b)$ be maximum number of desired pairs of subsets.

If $m = \binom{n}{2}$ then as far as you know $k = \frac{n!}{a!b!(n - a - b)!}$. If $m < ab$, then $k = 0$. If $m = ab$, then $k = 1 + [a = b]$. If $a = b = 1$, then $k = 2m$.

If $a = 1$ and $b > 1$, then each vertex of degree $d$ gives $\binom{d}{b}$ subgraphs. It is easy to see that universal vertex is the best choice in sense of relation between edges used and subgraphs gain. Graph can have $\ell$ universal vertices if $\binom{\ell}{2} + \ell (n - \ell) \le m$, i. e., if $\ell \le n - \frac12 - \sqrt{n^2 - n + \frac14 - 2m}$ for $m < \binom{n}{2}$. After getting maximum number of universal vertices it is better to give all remaining $r = m - \binom{\ell}{2} - \ell (n - \ell)$ edges to one of remaining vertices. Then $k = \ell\binom{n}{b} + \binom{\ell + r}{b} + (n - 1 - \ell)\binom{\ell}{b}$ for $\ell = \left\lfloor n - \frac12 - \sqrt{n^2 - n + \frac14 - 2m}\right\rfloor$ and $r = m - \binom{\ell}{2} - \ell (n - \ell)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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