# Given an $n$-element family $\mathcal{S}$ of average size $r$, is $\sum |S_i \cap S_j|\geq n\binom{r}{2}$?

Consider a set $$X$$ of size $$n$$, and a size-$$n$$ family of sets $$\mathcal{S}$$. The sets in $$\mathcal{S}$$ have average size $$r$$, and their intersections are of size at most $$k$$. I'm trying to show that the intersection graph of $$\mathcal{S}$$ satisfies the inequality $$|E|≥\frac{n}{k}\binom{r}{2}.$$

The intersection graph is a graph on $$n$$ vertices which has $$(i,j)$$ as an edge iff $$|S_i\cap S_j|$$ is nonzero.

I'm considering the sum $$\sum |S_i \cap S_j|$$. It's clear that $$|E|k\geq\sum |S_i \cap S_j|$$ so to complete the problem, it would be enough to show the assertion in the question. Unfortunately, I'm not sure how to proceed -- $$r$$ is only the average size, and I can't use any usual average-size-of-set-intersection lemmas since they're all lower bounds on the size of some set intersection, not upper bounds.

Any hints on how to proceed? I feel like I'm missing something obvious, so I'd prefer a hint instead of a solution.

After some consideration, it seems that the inclusion-exclusion principle gives a bit of leeway:

$$$$|S_1\cup\dots\cup S_n| \geq \sum|S_i| - \sum|S_i\cap S_j|\\ n \geq nr -\sum|S_i\cap S_j|\\ \sum|S_i\cap S_j|\geq n(r-1).$$$$

Still a missing $$r/2$$, however.

Your intuition is correct. You only need to prove $$\sum |S_i \cap S_j| \geq {r \choose 2}$$. I'll give you a hint as you requested.

First of all, the correct summation you want is $$\sum_{i to ensure no double counting of the edges in the intersection graph.

For any element $$x \in X$$, define $$d(x)$$ as the degree of $$x$$, or the number of sets of $$\mathcal{S}$$ that it is contained in. First observe that $$\sum_{x\in X}d(x) = \sum_i |S_i| = rn$$

Now notice that

$$\sum_{i

But note that $$\sum_{i,j} |S_i\cap S_j|$$ counts each element in $$X$$ a total of $$d(x)^2$$ times. Indeed, for fixed $$i$$, it is counted $$d(x)$$ times if $$x\in S_i$$, and $$0$$ otherwise. So in total it is counted $$d(x)^2$$ times. Thus

$$\frac{1}{2} \left( \sum_{i, j}|S_i \cap S_j| -\sum_i |S_i| \right) = \frac{1}{2}\left( \sum_{x\in X}d(x)^2 - \sum_{x\in X}d(x) \right) = \sum_{x\in X} {d(x) \choose 2}$$

So you get the inequality

$$\sum_{x\in X} {d(x) \choose 2} \leq k |E|$$

Can you take it from here?

• Got it, thanks. Mar 26 at 7:07