# Existence of a family of sets with some properties

Is it possible to find an example of a family $$\mathcal{F}$$ of $$n$$ finite distinct non-empty 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?

• Can't you take $4k$ random subsets of $[k]$, each of size $k/4$? Commented Oct 3, 2022 at 21:42
• 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. Commented Oct 4, 2022 at 6:12
• @PeterTaylor sorry I meant distinct, I edited the question now. Commented Oct 4, 2022 at 6:22
• @mathworker21 yes, thank you, I think it works for $k \ge 16$. Commented Oct 4, 2022 at 6:27
• I guess it can be adapted to work with $k \lt 16$. Commented Oct 4, 2022 at 6:41

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}(n-1)$$ sets; every element of $$S$$ is in $$\frac{1}{2}(n-1)$$ sets; $$x$$ is in one set. Every pair of sets which does not include $$\{x\}$$ has a non-empty intersection. The size of the universe is $$|S| + 8$$, so this family satisfies all of the constraints provided that $$4|S| + 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^{a-1} < \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$$.
• 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? Commented Oct 4, 2022 at 16:59