1
$\begingroup$

Let $\mathcal{F}_1, \ldots, \mathcal{F}_h$ be families of finite sets. Let $\mathcal{G}_{i,j} = \mathcal{F}_i \cap \mathcal{F}_j, 1 \le i \lt j \le h$. We know that $|\mathcal{G}_{i,j}| \ge h$ and $\mathcal{F}_i \cap \mathcal{F}_j \cap \mathcal{F}_k =\emptyset, 1 \le i \lt j \lt k \le h$ We know also that the intersection of any $A_i \in \mathcal{F}_{i}, 1 \le i \le n$, is empty: $\bigcap_{i=1}^h A_i = \emptyset$. Let $\mathcal{U} = \{A \cup B : A,B \in \mathcal{F}_1 \cup \cdots \cup \mathcal{F}_h, A \not= B\}$.

I would like to find a good lower bound for the size of $\mathcal{U}$ as a function of $h$. Ideally, I would like a bound $\approx h$.

My attempt:

Let $\mathcal{H} = \{\mathcal{G}_{i_k,j_k}: 1 \le k \le n\} \subseteq \{\mathcal{G}_{i,j}: 1 \le i \lt j \le h \}$ with the property that $\bigcup_{k=1}^n \{i_k,j_k\} = [h] = \{1, \ldots, h \}$ and $\{i_k,j_k\}, 1 \le k \le n$ are all different. By the conditions in the first paragraph, the intersection of any two families in $\mathcal{H}$ must be empty.

Let $\mathcal{U}_{p,q} = \{A_p \cup A_q: A_p \in \mathcal{G}_{i_p,j_p} \in \mathcal{H}, A_q \in \mathcal{G}_{i_q,j_q} \in \mathcal{H}\}, 1 \le p \lt q \le n$.

I know that the map:

$$\mathcal{G}_{i_1,j_1} \times \cdots \times \mathcal{G}_{i_n,j_n} \rightarrow \mathcal{U}_{1,2} \times \cdots \times \mathcal{U}_{1,n} \times \mathcal{U}_{2,3} \times \cdots \times \mathcal{U}_{2,n} \times \mathcal{U}_{3,4} \times \cdots \times \mathcal{U}_{3,n} \times \cdots \times \mathcal{U}_{n-1,n}, \\(A_1,\ldots,A_n) \rightarrow (A_1 \cup A_2, \ldots, A_1 \cup A_n, A_2 \cup A_3, \ldots, A_2 \cup A_n, A_3 \cup A_4, \ldots, A_4 \cup A_n, \ldots, A_{n-1} \cup A_n)$$

is injective, because if $(A_1 \cup A_2, \ldots, A_{n-1} \cup A_n) = (B_1 \cup B_2, \ldots, B_{n-1} \cup B_n)$ on the right side, then $A_k \setminus B_k \subseteq A_k \cap \bigcap_{1 \le m \le n, m \not= k} B_m = \emptyset, 1 \le k \le n$ and similarly $B_k \setminus A_k \subseteq \emptyset$, thus $A_k = B_k$.

Since $|\mathcal{U}| \ge |\mathcal{U}_{p,q}|, 1 \le p \lt q \le n$ and $|\mathcal{G}_{i,j}| \ge h, 1 \le i \lt j \le h$ then $|\mathcal{U}|^{n(n-1)/2} \ge h^n$, i.e.:

$$|\mathcal{U}| \ge h^\frac{2}{n-1}$$

For $h$ even, we could choose for example $i_k = 2k-1, j_k = 2k, 1 \le k \le n = h/2$. But this doesn't seem much unless $h$ is small. Is there a different construction that can do better than that?

$\endgroup$

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.