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$ Sep 20 at 17:40
  • $\begingroup$ @ChristopheLeuridan no it is just at least one $a \in [n]$. $\endgroup$ Sep 20 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.