15
$\begingroup$

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

$\endgroup$
7
  • 4
    $\begingroup$ It's enough to consider $\ \forall_i\,|A_i|=\left\lceil\frac n3\right\rceil$. $\endgroup$
    – Wlod AA
    Apr 20, 2021 at 8:48
  • 2
    $\begingroup$ 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. $\endgroup$
    – Louis D
    Apr 20, 2021 at 14:36
  • 2
    $\begingroup$ 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|)$. $\endgroup$
    – Louis D
    Apr 20, 2021 at 14:44
  • 3
    $\begingroup$ Can you elaborate on "Remark 2"? Is this just for $a=1$ or is it really for any constant $a$? $\endgroup$
    – Louis D
    Apr 21, 2021 at 2:00
  • 14
    $\begingroup$ @XiheLi Please do not delete your questions after someone answered them. -- Deleting someone else's work can be perceived as rude. $\endgroup$
    – Stefan Kohl
    Apr 21, 2021 at 19:17

2 Answers 2

6
$\begingroup$

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

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

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.

$\endgroup$
9
  • $\begingroup$ 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 ... $\endgroup$ Apr 22, 2021 at 10:55
  • $\begingroup$ ... 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. $\endgroup$ Apr 22, 2021 at 10:58
  • $\begingroup$ 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. $\endgroup$ Apr 22, 2021 at 11:12
  • $\begingroup$ @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. $\endgroup$
    – domotorp
    Apr 22, 2021 at 11:56
  • 1
    $\begingroup$ No, it would give $a=1$: every 3 points are in one plane. $\endgroup$ Apr 22, 2021 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy