# Can an arbitrary ordering of the $\binom{n}{2}$ slopes of the lines connecting $n$ points in $\mathbb{R}^2$ always be realized?

Given $$n$$ variable points on the plane, $$(x_i,y_i)$$, let the slope of the line connecting point $$i$$ and point $$j$$ be $$m_{ij}$$. If I specify an arbitrary ordering of all of these slopes, $$m_{ij} do there always exist values $$x_i,y_i$$ such that this ordering is satisfied?

• I have no idea what the question means – David C. Ullrich May 22 at 21:23
• Do I get that right that you do not want to specify any of the $m_{i,j}$, but only impose something like $m_{1,2}<m_{3,5}<m_{2,4}<m_{2,5}<m_{1,42}<\ldots$? With equality allowed for some or not? – Hagen von Eitzen May 22 at 21:25
• Equality is not allowed, I have edited the question to shoe this – cplusplusguru May 22 at 21:29
• I like this problem! – kimchi lover May 22 at 21:42
• This is a pretty interesting question. How did you come across a problem like this? Also, what have you tried? It smells like induction ... – Laz May 22 at 21:54

Place two points, $$A$$ and $$B$$, in the plane. Consider possible placements of a third point, $$C$$. The line $$m_{A, B} = m_{A, C} = m_{B, C}$$ is the line through $$A$$ and $$B$$. $$m_{A, C}$$ is discontinuous on the line through $$A$$ perpendicular to the x-axis, and similarly for $$B$$. These three lines divide the plane into six areas, each of which has a different order for the three gradients.

Suppose we place $$C$$ such that $$m_{A, B} < m_{A, C} < m_{B, C}$$ and $$D$$ such that $$m_{A, B} < m_{B, D} < m_{A, D}$$. Then we have forced $$m_{C, D} > m_{A, B}$$. (If we make $$m_{A,B}$$ negative the areas marked remain essentially unchanged, it's just the angles between the lines which change. If we swap $$A$$ and $$B$$ we also swap $$C$$ and $$D$$).

Therefore the answer to your question is that some orderings are impossible.

• I don't see how considering just one possible placement of $C,D$ is supposed to provide a general counterexample. – Ingix May 23 at 16:39
• @Ingix, it's not "one possible placement". It's every possible placement of $C$ and $D$ anywhere in their respective areas (which correspond exactly to constraints on the partial order). – Peter Taylor May 23 at 16:45

Not an answer, but evidence of sorts. I asked my computer to pick 1,000,000 random quadruplets of points in the plane, resulting in $$6=\binom 4 2$$ slopes each time. Each time I asked the computer to compute the ordering, and to tabulate the number of distinct orderings seen. This number might have been as big as $$6!=720$$ but my computer this time only saw $$192$$ distinct orderings.

I asked my computer to show me how many times each ordering came up (to get a handle on how thoroughly this procedure explored the space of all orderings) and found that the rarest ordering came up 3369 times and the most popular 6619 times. I attach no significance to the exact values of these counts, except to note that it is consistent with there being only $$192$$ orderings possible and with my program hitting them again and again.

Based on this, I would guess that not all possible orderings are possible. (But of course I might have a computer bug making me miscalculate the ordering, or my method of picking random points might make me miss some orderings.)

Consider three points $$A,B,C$$, where $$x_A. Then $$m_{AC}$$ is a convex combination of $$m_{AB}$$ and $$m_{BC}$$, hence is between these. We conclude that a given orderring of the slopes allows us to recover the "horizontal between" relation for our points. In particular, if for four points $$A,B,C,D$$, we impose $$m_{AB} then $$m_{AB} i.e., (horizontally) $$B$$ is between $$A$$ and $$C$$, and $$C$$ is between $$A$$ and $$D$$, and $$B$$ is between $$C$$ and $$D$$ - which is impossible (we would need $$C$$ between $$B$$ and $$D$$). Fix A at the origin.

Giving $$m_{A,B}$$ you get a line through the origin, where B can occupy whichever position.
Same, giving $$m_{A,C}$$, will fix another line through the origin containing point C.

Then the value of $$m_{B,C}$$ will determine a set of parallel lines, not parallel to the precedent two. So they will always cross the precedent, and the crossing determines B and C, with one degree of freedom remaining.

Introducing the fourth point D, then $$m_{B,D}$$ and $$m_{C,D}$$ give two sets of lines, stemming from the possible B's and C's.
These lines are not parallel between themselves, nor are they parallel to any one already existing.
They will form two sets of parallel lines, depending on the parameter defining the set of BC lines, crossing along a line containing D.
The sketch should help to figure that out.

Now the additional line $$m_{A,D}$$ will in general (unless exactly parallel to line D) cross the above and fix D, and thus also B and C.

After that it is clear that four lines through four fixed points are not going in general to meet at a single point E.
Only two values of $$m$$ can be given, to fix the point E: the others shall be consequently determined.

Same for any further point : only two values of $$m$$ free, the others are dependent.