|
In a recent Day[9] Daily (292), Sean mentions something about a his thesis. From out his lips come the word "Baxter Permutation". Being the good netizen I am I instantly google it as I have never heard of such a thing before. Unfortunately there is no Wikipedia article, so I am basically boned in terms of understanding wtf this is.
Here is the text you find from the first link if you google it ( http://arxiv.org/abs/0805.4180 ) :
Abstract: We present a simple bijection between Baxter permutations of size $n$ and plane bipolar orientations with n edges. This bijection translates several classical parameters of permutations (number of ascents, right-to-left maxima, left-to-right minima...) into natural parameters of plane bipolar orientations (number of vertices, degree of the sink, degree of the source...), and has remarkable symmetry properties. By specializing it to Baxter permutations avoiding the pattern 2413, we obtain a bijection with non-separable planar maps. A further specialization yields a bijection between permutations avoiding 2413 and 3142 and series-parallel maps.
...
...
...
Can someone please translate this into English please? Clearly the person who wrote that paragraph is much smarter than me because that piece of text has a higher ratio of (Bullshit words I can't understand) to (Real words that I understand) than if I were to read something in French or German.
Alternatively if no one knows what a Baxter Permutation, at least tell me what it is used for and what field of science it is used in, so I can know to stay the fuck away from that field when I get into university.
|
bijection is a one-to-one and onto mapping from set a to set b
permutation is amount of ways re-arranging a set of objects
edges are lines connecting vertices in graph theory
vertices are nodes
i dont know what a baxter permutation is, but that passage is most likely extremal graph theory
(the article does in no way explain what a baxter permutation is btw, but is most likely a subset of permutations)
|
I don't actually know much math but that looks like discrete mathematics. Graphs and sets and such.
Really there's a lot of stuff in every field that looks really esoteric to laymen. I can read something about theology and wtf for hours.
|
|
|
The best part of this is that the url mashed "S. Plott" to "splott", which is an awesome word.
|
It's abstract mathematics.
Don't touch that field unless you really love math because it will mind fuck you.
|
It's actually not hard to understand. There are several ways to think of permutations, but in this case you can think of a permutation as a list of numbers from 1 to n, with each number occurring exactly once.
For example, when n=3 there are 6 permutations:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Now, what is a Baxter permutation? Basically it is a permutation that avoids a certain pattern. So if you look at the list of numbers and see
... a ... b c ... d ...
such that c < a < d < b then the permutation is not Baxter. (Note that there can be numbers in between a and b and between c and d, but b and c must be adjacent). The other pattern to be avoided is b < d < c < a.
As to why they are useful, I can't say without more reading.
Examples:
2 4 1 3 and
4 1 3 2
are NOT Baxter permutations, but all other permutations with length 4 are Baxter permutations.
Disclaimer: could easily be a mistake here, since I haven't encountered these before.
Edit: see correction by ]343[ below.
|
I can read it, but I don't really understand what is going on. What munchmunch wrote definitely makes sense, hopefully Sean will come in and clear anything else up.
The only other thing to say is that his thesis is very kinky :p
|
Baxter permutation is before killer started to replace Jaedong as the Zerg Ace for Hwaseung Oz.
|
On April 27 2011 12:16 jodogohoo wrote:
Baxter permutation is before killer started to replace Jaedong as the Zerg Ace for Hwaseung Oz.
Hahaha too true!
|
United States10328 Posts
On April 27 2011 11:09 munchmunch wrote:
It's actually not hard to understand. There are several ways to think of permutations, but in this case you can think of a permutation as a list of numbers from 1 to n, with each number occurring exactly once.
For example, when n=3 there are 6 permutations:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Now, what is a Baxter permutation? Basically it is a permutation that avoids a certain pattern. So if you look at the list of numbers and see
... a ... b c ... d ...
such that c < a < d < b then the permutation is not Baxter. (Note that there can be numbers in between a and b and between c and d, but b and c must be adjacent). The other pattern to be avoided is b < d < c < a.
As to why they are useful, I can't say without more reading.
Examples:
2 4 1 3 and
4 1 3 2
are NOT Baxter permutations, but all other permutations with length 4 are Baxter permutations.
Disclaimer: could easily be a mistake here, since I haven't encountered these before.
Hmm, I think it says 3 1 4 2 and 2 4 1 3 are not Baxter permutations (yeah, that sounds right, since the inequalities they give are exactly opposite each other.)
A permutation is a rearrangement of an ordered set. What munchmunch says is right, but they try to avoid c < a < d < b and b < d < a < c (just a misreading by him  )
So apparently in an amusing coincidence, two different, unrelated people with surname Baxter discovered two different things that could be counted by a certain big expression: Baxter permutations, and plane bipolar maps.
Plane bipolar maps are pretty much a set of points in the plane connected by arrows (directed lines, not necessarily straight) with a certain set of properties (if you start anywhere and follow arrows, you can't get back to where you started; and there are two points on the "outside" of the diagram, one that only has arrows going out, and one that only has arrows going in.)
If we introduce a few more restrictions, and count the number of such maps with a certain number of points/arrows, we can find a one-to-one correspondence to the number of Baxter permutations with certain properties.
This is probably classified as discrete math -> combinatorics -> graph theory / algebraic combinatorics. Looks similar to one of my classes
|
On April 27 2011 13:02 ]343[ wrote:Hmm, I think it says 3 1 4 2 and 2 4 1 3 are not Baxter permutations (yeah, that sounds right, since the inequalities they give are exactly opposite each other.) A permutation is a rearrangement of an ordered set. What munchmunch says is right, but they try to avoid c < a < d < b and b < d < a < c (just a misreading by him )
I think you're right, thanks for the correction. 
|
The things Team Liquid has to offer never seize to amaze me. I put my friend to sleep reading this to him. Thank you TL! :D
|
United States10328 Posts
pretending to know math: a useful talent toi have
|
|
|
|
|
|
EPT
