Suppose we have a set of $n$ points $\{X\_1,X\_2,\dots,X\_n\}$ in the real plane and $\mathcal{A}$ a family of subsets of $\{1,\dots,n\}$.


By a "set of collinearity conditions for $\mathcal{A}$" we mean the conditions of collinearity for every subset $\{X\_i:i\in A\}$ s.t. $A\in\mathcal{A}$. I'm interested in determining families for which the induced collinearity conditions imply that all of the points are on the same line.


One way to propose a counterexample for a given family is to select three non-collinear points $Y\_1,Y\_2,Y\_3$ and for each $1\leq i\leq n$ declare $X\_i$ to be one of $Y\_j$'s ($j=1,2,3$), in such a way that every one of $Y\_j$'s have been selected at least one time and further for every $A\in \mathcal{A}$ one of $Y\_j$'s doesn't appear among $\{X\_i:i\in A\}$. Then this set of $n$ non-collinear points satisfies the collinearity conditions for $\mathcal{A}$. This observations leads naturally to the following conjecture:



> 
> Conjecture: The collinearity conditions for a family $\mathcal{A}$ implies collinearity of all of the points if and only if there doesn't exist a partition of $\{1,\dots,n\}$ into three nonempty disjoint sets $\{B\_1,B\_2,B\_3\}$ s.t. for every $A\in \mathcal{A}$, $A$ is contained in the union of at most two of $B\_i$'s.
> 
> 
> 


(In fact similar conjectures can be stated in higher dimensions, if we regard the existence of a hyperplane containing all of the points.) 


Is this conjecture true? If yes, how the imposed equivalent condition can be checked? what's the related notion in (hyper)graph theory? Are there any related theorems to this problem?


Thanks for your advice!



When does a set of collinearity conditions imply collinearity of all of the points?
Yes, if a collection of colinearity conditions is realizable, then they are realizable using only 3 distinct points.


Suppose that $x\_1$, $x\_2$, ..., $x\_n$ in $\mathbb{R}^2$ is a collection of points realizing your colinearity conditions, and not all on a line. Choose two unequal points $x\_i$ and $x\_j$, and let $\overline{x\_i x\_j}$ be the line through them. 


Take $B\_1$ to be the set of $x\_k$ which are equal to $x\_i$ (same point in $\mathbb{R}^2$); take $B\_2$ to be the set of $x\_k$ which are on the line $\overline{x\_i x\_j}$ but not in $B\_1$ and take $B\_3$ to be everything else. If a colinearity condition met all three of $(B\_1, B\_2, B\_3)$, then this would correspond to a line which met $\overline{x\_i x\_j}$ at $x\_i$ and another point, and also passed through a point not on $\overline{x\_i x\_j}$.


Obviously, this works for configurations in $\mathbb{R}^{k-1}$ just as well: Choose points $x\_1$, $x\_2$, ..., $x\_k$ with no linear relations between them, and let $B\_d$ be the points which are in the affine linear span of $(x\_1, \ldots, x\_d)$ but not of $(x\_1, \ldots, x\_{d-1})$. 




---


Let me explain where I had seen this construction before.


Work with $n$ points in $\mathbb{RP}^2$ rather than $\mathbb{R}^2$, to increase the symmetries available. Then we can encode our points as the columns of a $3 \times n$ matrix, up to rescaling of columns (because coordinates in $\mathbb{RP}^2$ are only up to scaling). Collinearity conditions say that various submatrices have rank $2$. You want to know if you can impose that various submatrices have rank $2$ without forcing the whole matrix to have rank $2$. And you only care about solutions where none of the columns are identically zero, since homogenous coordinates on projective space cannot all be zero.


So your question is: 



> 
> Suppose we have a $3 \times n$ matrix $M$, of rank $3$, with no zero columns. Can we make there only be three distinct columns, while preserving the "rank $2$"-ness of specified submatrices.
> 
> 
> 


All your conditioned are unaltered by acting on the matrix by $GL\_3$ on the left, so we can think on the space $GL\_3 \backslash \{ \mbox{$3 \times n$ matrices of rank $3$} \}$, also known as the Grassmannian $G(3,n)$. The advantage of the Grassmannian is that is compact. If we build a family $M(t)$ of rank $3$ matrices, parametrized by $t \neq 0$ and preserving all the rank $2$-ness conditions, then it will have some limit as $t \to 0$, which we can lift back to a rank $3$ matrix. EG: $\left( \begin{smallmatrix} 1 & 0 & 0 &0 \\ 0 & t & t^2 & t^3 \\ 0 & 0 & t & t \\ \end{smallmatrix} \right)$ looks like it is approaching a matrix of rank $1$ as $t \to 0$, but it is the same family up to $GL\_3$ action as $\left( \begin{smallmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & t & t^2 \\ 0 & 0 & 1 & 1 \\ \end{smallmatrix} \right)$, whose limit is rank $3$. So I can approach your question by building families $M(t)$, passing through $M$, and preserving the rank $2$-ness of various submatrices, and be guaranteed that my limits will exist.


An easy way to build a family of matrices that preserves the rank of all $3 \times (\mbox{whatever})$ submatrices is to look at $M \cdot X(t)$, where $X(t)$ is a one parameter subgroup of the diagonal matrices in $GL\_n$. For most one parameter subgroups, some columns will become $0$ in the limit, so we can't use them.


The set of one parameter subgroups for which none of the columns die is called the [Bergman complex](http://arxiv.org/abs/math/0311370). The most common elements of the Bergman complex are indexed by "complete chains in the lattice of flats". Removing the matroid jargon, in the case of the plane, this means "a point $x\_i$, and a line $\overline{x\_i x\_j}$ through the point".
What I wrote out was the limiting $3 \times n$ matrix for that case.


