This is a question I came up with when studying machine learning. A simple example revealing the limit of linear classifiers would be the four vertices of a square, one diagonal labelled $+1$ and the other $-1$.
What about the converse statement? For simplicity, consider a $\pm 1$-labelling of $\{0,1\}^n$ not containing any rectangle with (both vertices of) one diagonal $+1$ and the other $-1$. Would it necessarily be linearly separable?
I have tried induction on dimension but failed as the separating plane is not unique. Neither did I find any counterexample in low dimensions. After all this is just a fun question and might not have a simple answer. Thank you in advance if you have any ideas or suggestions.