“Orphans” are things you meant to think about but which you’ve regretfully concluded are never going to rise to the top of the stack. Ideas you never finished having.
Blogging your orphans seems a good use of a math blog, or even a partial math blog like this one — at best, someone else will be able to tell you what’s interesting about your question, or even derive some interest from it themselves; and at worst, someone will be able to explain to you why your question is in fact not interesting, thus setting your mind at ease.
Anyway: the mention of Voronoi cells reminded me of a question that once vexed me about combinatorial geometry in R^2. The question actually arose from an article I wrote about Howard Rosenthal and Keith Poole, political scientists who use data from Congressional votes to map legislators onto low-dimensional Euclidean space. But their method doesn’t really specify points in R^n. When n = 1, for instance, what they get is not a set of 535 points on the real line, but an ordering of the 535 legislators along an axis representing liberalism at one end and conservatism at the other.
What’s really being recorded by the projection of Congress to R^2? I think it’s something like this — for each triple of legislators (x,y,z) you ask: is z to the left or the right of the ray that starts at x and proceeds towards y?
There are n! possible orderings of n points on the line. How many “orderings” are there of n points in the plane?
An algebraic combinatorist might phrase the question like this: Let M be a 3xn matrix with real entries, where the third column consists entirely of 1’s. Suppose every 3×3 minor of M is nonsingular. Then let f(M) be a function from the set of 3-tuples of distinct elements of [1..n] to the set {+1,-1}, where you assign to each 3-tuple (i,j,k) with i < j < k the sign of the determinant of the 3×3 matrix formed by rows i,j,k of M.
Question: As M ranges over 3xn matrices of the given form, how many different functions f(M) are there?
An obvious upper bound is 2^(n choose 3), but this is way too big. Note that if you replace “3” by “2”, the answer to the analogous question is n!.
As a geometer, I’d phrase the question in a different (but I think equivalent) way:
Question: Let X_n be the space of ordered n-tuples of points in R^2 such that no three points are collinear. How many components does X_n have?
Again, if you replace R^2 with R^1 and “no three points are collinear” with “no two points coincide,” you get n!.
Let a(n) be the answer to the questions above (which, if I am not confused, have the same answer.) Then a(3) = 2 and a(4) = 14, and I think maybe a(5) is 252 but I’m not really sure. Combinatorial geometers with a soft spot for orphans, tell me more!
Quomodocumque 