SSL Minutes

17 May 2001
Dominic & ...

---

Baxter Permutations

Hal makes a conjecture that a series of moves such as the one described below can produce (1) only baxter permutations and (2) all of the baxter permutations. He was right on (1), but not on (2). Counterexample for (2): permutation 152436.

Dominic produced the following proof of (1):

---

Given any identity matrix, we can transpose any any number of 1's along the diagonal. For example, we can take

100000
010000
001000
000100
000010
000001

and transpose the four interior 1's to get

100000
000010
000100
001000
010000
000001

Claim: any such transposition (and successive transpositions) will yield a Baxter Permutation.

Proof: Recall that a Baxter Permutation can be defined as any permutation that fits #.p.p<.p>.p+1.#' where # and #' are unimportant, p is any number in {1,2,...,n-1}, p< is a sequence of numbers less than p, and p> is a sequence of numbers greater than p.

Let [ ] denote the list of numbers that we are transposing. In the previous example, [ ] would contain the numbers 2,3,4,5.

Case 1: Assume p and p+1 are both outside [ ]. This means both are either less than or greater than each number in [ ]. Then all of [ ] is in either # or #'. This is the unimportant stuff. So transposing [ ] does not affect p or p+1. they are still adjacent to each other in the ASM, so p< and p> are both empty. This fits the definition of a Baxter Permutation.

Case 2: Assume p and p+1 are both inside [ ]. Then transposing [ ] will not separate p and p+1. They will still be adjacent to each other. So again, p< and p> are empty. This again fits the definition of a Baxter Permutation.

Case 3: Either p or p+1 is inside [ ], but not both. If p is inside [ ] and p+1 is not, then p must be the maximum element in [ ] (recall we started with the identity matrix). Then transposing [ ], we get: [p-k ... p-2 p-1 p] p+1 -----> [p p-1 p-2 ... p-k] p+1. But this fits the definition of a Baxter permutation with p< containing p-1...p-k and p> as the empty set. If p is outside [ ] and p+1 is inside, then p+1 must be the minimum element in [ ]. Then transposing [ ], we get: p [p+1 p+2 p+3 ... p+k] -----> p [p+k ... p+3 p+2 p+1]. But this fits the definition of a Baxter permutation with p> containing p+1...p+k and p< as the empty set.

Thus, any transposition of elements along the diagonal of an identity matrix (and any successive such transposition) will yield a Baxter Permutation.

That finishes the proof.

---