Return to Question

Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:

$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$

Let $\mathcal{F} = \{A_1 \cup B_k, 1 \le k \le m\}$. Clearly $\mathcal{G}$ and $\mathcal{F}$ are disjoint. Also, $A_1 \cup B_j = A_1 \cup B_k$ implies $B_j = B_k$, therefore we know that $|\mathcal{F}| = m$.

Now let $\mathcal{G'} = \{ A_1',A_2',B_1',\ldots,B_m' \}$ be a family of $m + 2$ non-empty finite distinct sets with the following properties:

1. $A_1' \cap A_2' \cap B_k' = \emptyset, 1 \le k \le m$
2. $A_1' \not\subseteq A_2'$, $A_2' \not\subseteq A_1'$, $A_j' \not\subseteq B_k'$, $B_k' \not\subseteq A_j'$, $1 \le j \le 2$, $1 \le k \le m$

Let $\mathcal{F'} = \{A_1' \cup B_k', A_2' \cup B_k', A_1' \cup A_2' \cup B_k', 1 \le k \le m\}$. Clearly $\mathcal{G'}$ and $\mathcal{F'}$ are disjoint.

Any idea for extending the reasoning for $\mathcal{G}, \mathcal{F}$ to $\mathcal{G'}, \mathcal{F'}$ in order to obtain a lower bound for $|\mathcal{F'}|$ as a function of $m$?

For a motivation, I am trying to find a proof for case $m = 3$ in this question ($m$ there has not the same meaning as $m$ here).

EDIT:

There is a given answer that suggests that the lower bound is something near to $2 \sqrt{m}$. The first paragraph is clear to me, it gives an example where $|\mathcal{F}'| = 2\sqrt{m}+1$. From what I understand, the second paragraph says that the example given in the first paragraph is quite near to the actual lower bound, therefore I presume that the lower bound is $2 \sqrt{m}$ or something like that.

I understand that if e.g. $B_1 \cup A_i = B_2 \cup A_1$ for $i = 1$ or $i = 2$, then $B_1 \setminus B_2 \subseteq A_1$. If we have also $B_1 \cup A_i = B_2 \cup A_2$ for $i = 1$ or $i = 2$, then $B_1 \setminus B_2 \subseteq A_2$. Then $B_1 \setminus B_2 \subseteq A_1 \cap A_2$, and $B_1 \setminus B_2 \subseteq A_1 \cap A_2 \cap B_1$, but by hypothesis $A_1 \cap A_2 \cap B_1 = \emptyset$, therefore $B_1 \subseteq B_2$. Then if we have also that $B_2 \cup A_i = B_1 \cup A_1$ for $i = 1$ or $i = 2$, and $B_2 \cup A_i = B_1 \cup A_2$ for $i = 1$ or $i = 2$, then $B_2 \subseteq B_1$, then $B_1 = B_2$, but $B_1, B_2$ are required to be distinct.

It is enough to have $B_1 \cup A_1 = B_2 \cup A_1$ and $B_1 \cup A_2 = B_2 \cup A_2$ to imply $B_1 = B_2$, or alternatively $B_1 \cup A_1 = B_2 \cup A_2$ and $B_1 \cup A_2 = B_2 \cup A_1$.

Getting the lower bound from there doesn't seem to be completely obvious because I asked a clarification at mathstackexchange and didn't get any answer.

Someone can help to elaborate the given answer?

Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:

$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$

Let $\mathcal{F} = \{A_1 \cup B_k, 1 \le k \le m\}$. Clearly $\mathcal{G}$ and $\mathcal{F}$ are disjoint. Also, $A_1 \cup B_j = A_1 \cup B_k$ implies $B_j = B_k$, therefore we know that $|\mathcal{F}| = m$.

Now let $\mathcal{G'} = \{ A_1',A_2',B_1',\ldots,B_m' \}$ be a family of $m + 2$ non-empty finite distinct sets with the following properties:

1. $A_1' \cap A_2' \cap B_k' = \emptyset, 1 \le k \le m$
2. $A_1' \not\subseteq A_2'$, $A_2' \not\subseteq A_1'$, $A_j' \not\subseteq B_k'$, $B_k' \not\subseteq A_j'$, $1 \le j \le 2$, $1 \le k \le m$

Let $\mathcal{F'} = \{A_1' \cup B_k', A_2' \cup B_k', A_1' \cup A_2' \cup B_k', 1 \le k \le m\}$. Clearly $\mathcal{G'}$ and $\mathcal{F'}$ are disjoint.

Any idea for extending the reasoning for $\mathcal{G}, \mathcal{F}$ to $\mathcal{G'}, \mathcal{F'}$ in order to obtain a lower bound for $|\mathcal{F'}|$ as a function of $m$?

For a motivation, I am trying to find a proof for case $m = 3$ in this question ($m$ there has not the same meaning as $m$ here).

EDIT:

There is a given answer that suggests that the lower bound is something near to $2 \sqrt{m}$. The first paragraph is clear to me, it gives an example where $|\mathcal{F}'| = 2\sqrt{m}+1$. From what I understand, the second paragraph says that the example given in the first paragraph is quite near to the actual lower bound, therefore I presume that the lower bound is $2 \sqrt{m}$ or something like that.

I understand that if e.g. $B_1' \cup A_i' = B_2' \cup A_1'$ for $i = 1$ or $i = 2$, then $B_1' \setminus B_2' \subseteq A_1'$. If we have also $B_1' \cup A_i' = B_2' \cup A_2'$ for $i = 1$ or $i = 2$, then $B_1' \setminus B_2' \subseteq A_2'$. Then $B_1' \setminus B_2' \subseteq A_1' \cap A_2'$, and $B_1' \setminus B_2' \subseteq A_1' \cap A_2' \cap B_1'$, but by hypothesis $A_1' \cap A_2' \cap B_1' = \emptyset$, therefore $B_1' \subseteq B_2'$. Then if we have also that $B_2' \cup A_i' = B_1' \cup A_1'$ for $i = 1$ or $i = 2$, and $B_2' \cup A_i' = B_1' \cup A_2'$ for $i = 1$ or $i = 2$, then $B_2' \subseteq B_1'$, then $B_1' = B_2'$, but $B_1', B_2'$ are required to be distinct.

It is enough to have $B_1' \cup A_1' = B_2' \cup A_1'$ and $B_1' \cup A_2' = B_2' \cup A_2'$ to imply $B_1' = B_2'$, or alternatively $B_1' \cup A_1' = B_2' \cup A_2'$ and $B_1' \cup A_2' = B_2' \cup A_1'$.

Getting the lower bound from there doesn't seem to be completely obvious.

Someone can help to elaborate the given answer?

Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:

$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$

Let $\mathcal{F} = \{A_1 \cup B_k, 1 \le k \le m\}$. Clearly $\mathcal{G}$ and $\mathcal{F}$ are disjoint. Also, $A_1 \cup B_j = A_1 \cup B_k$ implies $B_j = B_k$, therefore we know that $|\mathcal{F}| = m$.

Now let $\mathcal{G'} = \{ A_1',A_2',B_1',\ldots,B_m' \}$ be a family of $m + 2$ non-empty finite distinct sets with the following properties:

1. $A_1' \cap A_2' \cap B_k' = \emptyset, 1 \le k \le m$
2. $A_1' \not\subseteq A_2'$, $A_2' \not\subseteq A_1'$, $A_j' \not\subseteq B_k'$, $B_k' \not\subseteq A_j'$, $1 \le j \le 2$, $1 \le k \le m$

Let $\mathcal{F'} = \{A_1' \cup B_k', A_2' \cup B_k', A_1' \cup A_2' \cup B_k', 1 \le k \le m\}$. Clearly $\mathcal{G'}$ and $\mathcal{F'}$ are disjoint.

Any idea for extending the reasoning for $\mathcal{G}, \mathcal{F}$ to $\mathcal{G'}, \mathcal{F'}$ in order to obtain a lower bound for $|\mathcal{F'}|$ as a function of $m$?

For a motivation, the question is related to the family of sets in this answer.

EDIT:

There is a given answer that suggests that the lower bound is something near to $2 \sqrt{m}$. The first paragraph is clear to me, it gives an example where $|\mathcal{F}'| = 2\sqrt{m}+1$. From what I understand, the second paragraph says that the example given in the first paragraph is quite near to the actual lower bound, therefore I presume that the lower bound is $2 \sqrt{m}$ or something like that.

I understand that if e.g. $B_1 \cup A_i = B_2 \cup A_1$ for $i = 1$ or $i = 2$, then $B_1 \setminus B_2 \subseteq A_1$. If we have also $B_1 \cup A_i = B_2 \cup A_2$ for $i = 1$ or $i = 2$, then $B_1 \setminus B_2 \subseteq A_2$. Then $B_1 \setminus B_2 \subseteq A_1 \cap A_2$, and $B_1 \setminus B_2 \subseteq A_1 \cap A_2 \cap B_1$, but by hypothesis $A_1 \cap A_2 \cap B_1 = \emptyset$, therefore $B_1 \subseteq B_2$. Then if we have also that $B_2 \cup A_i = B_1 \cup A_1$ for $i = 1$ or $i = 2$, and $B_2 \cup A_i = B_1 \cup A_2$ for $i = 1$ or $i = 2$, then $B_2 \subseteq B_1$, then $B_1 = B_2$, but $B_1, B_2$ are required to be distinct.

It is enough to have $B_1 \cup A_1 = B_2 \cup A_1$ and $B_1 \cup A_2 = B_2 \cup A_2$ to imply $B_1 = B_2$, or alternatively $B_1 \cup A_1 = B_2 \cup A_2$ and $B_1 \cup A_2 = B_2 \cup A_1$.

Getting the lower bound from there doesn't seem to be completely obvious because I asked a clarification at mathstackexchange and didn't get any answer.

Someone can help to elaborate the given answer?

Consider a family $\mathcal{G} = \{ A_1,B_1,\ldots,B_m \}$ of $m+1$ non-empty finite distinct sets with the following property:

$$A_1 \cap B_k = \emptyset, 1 \le k \le m$$

Let $\mathcal{F} = \{A_1 \cup B_k, 1 \le k \le m\}$. Clearly $\mathcal{G}$ and $\mathcal{F}$ are disjoint. Also, $A_1 \cup B_j = A_1 \cup B_k$ implies $B_j = B_k$, therefore we know that $|\mathcal{F}| = m$.

Now let $\mathcal{G'} = \{ A_1',A_2',B_1',\ldots,B_m' \}$ be a family of $m + 2$ non-empty finite distinct sets with the following properties:

1. $A_1' \cap A_2' \cap B_k' = \emptyset, 1 \le k \le m$
2. $A_1' \not\subseteq A_2'$, $A_2' \not\subseteq A_1'$, $A_j' \not\subseteq B_k'$, $B_k' \not\subseteq A_j'$, $1 \le j \le 2$, $1 \le k \le m$

Let $\mathcal{F'} = \{A_1' \cup B_k', A_2' \cup B_k', A_1' \cup A_2' \cup B_k', 1 \le k \le m\}$. Clearly $\mathcal{G'}$ and $\mathcal{F'}$ are disjoint.

Any idea for extending the reasoning for $\mathcal{G}, \mathcal{F}$ to $\mathcal{G'}, \mathcal{F'}$ in order to obtain a lower bound for $|\mathcal{F'}|$ as a function of $m$?

For a motivation, I am trying to find a proof for case $m = 3$ in this question ($m$ there has not the same meaning as $m$ here).

EDIT:

There is a given answer that suggests that the lower bound is something near to $2 \sqrt{m}$. The first paragraph is clear to me, it gives an example where $|\mathcal{F}'| = 2\sqrt{m}+1$. From what I understand, the second paragraph says that the example given in the first paragraph is quite near to the actual lower bound, therefore I presume that the lower bound is $2 \sqrt{m}$ or something like that.

I understand that if e.g. $B_1 \cup A_i = B_2 \cup A_1$ for $i = 1$ or $i = 2$, then $B_1 \setminus B_2 \subseteq A_1$. If we have also $B_1 \cup A_i = B_2 \cup A_2$ for $i = 1$ or $i = 2$, then $B_1 \setminus B_2 \subseteq A_2$. Then $B_1 \setminus B_2 \subseteq A_1 \cap A_2$, and $B_1 \setminus B_2 \subseteq A_1 \cap A_2 \cap B_1$, but by hypothesis $A_1 \cap A_2 \cap B_1 = \emptyset$, therefore $B_1 \subseteq B_2$. Then if we have also that $B_2 \cup A_i = B_1 \cup A_1$ for $i = 1$ or $i = 2$, and $B_2 \cup A_i = B_1 \cup A_2$ for $i = 1$ or $i = 2$, then $B_2 \subseteq B_1$, then $B_1 = B_2$, but $B_1, B_2$ are required to be distinct.

It is enough to have $B_1 \cup A_1 = B_2 \cup A_1$ and $B_1 \cup A_2 = B_2 \cup A_2$ to imply $B_1 = B_2$, or alternatively $B_1 \cup A_1 = B_2 \cup A_2$ and $B_1 \cup A_2 = B_2 \cup A_1$.

Getting the lower bound from there doesn't seem to be completely obvious because I asked a clarification at mathstackexchange and didn't get any answer.

Someone can help to elaborate the given answer?