Conjecture on Partitions of Powerset Without Empty Set

co.combinatoricsextremal-combinatorics

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.

Best Answer

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]$.

Related Solutions

[Math] Characterization of infinite paths in graphs

(Not an answer, but too long for a comment)

One way to look at what you're asking for is a theory in some appropriate language which axiomatizes that we have a serial directed rooted graph, and a collection of subsets of the graph which behaves like $N(\mathcal{G},s)$, where the part of the axiomatization that dictates the behaviour of $N(\mathcal{G},s)$ doesn't say anything about the graph relation on $\mathcal{G}$. I'll give an axiomatization where the part that talks about $N(\mathcal{G},s)$ does mention the graph relation, and I'll set it up in such a way that it'll seem unlikely that it can be redone without mentioning the graph relation. I'm not sure about this, it's just an idea, but it's too long for a comment.

The Language

Consider the language $(\bar{V}, \bar{N}, \bar{E}, \bar{s}, \bar{\epsilon})$ - two unary relation symbols, one binary relation symbol, one constant symbol, and another binary relation symbol, respectively. I'm going to set up a theory whose finite models will be precisely (sort of) those in which $(\bar{V}, \bar{E})$ is interpreted as a directed serial graph $\mathcal{G}$, $\bar{s}$ gets interpreted as a member $s$ of $\bar{V}$, $\bar{N}$ gets interpreted as $N(\mathcal{G},s)$, and $\bar{\epsilon}$ gets interpreted as the membership relation, a subset of $\bar{V} \times \bar{N}$. Setting up the right theory is easy, the only part that will require a little explanation is how we ensure $\bar{N}$ gets interpreted correctly.

Axiomatizing $N(\mathcal{G},s)$ when we're allowed to mention the edge relation

Consider a formula like: $$x_1 = \bar{s} \wedge x_1 \neq x_2 \wedge x_1 \neq x_3 \wedge x_2 \neq x_3$$ $$\wedge \bar{E}(x_1,x_2) \wedge \bar{E}(x_2,x_1) \wedge \neg \bar{E}(x_1,x_3) \wedge \neg \bar{E}(x_3,x_1) \wedge \neg \bar{E}(x_2,x_3) \wedge \neg \bar{E}(x_3,x_2)$$ It "says" we have three distinct $x_i$, the first one is $s$, and it tells you exactly which pairs stand in edge relation to one another and which don't. You can also tell by looking at it that it defines a set $\{ x_1, x_2, x_3\}$ which contains an infinite path starting at $s$, namely $x_1, x_2, x_1, x_2, \dots$.

Let's define $\mathcal{R}$ to be the set of formulas in the language $(\bar{s}, \bar{E})$ of the form $\phi(x_1, \dots , x_n)$ which say that the $x_i$ are distinct, and which tell you precisely which pairs of the $x_i$ stand in $\bar{E}$ relation to one another, and which don't. Define $\mathcal{R}^+$ to be those formulas $\phi \in \mathcal{R}$ such that for any rooted directed graph $((V,E),s)$, we have that:

$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \in N((V,E),s)$.

$\mathcal{R}^-$ will be those $\phi$ such that:

$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \not\in N((V,E),s)$.

Alright, now here's our theory:

(Rooted serial directed graph) $\bar{V}(\bar{s}) \wedge \forall x \bar{V}(x) \rightarrow [\neg \bar{E}(x,x) \wedge \exists y (\bar{V}(y) \wedge \bar{E}(x,y))]$
(Schema for what goes in $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^+$: $\forall \vec{x} \exists Y \forall x \left (\phi(\vec{x}) \rightarrow \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$
(Schema for what stays out of $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^-$: $\forall \vec{x} \forall Y \exists x \left (\phi(\vec{x}) \rightarrow \neg \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$

Checking this axiomatization works

It's clear that if $\mathcal{G} = (V,E)$ is a finite directed serial graph and $s \in V$, then $(V,N(\mathcal{G},s),E,s,\in)$ is a model of this theory. Conversely, if we have a finite model $(V,N_0,E,s,\epsilon)$ of this theory, then $(V,E)$ forms a directed serial graph with $s \in V$. Now let $N_1$ consist of those $Y \in N_0$ such that $\forall x (x \epsilon Y \rightarrow V(x))$. I claim that:

$N((V,E),s) = \{ \{x : x \epsilon Y\} : Y \in N_1\}$

But I won't prove this.

A remark about some "unnaturalness"

It should seem like I could have done things differently so that things looked more natural and the above claim could be proved more easily. The way I've written 2 and 3 are not the most natural, but I've done it for a reason. 2 says that if $\vec{x}$ is a tuple which is sure to contain an infinite path starting at $s$, then there's a member of $N$ consisting precisely of the members of $\vec{x}$. 3 says that if $\vec{x}$ is sure to not contain an infinite path starting at $x$, then there's nothing in $N$ consisting precisely of the members of $\vec{x}$. The formulas in 2 and 3 are in prenex normal form, where the matrix is a conditional where the left side only involves the symbols $\bar{E}$ and $\bar{s}$, and the right side only $\bar{N}$ and $\bar{\epsilon}$. Moreover, the antecedents have variables $\vec{x}$ and the consequents have variables $\vec{x}, Y, x$.

The point

You want a theory equivalent to axiom 1 and schemas 2 and 3 above, but you want to replace 2 and 3 with (probably finitely many) axioms which don't mention the symbol $\bar{E}$. I feel like there ought to be some interpolation-type theorem (along the lines of Craig Interpolation or Lyndon Interpolation) which says this can't happen, i.e. something which says that a theory in which each axiom mention either only $\bar{V}, \bar{E}, \bar{s}$ or only $\bar{V}, \bar{N}, \bar{s}, \bar{\epsilon}$ can't prove a theory which has axioms like those in schemas 2 or 3.

Combinatorics – Conjecture About Families of Subsets of $\{1,\ldots,2n+1\}$ of Size $n+1$

This is false in general. Let $X=\{1, \dots, n+1\}$, $Y=\{n+1, \dots, 2n+1\}$, and $Z$ be any $(n+1)$-subset of $[2n+1]$ not containing $n+1$. Let $\mathcal{F}=\mathcal{A} \setminus \{X,Y,Z\}$. Then for all $j \in [n]$, we may take $R_j(\mathcal{F})=[n]$, since $Y \notin \mathcal{F}$. Similarly, for all $j \in \{n+2, \dots, 2n+1\}$ we may take $R_j(\mathcal{F})=\{n+2, \dots, 2n+1\}$, since $X \notin \mathcal{F}$. Finally, we may take $R_{n+1}(\mathcal{F})$ to be the complement of $Z$, since $Z \notin \mathcal{F}$. Thus, $r(\mathcal{F}) \leq n$. This is a counterexample to your conjecture, provided $n \geq 6$.

Best Answer

Related Solutions

[Math] Characterization of infinite paths in graphs

Combinatorics – Conjecture About Families of Subsets of $\{1,\ldots,2n+1\}$ of Size $n+1$

Related Question