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:

\begin{equation} |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). \end{equation}

Still a missing $r/2$, however.


1 Answer 1


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<j}|S_i \cap S_j|$ 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<j}|S_i \cap S_j| = \frac{1}{2} \left( \sum_{i, j}|S_i \cap S_j| -\sum_i |S_i| \right)$$

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?


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .