the largest $F\subseteq \{0,1\}^n$ that can be defined by $m$ critical indices

Question

Please forgive me if this sounds non-mathy problem.

Consider $F\subseteq \{0,1\}^{n}$ and the set of all possible partitions $\mathscr{P}$ of $F$ into two sets $S^+$ and $S^-$. An index $i\in {1,2,\dots,n}$ is a critical index to a partition $S^+$ and $S^-$ if and only if :

1. It has the same value $b\in \{0,1\}$ in all the elements of $S^+$.
2. It has the same value $b'\in \{0,1\}$ in all the elements of $S^-$.
3. $b\neq b'$.

What is the largest $F\subseteq \{0,1\}^n$ such that there is always at most one critical index explains its partitions? the critical index is not necessarily the same index for every partition. It could be $i$ in $p$ but $j\neq i$ in $p'$ for $p,p'\in \mathscr{P}$.

Example: $n=3$ (0,0,0),(0,1,1),(1,1,0) is the largest $F\subseteq \{0,1\}^3$ where there is at most one critical index for every possible partition. For any partition of these, we always have one critical index. For instance $S^+=\{(0,0,0),(1,1,0)\}$ and $S^-=\{(0,1,1)\}$ have $i=3$ as critical index.

The problem must have been studied before in mathematical terms; But I don't know the correct words for it. A generalization to it is to look for the largest set that is explained by at most $1<m<n$ indices.

Answer 1

Let $F$ be a subset of $\{0,1\}^n$ with the desired properties where $|F| = k$. Notice the number of partitions of $F$ into two non-trivial sets is $\frac{2^k-2}{2} = 2^{k-1}-1.$ This gives rise to $2^{k-1}-1$ critical indices. If $2^{k-1}-1 > n$, then two of these critical indices must fall on the same index $i$. That means we have two distinct sets $S_1$ and $S_2$ such that,

$$\forall s \in S_1, s_i =1 \wedge \forall s \in F \setminus S_1, s_i = 0 $$

and

$$\forall s \in S_2, s_i =1 \wedge \forall s \in F \setminus S_2, s_i = 0 .$$

Consider an element $s \in S_1$. We know $s_i = 1$. We know that $s_i$ is either in $S_2$ or $F \setminus S_2$. If $s_i \in F \setminus S_2$, then $s_i = 0$, a contradiction, thus, $s_i \in S_2$. From this, we see $S_1 \subseteq S_2$. Similarly, $S_2 \subseteq S_1$, and thus $S_1 = S_2$, a contradiction since the two sets are supposed to be distinct. This contradiction means that it must be the case that $2^{k-1}-1 \leq n$.

Solving the above inequality for $k$, we see that, $$k \leq \log_2(n+1)+1.$$

In the example where $n=3$, the above inequality means that $$k \leq \log_2(3+1)+1 = \log_2(4)+1 = 2+1=3,$$ which is consistent with the example.