• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 07:59
CEST 13:59
KST 20:59
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
TL.net Map Contest #21: Voting10[ASL20] Ro4 Preview: Descent11Team TLMC #5: Winners Announced!3[ASL20] Ro8 Preview Pt2: Holding On9Maestros of the Game: Live Finals Preview (RO4)5
Community News
Chinese SC2 server to reopen; live all-star event in Hangzhou5Weekly Cups (Oct 13-19): Clem Goes for Four0BSL Team A vs Koreans - Sat-Sun 16:00 CET6Weekly Cups (Oct 6-12): Four star herO85.0.15 Patch Balance Hotfix (2025-10-8)80
StarCraft 2
General
https://www.facebook.com/MachoMachoNetherlands/ Chinese SC2 server to reopen; live all-star event in Hangzhou The New Patch Killed Mech! Team Liquid Map Contest #21 - Presented by Monster Energy herO joins T1
Tourneys
SC2's Safe House 2 - October 18 & 19 INu's Battles #13 - ByuN vs Zoun Tenacious Turtle Tussle Sparkling Tuna Cup - Weekly Open Tournament $1,200 WardiTV October (Oct 21st-31st)
Strategy
Custom Maps
Map Editor closed ?
External Content
Mutation # 496 Endless Infection Mutation # 495 Rest In Peace Mutation # 494 Unstable Environment Mutation # 493 Quick Killers
Brood War
General
Is there anyway to get a private coach? BSL Season 21 OGN to release AI-upscaled StarLeague from Feb 24 BW caster Sayle BW General Discussion
Tourneys
[Megathread] Daily Proleagues [ASL20] Semifinal B SC4ALL $1,500 Open Bracket LAN Azhi's Colosseum - Anonymous Tournament
Strategy
[I] TvZ Strategies and Builds [I] TvP Strategies and Build Roaring Currents ASL final Current Meta
Other Games
General Games
Stormgate/Frost Giant Megathread Path of Exile Nintendo Switch Thread Dawn of War IV ZeroSpace Megathread
Dota 2
Official 'what is Dota anymore' discussion LiquidDota to reintegrate into TL.net
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Deck construction bug Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread SPIRED by.ASL Mafia {211640}
Community
General
Russo-Ukrainian War Thread US Politics Mega-thread The Chess Thread Things Aren’t Peaceful in Palestine Men's Fashion Thread
Fan Clubs
The herO Fan Club!
Media & Entertainment
Series you have seen recently... Anime Discussion Thread [Manga] One Piece Movie Discussion!
Sports
2024 - 2026 Football Thread Formula 1 Discussion MLB/Baseball 2023 NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
SC2 Client Relocalization [Change SC2 Language] Linksys AE2500 USB WIFI keeps disconnecting Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
Certified Crazy
Hildegard
The Heroism of Pepe the Fro…
Peanutsc
Rocket League: Traits, Abili…
TrAiDoS
Customize Sidebar...

Website Feedback

Closed Threads



Active: 1225 users

What is a Baxter Permutation?

Blogs > Geovu
Post a Reply
Geovu
Profile Blog Joined November 2010
Estonia1344 Posts
April 27 2011 01:33 GMT
#1
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.

Oracle
Profile Blog Joined May 2007
Canada411 Posts
Last Edited: 2011-04-27 01:41:59
April 27 2011 01:40 GMT
#2
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)
Redmark
Profile Joined March 2010
Canada2129 Posts
Last Edited: 2011-04-27 01:40:51
April 27 2011 01:40 GMT
#3
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.
d3_crescentia
Profile Blog Joined May 2009
United States4054 Posts
Last Edited: 2011-04-27 01:46:23
April 27 2011 01:42 GMT
#4
You might want to check out his undergrad senior thesis in math here:

http://www.math.hmc.edu/seniorthesis/archives/2008/splott/splott-2008-thesis.pdf
once, not long ago, there was a moon here
Kon-Tiki
Profile Joined February 2011
United States402 Posts
April 27 2011 01:48 GMT
#5
On April 27 2011 10:42 d3_crescentia wrote:
You might want to check out his undergrad senior thesis in math here:

http://www.math.hmc.edu/seniorthesis/archives/2008/splott/splott-2008-thesis.pdf


The best part of this is that the url mashed "S. Plott" to "splott", which is an awesome word.
I am a leaf on the wind. Watch how I soar.
Jayme
Profile Blog Joined February 2009
United States5866 Posts
April 27 2011 01:49 GMT
#6
It's abstract mathematics.

Don't touch that field unless you really love math because it will mind fuck you.
Python is garbage, number 1 advocate of getting rid of it.
munchmunch
Profile Joined October 2010
Canada789 Posts
Last Edited: 2011-04-27 06:10:26
April 27 2011 02:09 GMT
#7
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.
emperorchampion
Profile Blog Joined December 2008
Canada9496 Posts
April 27 2011 02:23 GMT
#8
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
TRUEESPORTS || your days as a respected member of team liquid are over
jodogohoo
Profile Blog Joined March 2008
Canada2533 Posts
April 27 2011 03:16 GMT
#9
Baxter permutation is before killer started to replace Jaedong as the Zerg Ace for Hwaseung Oz.
emperorchampion
Profile Blog Joined December 2008
Canada9496 Posts
April 27 2011 03:53 GMT
#10
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!
TRUEESPORTS || your days as a respected member of team liquid are over
]343[
Profile Blog Joined May 2008
United States10328 Posts
April 27 2011 04:02 GMT
#11
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
Writer
munchmunch
Profile Joined October 2010
Canada789 Posts
April 27 2011 06:09 GMT
#12
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.
AzashaRa
Profile Joined February 2011
United States10 Posts
June 19 2011 18:15 GMT
#13
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
]343[
Profile Blog Joined May 2008
United States10328 Posts
June 19 2011 21:45 GMT
#14
pretending to know math: a useful talent toi have
Writer
Please log in or register to reply.
Live Events Refresh
Wardi Open
11:00
October Qualifier #1
WardiTV730
IndyStarCraft 112
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Lowko242
Rex 106
IndyStarCraft 101
Codebar 7
StarCraft: Brood War
Britney 32288
Calm 7282
Rain 3790
Horang2 1637
Hyuk 1504
Bisu 1104
Flash 827
firebathero 623
Jaedong 621
Soma 385
[ Show more ]
actioN 300
Larva 265
Light 225
Hyun 190
Stork 185
Pusan 164
BeSt 156
sSak 151
EffOrt 151
ZerO 151
Mini 141
Killer 124
PianO 106
Snow 85
Rush 45
ggaemo 40
Liquid`Ret 40
Sea.KH 35
JYJ35
TY 34
soO 29
Sharp 23
Shinee 22
Free 21
sorry 21
Movie 20
Bale 17
Yoon 14
Sacsri 14
Shine 13
HiyA 9
Noble 9
Hm[arnc] 5
Icarus 4
Mong 1
Dota 2
XaKoH 404
XcaliburYe215
Fuzer 129
Counter-Strike
shoxiejesuss887
zeus653
oskar71
Other Games
summit1g7640
singsing1820
olofmeister1239
B2W.Neo646
Liquid`LucifroN93
Mew2King59
Trikslyr29
ZerO(Twitch)10
Organizations
Counter-Strike
PGL422
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 14 non-featured ]
StarCraft 2
• LUISG 30
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• iopq 3
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• WagamamaTV452
League of Legends
• Jankos3389
Upcoming Events
Wardi Open
2h 32m
PiGosaur Monday
12h 2m
Replay Cast
22h 2m
Tenacious Turtle Tussle
1d 11h
The PondCast
1d 22h
OSC
2 days
WardiTV Invitational
2 days
Online Event
3 days
RSL Revival
3 days
RSL Revival
3 days
[ Show More ]
WardiTV Invitational
3 days
Afreeca Starleague
4 days
Snow vs Soma
Sparkling Tuna Cup
4 days
WardiTV Invitational
5 days
CrankTV Team League
5 days
RSL Revival
5 days
Wardi Open
6 days
CrankTV Team League
6 days
Replay Cast
6 days
Liquipedia Results

Completed

Acropolis #4 - TS2
WardiTV TLMC #15
HCC Europe

Ongoing

BSL 21 Points
ASL Season 20
CSL 2025 AUTUMN (S18)
C-Race Season 1
IPSL Winter 2025-26
EC S1
Thunderpick World Champ.
CS Asia Championships 2025
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual

Upcoming

SC4ALL: Brood War
BSL Season 21
BSL 21 Team A
BSL 21 Non-Korean Championship
RSL Offline Finals
RSL Revival: Season 3
Stellar Fest
SC4ALL: StarCraft II
CranK Gathers Season 2: SC II Pro Teams
eXTREMESLAND 2025
ESL Impact League Season 8
SL Budapest Major 2025
BLAST Rivals Fall 2025
IEM Chengdu 2025
PGL Masters Bucharest 2025
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.