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 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 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 at 14:44
  • 2
    $\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 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 at 19:17
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 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 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 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 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 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 at 11:56
  • 1
    $\begingroup$ No, it would give $a=1$: every 3 points are in one plane. $\endgroup$ Apr 22 at 20:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.