6
$\begingroup$

I would like to have some ideas about possibilities of proving or disproving the following conjecture:

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\}$, and defined $\mathcal{F}_a = \{\mathcal{A} \in \mathcal{F} : \exists B \in \mathcal{A} : a \in B\}$, there exists $x \in [n]$ such that $\vert \mathcal{F}_x \vert \ge \big\lfloor \frac{m}{2} \big\rfloor$.

For example, for $n = 4$, a possible family $\mathcal{F}$ is: $$\{\{\{1\}\}, \{\{2\}\}, \{\{1,3\}, \{2,3\}\}, \{\{4\}\}, \{\{1,4\}, \{2,4\}\}, \{\{1,2\}, \{3\}, \{1,2,3\}, \{1,2,4\}, \{3,4\}, \{1,3,4\}, \{2,3,4\}, \{1,2,3,4\}\}\}$$ with $m = 6$ and $\vert \mathcal{F}_1 \vert = 4 \ge 3$, $\vert\mathcal{F}_2 \vert = 4 \ge 3$, $\vert\mathcal{F}_3 \vert = 2 \lt 3$, $\vert\mathcal{F}_4 \vert = 3 \ge 3$.

I have tested all cases for $n \le 4$, however I don't see how to go further with brute force.

$\endgroup$
2
  • $\begingroup$ The statement of the question is not clear. I suppose that you mean $\mathcal{P}([n]) \setminus \{\emptyset\}$, and that you note $\mathcal{F}_a = \{\mathcal{A} \in \mathcal{F} : \exists B \in \mathcal{A} : \{a\} \in B\}$ for all $a \in [n]$? $\endgroup$ Commented Sep 20, 2023 at 17:40
  • $\begingroup$ @ChristopheLeuridan no it is just at least one $a \in [n]$. $\endgroup$ Commented Sep 20, 2023 at 18:24

2 Answers 2

10
$\begingroup$

Here is a counterexample for $n=5$. Partition the non-empty subsets of $\{1, \dots, 5\}$ into the singleton subsets and a sixth family containing all the other non-empty subsets. So, $m=6$ and $|\mathcal{F}_i|=2$ for all $i \in [5]$.

$\endgroup$
6
$\begingroup$

Partition the subsets of $\{1,2,\dots, 100\}$ as $\{\mathcal{A_1},\ldots,\mathcal{A_6}\}$ by defining $$\mathcal{A_i}=\{S\in \mathcal{P}([100]) \setminus \{\emptyset\}: \text{all elements of S are} \,\equiv i \pmod{6}\}$$ for $1\le i\le 5$, and letting $\mathcal A_6$ consist of all the remaining subsets. You can check that $|\mathcal F_x|\le 2$ for all $x$, providing a counterexample.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .