Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
But what happens if all $n$ points should be distinct? –  Ilya Bogdanov Jun 24 at 23:37

2 Answers 2

up vote 9 down vote accepted

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

share|improve this answer

Your conjecture is true, at least if you allow degenerate realizations where some of the points coincide (and with some form of the axiom of choice).

Clearly, if there does exist a partition of this type, then there is a non-collinear realization of your collinearity conditions: just place each of your $n$ points at the vertex of an equilateral triangle corresponding to its set in the partition.

In the other direction, suppose you have a realization of your collinearity conditions in which not all points are collinear. Under the axiom of choice, there exists a 3-coloring of the plane in which each line is 2-colored (see e.g. Hales and Straus, "Projective colorings", Pacific J. Math. 1982) and by an appropriate affine transformation of such a coloring you can make any three of its points, with three different colors, coincide with a chosen three non-collinear points of your realization. Then the coloring gives you your desired partition.

share|improve this answer
2  
Wouldn't it be enough (even if there are infinitely many $X_i$ and $A_j$) to have no $3$ colored lines? So color the entire plane green except color the origin red and the rest of the $x$-axis blue. Then use an affine transformation to map three non-collinear points to $(0,0)$, $(1,0)$ and $(0,1)$. Of course then it looks like David Speyer's solution. –  Aaron Meyerowitz Jun 24 at 21:24
    
Yes, that seems like a big simplification. –  David Eppstein Jun 24 at 21:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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