This conjecture is similar to the previously disproved one, but more difficult.
For any partition $\mathcal{F}=\{\mathcal{A_1},\ldots,\mathcal{A_m} \}$ of the powerset without the empty set element $\mathcal{P}([n]) \setminus \{\emptyset\}$, define the following algorithm:
- Define $\mathcal{G}_0 = \emptyset$. Select an element $i_1 \in [n]$. Let $J_1 = \{i_1\}$. Let $k = 1$.
- Let $\mathcal{G}_k = \mathcal{G}_{k-1} \cup \{\mathcal{A} \in \mathcal{F} : \exists S \in \mathcal{A} : i_k \in S\}$.
- Select an element $i_{k+1} \in [n], i_{k+1} \not\in J_k : \exists \mathcal{A} \in \mathcal{G}_k : \exists S \in \mathcal{A} : i_{k+1} \in S \land J_k \cap S = \emptyset$. If such an element does not exist let $\mathcal{H}_{(i_1,\ldots,i_k)} = \mathcal{G}_k$ and stop, otherwise go on.
- Let $J_{k+1} = J_k \cup \{i_{k+1}\}$.
- Let $k := k+1$ then repeat from step 2.
The conjecture is:
$$\forall \mathcal{F} \space \exists (i_1,\ldots,i_k) : \vert \mathcal{H}_{(i_1,\ldots,i_k)} \vert \ge \Big\lceil \frac{m}{2} \Big\rceil$$
For example for $n = 5$, $\mathcal{A}_q = \{\{q\}\}, 1 \le q \le 5$, $\mathcal{A}_6 = \mathcal{P}([n]) \setminus \{\emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{5\} \}$ (counterexample for the linked question), we can choose $i_1 = 1$, then $\mathcal{G}_1 = \{ \mathcal{A}_1, \mathcal{A}_6 \}$, then we can choose $i_2 = 2$, because $2 \in \{2,3\} \in \mathcal{A}_6 \in \mathcal{G}_1$ and $1 \not\in \{2,3\}$, then $\mathcal{G}_2 = \{ \mathcal{A}_1, \mathcal{A}_2, \mathcal{A}_6 \}$ and so on till obtaining $\vert \mathcal{H}_{(1,2,3,4)} \vert = \vert \{ \mathcal{A}_1, \mathcal{A}_2, \mathcal{A}_3, \mathcal{A}_4, \mathcal{A}_6 \} \vert =5 \gt 3$.
Can we found a counterexample or say something else about this conjecture?
