# Improving a lower bound for the minimum of the maximum frequency of an element in a family of sets

[Originally posted at math.stackexchange without answer]

Consider a family $$\mathcal{F}$$ of $$n=|\mathcal{F}|$$ sets, $$\emptyset \not\in \mathcal{F}$$ and an universe $$U(\mathcal{F})$$ of $$q=|U(\mathcal{F})|$$ elements.

It is known that at least a fraction $$r\binom{n}2$$, $$0 \lt r \lt 1$$, of the unordered couples of sets of $$\mathcal{F}$$, have at least one element in common, i.e. $$|\{\{A_1,A_2\}: A_1,A_2 \in \mathcal{F} \land A_1 \not= A_2 \land A_1 \cap A_2 \not= \emptyset \}| \ge r\binom{n}2$$.

If we find the lowest $$m$$ such that:

$$\binom{m}2 \ge \frac{r\binom{n}2}q$$

we can then say that there exists an element belonging to at least $$m$$ sets of $$\mathcal{F}$$.

However since those $$m$$ sets cannot be made of only one element, I think the bound can be improved, i.e. we can say that there is an element in at least $$m'$$ sets:

$$m' = f(r,n,q) \gt m$$

Any idea for doing that?

• Ask another question please. This question and answer are interesting and I think should remain Commented Feb 6, 2023 at 17:34
• @kodlu ok, I have removed the edit. Commented Feb 6, 2023 at 19:55

I do not think the bound can be improved without further assumptions. For example, consider the family $$\mathcal{F}$$ consisting of all singleton subsets of $$\{1, \dots, n-1\}$$ together with $$\{1, \dots, n-1\}$$. Here $$q=n-1$$, and $$r\binom{n}{2}=n-1$$. Thus, the smallest $$m$$ for which $$\binom{m}{2} \geq \frac{r\binom{n}{2}}{q}$$ is $$m=2$$. However, there is no element which is contained in $$3$$ sets of $$\mathcal{F}$$, so the bound is tight.