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

Question

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<j<k\leq n$, $|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|$.)

Answer 1

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$.

Answer 2

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.