# n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $$A_1, A_2, \ldots, A_n$$ be $$n$$ sets such that:

(1) for each $$i\in [n]$$, $$\frac{n}{3}\leq |A_i|\leq n$$;

(2) for any $$1\leq i, $$|A_i\cap A_j\cap A_k|\leq a$$, where $$a$$ is a constant and $$n$$ is sufficiently large.

What is $$\min |A_1\cup A_2\cup \cdots \cup A_n|$$? Is it $$\Omega(n^2)$$ or $$o(n^2)$$?

Remark 1. If we change condition (2) to $$|A_i\cap A_j|\leq a$$ for every $$i\neq j$$, then the problem is related to Corradi's lemma (in the language of hypergraph) https://de.wikipedia.org/wiki/Lemma_von_Corr%C3%A1di

Remark 2. I can prove $$\min |A_1\cup A_2\cup \cdots \cup A_n|=\Omega(n^{\frac{3}{2}})$$ for any constant $$a$$ using some double counting arguments. (Hint: Let $$A=A_1\cup A_2\cup \cdots \cup A_n$$, and for any $$x\in A$$, let $$d(x)=|\{A_i\colon\, x\in A_i, i\in [n]\}|$$. Then $$\sum_{x\in A}d^3(x)=\sum_{(i,j,k)\in [n]^3}|A_i\cap A_j\cap A_k|$$.)

• It's enough to consider $\ \forall_i\,|A_i|=\left\lceil\frac n3\right\rceil$. Apr 20, 2021 at 8:48
• A small observation is that if $a=0$, then every element is in at most two sets and thus $|A_1\cup \dots \cup A_n|\geq \frac{1}{2}\sum_{i=1}^n|A_i|$. So in this case $\min |A_1\cup \dots \cup A_n|=\Omega(n^2)$ even if the sets have much fewer than $n/3$ elements. Apr 20, 2021 at 14:36
• Perhaps a bit more generally, if the average degree (i.e. average number of sets each element is contained in) of the hypergraph is constant, then $\min |A_1\cup \dots \cup A_n|=\Omega(\sum_{i=1}^n|A_i|)$. Apr 20, 2021 at 14:44
• Can you elaborate on "Remark 2"? Is this just for $a=1$ or is it really for any constant $a$? Apr 21, 2021 at 2:00
• @XiheLi Please do not delete your questions after someone answered them. -- Deleting someone else's work can be perceived as rude. Apr 21, 2021 at 19:17

Let $$m$$ be chosen later, and let $$A_1, A_2, \dots, A_n$$ be independently chosen random subsets of $$\{1,2,\dots m\}$$, each having size $$n$$.

For a fixed $$a+1$$-tuple $$(x_1, x_2, \dots, x_{a+1})$$ of distinct elements from $$\{1,\dots,m\}$$, and a fixed triple $$(i,j,k)$$, the probability that $$\{x_1, \dots, x_a\} \subseteq A_i \cap A_j \cap A_k$$ is at most $$\left(\frac{n}{m}\right)^{3a+3}$$. Taking the union bound over all $$x_1, x_2, \dots, x_{a+1}$$ and all $$(i,j,k)$$, the probability that there is some collection of $$a+1$$ elements in the intersection of some $$3$$ sets is at most $$m^{a+1} n^3 \left(\frac{n}{m}\right)^{3a+3} = n^{6+3a} m^{-2a-2}$$ In particular, if $$m=n^{\alpha}$$ and $$\alpha>\frac{6+3a}{2a+2} = \frac{3}{2}\left(1+\frac{1}{a+1}\right)$$, there is a positive probability that none of the intersections is larger than $$a$$, so a collection of subsets of $$[m]$$ must exist with no large intersections.

This gives an $$o(n^2)$$ bound for $$a \geq 3$$.

• Does this contradict the other answer?? Apr 22, 2021 at 3:02
• I'm sorry everyone, but the numbers in my previous answer made no sense at all. Please see the fix. Apr 22, 2021 at 7:44

It can be $$O(n^{\frac32})$$ for $$a\ge 1$$ if the sets $$A_i$$ correspond to the $$p^2$$ points of a smooth surface in an appropriate surface in a 3-dimensional space over $$\mathbb F_p$$ and your points are the $$p^3$$ general position planes, with $$p^2$$ planes through each point. There are no 3 collinear points if the surface is chosen appropriately, so for any 3 points we only have the unique plane through them, this gives $$a=1$$. The main idea can be found in Remark 4 here: Rudnev - On the number of incidences between points and planes in three dimensions, while the modification for this question has been made by Emil in the comment to this answer.

Your Remark 2 practically implies the main result of Rudnev, Theorem 3, and practically the same argument appears in Lemma 3.1 of de Zeeuw: A short proof of Rudnev's point–plane incidence bound.

• I’m not sure what is the purpose of the last edit. Since sets are points and elements are planes, the fact that any 3 planes (or indeed, 2 planes) have at most 3 points in common just means that any set of size 3 is included in at most 3 sets $A_i$, which is neither here nor there. What you are supposed to show instead is that any triple of points is included in only a constant number ($a$) of planes. Since collinear points lie in $p\approx\sqrt n$ planes, this just means that no 3 points can be collinear (in which case the property will hold with $a=1$). Remark 4 somehow arranges that ... Apr 22, 2021 at 10:55
• ... no 4 points are collinear by throwing out $O(1)$ lines, but it’s not clear to me how you lower this down to no 3 points collinear. Apr 22, 2021 at 10:58
• Though, why do you want the surface to be cubic? Perhaps it might work if it is quadratic: if, additionally, the surface does not include a whole line, then indeed no 3 points are collinear. Apr 22, 2021 at 11:12
• @Emil Oops, you are right, I again got confused because I (incorrectly) keep on thinking that points go to vertices. Then one should think about the example given in Remark 4 more to see why it is assumed that the surface is cubic, or if quadratic is enough. Apr 22, 2021 at 11:56
• No, it would give $a=1$: every 3 points are in one plane. Apr 22, 2021 at 20:52