MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(updated; apologies for way too much room left for interpretation in the original post)

Let $\mathcal{A} =A_{n-1}$ be the $A_{n-1}$ arrangement in $\mathbb{R}^{n}$, i.e. the set of hyperplanes $H_{ij}$ specified by equations $x_i=x_j$, for $1\leq i\leq j\leq n$. It is well-known that the connected components $c$ of the complement of the intersection of $\mathcal{A}$ with the affine hyperplane $H$={$x\mid \sum_i x_i=1$} (let me call them cells) are in 1-to-1 correspondence with permutations $\sigma(c)\in S_{n}$, so that crossing the hyperplane $H_{ij}$ corresponds to multiplication by the transposition $(i,j)$. More precisely, $\sigma(c)$ records the order of (Euclidean) distances $d(x,e_k)$ at which the standard basis vectors $e_k$ are from every $x\in c$. E.g. for $\sigma(c)=()=12 \dots n$, the identity permutation, one has $d(x,e_1)$<$d(x,e_2)$<...<$d(x,e_n)$, and the arrangement hyperplanes on the boundary of this $c$ are $H_{k,k+1}$ for $k=1,\dots ,n -1$.

Let $\ell$ be a general position line in $H$. Then $\ell$ intersects $\binom{n}{2}+1$ cells. Two of these intersections are unbounded; let us denote the corresponding cells $c_0$ and $c_t$, respectively. As we follow $\ell$ from $c_0$ to $c_t$, from one cell to the next, the corresponding permutation $\sigma(c) = i_1 i_2...$ $i_n$ changes from $\sigma(c_0)$ to $\sigma(c_t)$; namely, it gets multiplied by $(i_k,i_{k+1})$ whenever we cross $H_{i_k,i_{k+1}}$. One can also view this as flipping the adjacent entries, i.e. applying the transposition $(k,k+1)$ to the sequence $\sigma(c)$.

Assume that $\sigma(c_0)$ is the identity permutation. Then $\ell$ specifies a sequence of flips $(k,k+1)$ that need to be applied to obtain $\sigma(c_t)=n, n-1, n-2, \ldots 1$. E.g. for $n=3$ there are two such sequences:

  1. (12), (23), (12)
  2. (23), (12), (23)

Question. Are all the sequences of $\binom{n}{2}$ flips leading from $1,2, \dots, n$ to $n, n-1, n-2, \ldots 1$ realized by general position lines in $H$?

share|cite|improve this question
up vote 3 down vote accepted

I find your description of the combinatorial data you want to use to encode crossing sequences a little unclear. However, I am confident that the answer to your intended question is "no". I will describe combinatorial data which at least as restrictive as what you have described, and show that this is still not restrictive enough.

For simplicity, I will consider paths from the identity region to $n(n-1) \cdots 321$. I will describe such a path by giving (1) the sequence of chambers it passes through: $v_0 = \mathrm{Id}$, $v_1$, $v_2$, ..., $v_{\binom{n}{2}} = n(n-1) \cdots 321$ and (2) the sequence of walls crossed at every step $(i_1 \ j_1)$, $(i_2 \ j_2)$, ..., $(i_{\binom{n}{2}} \ j_{\binom{n}{2}}$). I require at every step that the wall $(i_r \ j_r)$ really does separate regions $v_{r-1}$ and $v_{r}$. Using my favorite conventions, this is equivalent to

$$v_{r} = (i_r \ j_r) v_{r-1} \ \mbox{and} \ v_{r-1}^{-1} (i_r \ j_r) v_{r-1} = (k_r \ (k_r+1))$$ for some $k_r$. (Other people may use the inverse convention for labeling regions of the $A_n$ arrangement by permutations, or for multiplying permutations, but it shouldn't be hard to translate.)

In terms of Fedja's metaphor of the $n$ runners, the second condition says that runners $i_r$ and $j_r$ really are next to each other at time $r-1$, in positions $k_r$ and $k_r+1$.

Note that you can recover the $v$'s from the $(i \ j)$'s as $v_r = (i_r \ j_r) (i_{r-1} \ j_{r-1}) \cdots (i_2 \ j_2) (i_1 \ j_1)$, so we could just record the sequence of transpositions. However, you would need to recompute the $v$'s to state the condition that $ v_{r-1}^{-1} (i_r \ j_r) v_{r-1} = (k_r \ (k_r+1))$ for some $k_r$. Even better is just to record the sequence of $k$'s, in which case the $v$'s can be recovered as $v_r = (k_1 \ k_1+1) (k_2 \ k_2 +1 ) \cdots (k_r \ k_r+1)$. In this language, what I am describing is reduced words for $n(n-1) \cdots 321$.

For example, there are two reduced words for $321$ in $S_3$: $$\begin{array}{|l|l|l|} \hline v_r & (i_r \ j_r) & k_r \\ \hline 123,\ 213,\ 231,\ 321 & (1\ 2 ),\ (1\ 3),\ (2\ 3) & 1,\ 2,\ 1 \\ 123,\ 132,\ 312,\ 321 & (2\ 3),\ (1\ 3),\ (1\ 2) & 2,\ 1,\ 2 \\ \hline \end{array}$$

It is not clear to me whether the data you are describing is the same as this, or something more permissive. (For example, $(1\ 2)(2\ 3)(1\ 2)$ also has product $321$, but, would correspond to the sequence of chambers $x \lt y \lt z$, $y \lt x \lt z$, $z \lt x \lt y$, $z \lt y \lt x$, and the middle two chambers are not adjacent. I assume you don't want to permit this, but I don't see any place where you say it is not legitimate.)

However, it doesn't matter, because even reduced words for $n(n-1) \cdots 321$ are not restrictive enough to describe all straight lines through the $A_{n-1}$ arrangement once $n \geq 9$.

As fedja suggests, if we have a linear path from the $123\ldots n$ region to the $n (n-1) \cdots 321$ region, we can think of it as describing the positions of $n$ runners who move at constant rates, starting in order $12 \ldots (n-1) n$ and ending in the reverse order.

Similarly, a reduced word for $n(n-1) \cdots 321$ can be realized as a simple pseduoline arrangement: An arrangement of $n$ paths in $\mathbb{R}^2$ each of which divide the plane in two and only cross in pairs, with each pair only crossing once. And this dictionary is reversable: Every pseduoline arrangment where all $\binom{n}{2}$ pairs of lines cross gives us a reduced word. (You'll often hear pseudoline arrangements called "wiring diagrams" when used in this context.)

Here is the key point:

For $n \leq 8$, every simple pseudoline arrangement where all pairs of lines cross is realizeable by actual straight lines. However, for $n=9$, this is not true.

Pseudoline arrangements which cannot be realized using straight lines are called non-stretchable. See Section 5.3 of the Handbook of Discrete and Computational Geometry, or Chapter 7 of Ziegler's Lectures on Polytopes, for examples of nonstretchable arrangements. Peter Shor has shown that it is NP-Hard to determine whether a given pseudo-line arrangement is stretchable.

share|cite|improve this answer
Thanks, great, that's precisely what we are looking for! (One needs to embed $\ell$ in a plane and obtain an arrangement of lines.) It even answers a more general question than the original. – Dima Pasechnik Nov 25 '12 at 7:13

I'm not sure if I understand the question correctly, but stripped of all high tech language, it seems to be "Having $n$ runners on the road, can we arrange any order of their pairwise meeting times?". In this formulation, the answer is clearly "No". Assign one runner as a standing checkpoint. Then if the two runners meet outside the interval bounded by their checkpoint crossings, they have to run in the same direction and if they meet inside that interval, they must to run in the opposite directions. Now let the relative time arrangement be

checkpoint1=1, checkpoint 2=3, checkpoint3=4,

meeting12=5, meeting23=6, meeting 13=2.

i.e., the corresponding impossible permutation is (2,3)(1,2)(3,0)(2,0)(1,3)(1,0).

share|cite|improve this answer
It looks as if you stripped too much. Indeed, your permutation equals (), the trivial permutation, as you can see by multiplying these (2,3)(1,2)(3,0)(2,0)(1,3)(1,0) out. Surely this has nothing to do with being able to get from () to a permutation which is far from it in the combinatorial sense, e.g. in terms of the distance in the Cayley graph of $S_n$ on transpositions. – Dima Pasechnik Nov 24 '12 at 14:27
Is distance in the combinatorial sense what this question was about? I thought it was about whether expressions could be realized in terms of general position lines. – Will Sawin Nov 24 '12 at 14:45
The question I am struggling a bit to formulate, as I see from responses, is about a combinatorial order being realizable by a geometric construction... – Dima Pasechnik Nov 24 '12 at 15:36
You can easily add 4 more runners and get the inverse permutation as initially requested. However, since now you require true adjacency of the swapping runners at every moment, I'd better look at the final correct formulation than explain how to modify the example to satisfy just the formal requirement of getting 765...210 out of 01...67 :). – fedja Nov 25 '12 at 0:15

Not every hyperplane touches every cell. In fact, every cell touches only $n-1$ of the $\left(\begin{array}{c} n \\ 2 \end{array}\right)$ hyperplanes. Thus, many sequences are impossible.

But suppose you have a general position curve that intersects each hyperplane once. It might still be impossible, owing to the fact that the cells are convex. While a curve can leave a cell and return to the same cell, a line cannot. I think this is a de-stripped version of fedja's answer, but I haven't checked carefully.

So suppose your curve never returns to a cell it's been too before? Well, project it down from $\mathbb R^n$ to $\mathbb R^{n-1}$ by removing a coordinate. Does it still have that property? If not, it can't come from a generic line - because a generic line, projected, is still a generic line.

So suppose your curve intersects each hyperplane exactly once, each cell at most once, and the inverse image of each cell on each projection at most once. At this point I'm not sure if there are any more obstructions.

share|cite|improve this answer
I don't understand the comment. My $c_t$ is already selected, it is far from $c_0$ in the sense that $\ell$ has to cross all the hyperplanes of the arrangement. E.g. for $n=3$ the cell $c_t$ can chosen to correspond to $\sigma(c_t)=(13)$, where the cell $c_0$, with $\sigma(c_0)=()$, is bounded by hyperplanes $H_{12}$ and $H_{23}$. Actually, if I am not mistaken, one can assume in general that $\sigma(c_t)=(1,n)(2,n-1)(3,n-2)...(i+1,n-i)...$ – Dima Pasechnik Nov 24 '12 at 15:13
Yes I think so. Thus, in the "runners" formulation of the question, one assumes that the runners switch positions, with the front runner ending up in the back and the back runner ending up in the front. – Will Sawin Nov 24 '12 at 19:10

Your Answer


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.