Is it possible to find an example of a family $\mathcal{F}$ of $n$ finite distinct nonempty sets, a universe of maximum size $n/4$, with at least $\lfloor \frac{2}{3}{n \choose 2} \rfloor$ unordered couples of sets with at least one element in common between the two sets, and no element belonging to at least $n/2$ sets of the family?

4$\begingroup$ Can't you take $4k$ random subsets of $[k]$, each of size $k/4$? $\endgroup$– mathworker21Commented Oct 3, 2022 at 21:42

$\begingroup$ If the sets don't have to be distinct, you could take a finite projective plane and have the family of sets consist of four copies of the lines. $\endgroup$– Peter TaylorCommented Oct 4, 2022 at 6:12

$\begingroup$ @PeterTaylor sorry I meant distinct, I edited the question now. $\endgroup$– Fabius WiesnerCommented Oct 4, 2022 at 6:22

$\begingroup$ @mathworker21 yes, thank you, I think it works for $k \ge 16$. $\endgroup$– Fabius WiesnerCommented Oct 4, 2022 at 6:27

$\begingroup$ I guess it can be adapted to work with $k \lt 16$. $\endgroup$– Fabius WiesnerCommented Oct 4, 2022 at 6:41
1 Answer
Take a finite projective plane: for the sake of concreteness, the Fano plane $PG(2, 2)$. It has seven points $P$ and seven lines $L$, where each line goes through three points and each pair of lines intersects.
Take a second set $S$ which is disjoint from $P$ and an element $x$ which is not in either. Consider $$\mathcal{F} = L \times 2^S \cup \{\{x\}\}$$ and let $n = \mathcal{F} = 7 \cdot 2^{S} + 1$. Every element of $P$ is in $\frac{3}{7}(n1)$ sets; every element of $S$ is in $\frac{1}{2}(n1)$ sets; $x$ is in one set. Every pair of sets which does not include $\{x\}$ has a nonempty intersection. The size of the universe is $S + 8$, so this family satisfies all of the constraints provided that $4S + 32 \le 7 \cdot 2^{S} + 1$, which is true if $S \ge 3$.
For more general values of $n$, let $a$ be the largest integer such that $7 \cdot 2^a < n$. If we take two disjoint sets $S_1, S_2$ with $S_1 = S_2 = a$ then $L \times \left(2^{S_1} \cup 2^{S_2} \right)$ has more than $n$ sets, but each element of $S_1 \cup S_2$ occurs exactly $7 \cdot 2^{a1} < \frac n2$ times. Each element of $P$ occurs exactly $3 \cdot 2^{a+1}$ times, so when choosing $\mathcal{F} \subset L \times \left(2^{S_1} \cup 2^{S_2} \right)$ we should be careful to keep the projection onto $L$ balanced, but if we do this then each element of $P$ will occur no more than $\frac{3}{7}n + 3$ times.
Then we simply require that the universe be sufficiently small. Now the size of the universe is $7 + 2a$, and we find that the construction works for $n \ge 44$.

$\begingroup$ I think you mean $P=\{p_1,p_2,p_3,p_4,p_5,p_6,p_7\}$, $L=\{\{p_1,p_2,p_3\},\ldots\}$, $L \times 2^S = \{A \cup B : A \in L \land B \in 2^S\}$, right? $\endgroup$ Commented Oct 4, 2022 at 16:59
