Increasing and decreasing subsequences and their variants
Formal Metadata
Title 
Increasing and decreasing subsequences and their variants

Title of Series  
Number of Parts 
33

Author 

License 
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. 
Identifiers 

Publisher 

Release Date 
2006

Language 
English

Content Metadata
Subject Area  
Abstract 
We survey the theory of increasing and decreasing subsequences of permutations. Enumeration problems in this area are closely related to the RSK algorithm. The asymptotic behavior of the expected value of the length is(w) of the longest increasing subsequence of a permutation w of 1, 2,...,n was obtained by VershikKerov and (almost) by LoganShepp. The entire limiting distribution of is(w) was then determined by Baik, Deift, and Johansson. These techniques can be applied to other classes of permutations, such as involutions, and are related to the distribution of eigenvalues of elements of the classical groups. A number of generalizations and variations of increasing/decreasing subsequences are discussed, including the theory of pattern avoidance, unimodal and alternating subsequences, and crossings and nestings of matchings and set partitions.

Keywords  increasing subsequence decreasing subsequence Young tableau RSK algorithm, TracyWidom distribution GUE model pattern avoidance unimodal subsequence alternating subsequence matching oscillating tableau 
Related Material
00:00
Geometry
4 (number)
Twin prime
Enumerated type
Angle trisection
Natural number
Network topology
Right angle
Student's ttest
Sequence
Combinatorics
Numerical analysis
02:47
Length
State of matter
Multiplication sign
Water vapor
Insertion loss
Dimensional analysis
Permutation
Explosion
Group representation
Mathematics
Conjugacy class
Square number
Cuboid
Diagram
Partition (number theory)
Physical system
Process (computing)
Maxima and minima
Sequence
Connected space
Order (biology)
Moving average
Right angle
Factorization
Link (knot theory)
Real number
Student's ttest
Rule of inference
Theory
4 (number)
Frequency
Natural number
Term (mathematics)
Wellformed formula
Integer
Theorem
Set theory
Standard deviation
Matching (graph theory)
Weight
Model theory
Physical law
Total S.A.
Line (geometry)
Cartesian coordinate system
Rectangle
Numerical analysis
Planar graph
Doubling the cube
Vertex (graph theory)
Maß <Mathematik>
18:33
Point (geometry)
Supremum
Divisor
Length
Equaliser (mathematics)
1 (number)
Function (mathematics)
Parameter (computer programming)
Mereology
Event horizon
Permutation
Element (mathematics)
Expected value
4 (number)
Goodness of fit
Wellformed formula
Term (mathematics)
Square number
Nichtlineares Gleichungssystem
Determinant
Analytic continuation
Area
Distribution (mathematics)
Standard deviation
Logarithm
Prisoner's dilemma
Expression
Curve
Infinity
Maxima and minima
Mortality rate
Limit (category theory)
Numerical analysis
Substitute good
Degree (graph theory)
Proof theory
Elementary arithmetic
Computer animation
Ergodentheorie
Order (biology)
Vertex (graph theory)
Gleichverteilung
Figurate number
Table (information)
Arithmetic progression
Resultant
Directed graph
27:05
Logical constant
Randomization
Presentation of a group
Length
Interior (topology)
Multiplication sign
Water vapor
Function (mathematics)
Parameter (computer programming)
Fast Fourier transform
Junction (traffic)
Permutation
Expected value
Mathematics
Manysorted logic
Analogy
Matrix (mathematics)
Square number
Diagram
Recursion
Fiber (mathematics)
Position operator
Descriptive statistics
Partition (number theory)
Social class
Physical system
Infinity
Price index
Sequence
Connected space
Proof theory
Category of being
Symmetry (physics)
Order (biology)
Right angle
Cycle (graph theory)
Mathematician
Resultant
Point (geometry)
Probability distribution
Statistics
Free group
Beat (acoustics)
Parity (mathematics)
Real number
Random matrix
Event horizon
Rule of inference
Theory
Product (business)
Term (mathematics)
Natural number
Modulform
Differential equation
Theorem
Nichtlineares Gleichungssystem
Associative property
Symmetric matrix
Standard deviation
Distribution (mathematics)
Matching (graph theory)
Surface
Polygon
Model theory
Mathematical analysis
Counting
Division (mathematics)
Total S.A.
Evolute
Equivalence relation
Numerical analysis
Vertex (graph theory)
Object (grammar)
Coefficient
Pressure
Table (information)
Quantum gravity
44:11
Point (geometry)
Statistics
Dynamical system
Group action
Length
Correspondence (mathematics)
Multiplication sign
Insertion loss
Mass
Function (mathematics)
Theory
Dimensional analysis
Permutation
Power (physics)
Prime ideal
Group representation
Conjugacy class
Average
Analogy
Gastropod shell
Square number
Theorem
Algebra
Symmetric matrix
Associative property
Representation theory
Partition (number theory)
Pairwise comparison
Standard deviation
Distribution (mathematics)
Matching (graph theory)
Process (computing)
Infinity
Staff (military)
Line (geometry)
Sequence
Symmetric group
Numerical analysis
Proof theory
Film editing
Enumerated type
Order (biology)
Right angle
Figurate number
Metric system
Asymptotic analysis
52:48
Point (geometry)
Randomization
Real number
Function (mathematics)
Mereology
Generating function
Frequency
Sign (mathematics)
Lattice (group)
Natural number
Different (Kate Ryan album)
Term (mathematics)
Integer
Determinant
Partition (number theory)
Distribution (mathematics)
Standard deviation
Dependent and independent variables
Matching (graph theory)
Reflection (mathematics)
Limit (category theory)
Numerical analysis
Order (biology)
Resultant
Maß <Mathematik>
57:33
Principal ideal
Distribution (mathematics)
Finitismus
Trigonometry
Divisor
Length
Characteristic polynomial
Line (geometry)
Linear algebra
Rectangle
Numerical analysis
Theory
Permutation
Fraction (mathematics)
Degree (graph theory)
Different (Kate Ryan album)
Matrix (mathematics)
Square number
Nichtlineares Gleichungssystem
Adjacency matrix
Extension (kinesiology)
Partition (number theory)
Rational function
Set theory
1:00:06
Degree (graph theory)
Fraction (mathematics)
Multiplication
Graph (mathematics)
Divisor
Matrix (mathematics)
Modulform
Adjacency matrix
Rectangle
00:03
OK Good morning He's a great danger Introduced charred saying me from a my team Recharge has been a leader in the story During the last 30 years found deal Profound and fruitful lean between combinatory X . Their yards off at a much much of his wary Hayes who in 1 way or another wheezing you will bird tapes most teams in the area of combinatory But it means of free charred died enumeration Probably Waterways We Iger grant geometry Recharge has been able to produce federal ended deep techniques from Duke 55 to grant a discrete mathematics he's breakthrough Proved off they opera bound from Cape chair 4th years The date twin Utrecht fury or scoring the crowd complex's 18 trisect shade of combinatory commuted to you fight Retired member of the U.S. National Academy of Sciences and received Maney words including support your price he writes in short Right He is so provides for Ph.D. that's really Michael the inning short piece number will keep growing may be thing during these picture students include menial very based young researchers Badger bright communicatory into work I'd 1st Make tree charred more things 20 years ago They know they decide being In outstanding with at Shane easy to Prairieburg speaker where is I'm sure we always Tito The title of his nature Please We'll crystal in decreasing salve sequence Rich or walk for a free told thank you note Maybe that's a little more
02:48
Better would carry cell I will start out by defining what I mean by increasing indicating subsequent but suppose we have a permutation of the numbers from 1 day and nite illustrated here for a Nichols lined write my permutations doesn't just sequence The numbers from 1 to and And an increasing subsequent shown here on the top of the red It is a subsequent developments that appears in increasing order 3 for Set and similarly 4 2 0 0 would be a decrease in subsequent and mainly interested in in this talk is the length of the longest increasing subsequent a number of terms here at this Red Sea clients is 1 of the longest and 1 is 1 has for this as 1 of them So I S W denial the length of the longest increasing subsequent Incirlik DSW As a line of Warner's decreasing subsequent For I'm history 3 Well before beginning mathematics I should point out there are real world applications of increasing sequences and I will mention His application to point Borden which was also discussed yesterday person died in his planners tall so will make it very naive models offer for all passengers boarding we have 6 seats and we have our 6 passengers and just come in random order and they have assigned seats and the algorithm they will follow adjust What would just assume that they take 1 time unit to be seated After they arrived at their seats for the 1st time True Bobo Because there's no obstructions won his seat 5 3 6 at the weight behind 2 and 4 behind want before they can move on so too and once it down and the remaining passengers will continue as you can see a kind of a defect already in this model must assume the passengers are very thin Wanting to have sit down 3 6 4 5 would spark For its possible 3 in 5 sit down in the last for 6 well it's very easy to say that the total waiting time you're a number of steps in this algorithm is the length of a wondrous increasing subsequent But this is a very simple model but box and his collaborators have come up with much More sophisticated models in which increasing such sequences and a lot of the theory I will discuss planar important role and the 2 of them make conclusions are the following the usual system that airlines use for boarding is backed front is really not much better than random in the amount of time it takes to board a better system is the 1st to the window seats and the center seats and I'll see him I think some airlines have actually moved to this system the peso Now starting with some of the mathematics of increasing decreasing sequences no 1 aspect of this subject that makes it so interesting is that these subsequent loser connected unexpectedly with many other topics in the first one I want to talk about Yummy tableau so Most start the definition of a partition of an integer and noted this way That would be a weekly decreasing subsequent nonnegative integers that's something and we can represent this partitioned by this diagram of in their land I swear Sydney I throw left justify this is a diagram 4 4 3 1 and also Needing hot concept of the conjugate partition the 1 you get from the diagram of land by transpose changing roast columns so the kind to get 4 4 3 1 4 3 3 true Standard young Cabello or s slightly show While some petitioners Illustrated here should make a definition cleric You insert the numbers from 1 day and into the squares of a diagram So that every roll columns Increase So Land will note the number Standard John Cabell shit planned so person for the shit 3 to find standard on So After 3 to a spotlight Now it's quite surprising that there is actually a very simple Explicit formula for this number at slammed famous Frank Robinson brawl thank formula bothered to stay here but 1 nite Monday that Flanders come up and later formulas you should realize that they can be replaced by a very simple explicit formula Nor does make a note The subject of increasing and decreasing sequences has a lot of connections representation and don't have time to go into any details But it can be seen by the fact that have slammed the patrols Soon tying in with increasing subsequent these numbers A plan by the dimensions of irreducible Representations of the match but I be singing anything more about now we have to connect the permutations with standard young double in the way this is done famous RSK algorithm which gives a bite Jackson from permutations of 1 up and In Paris standard young cabbala saying which some partition plan and take my permutation had produced 2 standard don't tableau from I will call wish whatever they Shape land that is at least 2 standard tableau the shape of the permutations of you explain where the letters are come from our is still bear the Beaureguard Robinson who 1st defined this They perform Craig there who later changed his name to
10:44
We made a much more explicit and also approve this key Connection with increasing subsequent says Katie is Donald who developed the steely further not going to describe this RSA algorithm With an example and is is not quite a standard way of describing algorithm but is most convenient I'm going to do for purposes of generalization law while so what do it Prudishness 4 1 3 2 2 and . worldwide Here and for her right permutations under the 1st and thought 4 1 3 2 in the next and thoughts are just numbers From 1 day and decreasing water I join or from 2 Were 2 vertices with the same number So I had the match in all of these 2 and and know what it is I goal course scan these numbers from left to right When I encounter number for the 1st time which will be just where firsthalf here inserted Until a tableau when I encounter for the 2nd time I deleted now defined the details of the process which is a key step in our state order the others some simple rule for how you insert number into a tableau keeping the rows and columns increasing our 1st insert for And I'm sure want going to get this done I answered 3 yelled this and then an answer to according to the insertion ruled that this tableau tonight to lead 4 3 2 1 so I'm back at and set and I read off my Parra standard young Cabello as follows a right in the middle We're going to have a standard on tableau with ends squares and that will be 1 2 3 4 4 Q I look at the water in which his middle Taboao has been built talk My 1st edit entries This where here But won the 2nd square that I edit entry this 4th year bridge to them Here are the 3rd square But his preferred so This 2nd double reports a quarter in which entries and build an end this way I get a pair of standard on tableau associated with permutations and it's not hard to see that this is a by Jack any pair standard Temple sanctions need recover from this is 1 of the fundamental algorithms of algebraic come tore the could argue if I had a couple more hours 1 of the most interesting of all The medical College what does this have to do with Increasing and decreasing some sequences Rover Dear emotions that Protection W. corresponds to the spare key to the shape of a purist petition my under the length of the longest increasing subsequent W. is just the longest role length of land that is a way for the 1st draw And the length of the 1 decreasing subsequent is a line in the 1st column that is as example from the previous light 4 1 3 2 wanted this pair the length of the 1st rose to 12 of the 1st row Of the like 1 is increasing subsequent No it's not so easy to actually recovered from these And increasing subsequent of going to De Soto Not such a simple this not just at this 1st rose necessarily such an interesting subject to me this simple example more that answer a The link to the 1st column 3 so the longest decreasing subsidy funds W has like well I want immediate corollary to this by ejection and that's theorem is the 1st year ever approved about increasing and decreasing such sequences this thing this year sectors theorem 1 of the 1st year of the extreme common toward supposed W is Permutation of She due plus 1 and there is an increase subsequent greater than 80 or decreasing subsequent of 1 greater than she thought to think about What happens you apply artists The Lambda While If the contrary or through here No 1 is increasing subsequent lesser the Chadian DSW last with 2 children by Shen said They're wrong Member 1 the 1st role would be However most peaceful players The 1st column and was choose where it so the whole show It didn't keep bite you rectangle ever most key time students players so that would be the number of tourist permutations so that's breed Simple from artist never also 10 day something about extreme situations where we do have an increasing subsequent but said it was generalities Westlake kill if we look at the number of permutations in S P 2 whose longest increasing such occurrences like subsequent assigned she so Mr. pitcher plus 1 wouldn't be any budget year sectors from the same best Possible in that do exist such W. right down exact number because the only shaky with kids use players 1st Roebling they 1st column on to his P by Hugh Squire sulfur RSK would give the pair standard young The rectangular He by times killed a number of pairs of such things don't have gas lamp square land that shape Before going formula The Who do this as I said gives an explicit formula Were This number in Applied to this situation you get Very mysterious looking for what he didn't notice period where the number of these permutations is extreme permutation back don't or simple reason why perfect square We are going through this Hardest hit was a kind of aside mentioned that she would result Dana on what Permutations looks like typically that I see this as an Ah yes DSW Shoe hands of protection 1 star order status to Italy if you think you're very patient W and look at a permutation matrix of W which we think of us
18:47
Lying the court playing vertices quarters minus 1 there and we look at the location of the ones in this permutation matrix There's an example for Calls for We have a permutation 16 elements wanders increasing subsequent as foreign bonds decrease subsequent I've written until the squares were the ones appears to be a small example looks like it might be pulling out Kirk was much too small too Really going on But our Ahmad showed indeed this is the case in this curry was 4th degree for and assistant draft the should desist from amusing care about a typical extreme all permutations and people's wrote what can we do next week and asked for for the distribution of the length of wanders increasing subsequent Marie Ramirez problem So The simplest question is whether the expectations are like me and be the expectations of the length of longest increasing subsequent that letters and this With respect the uniform distribution on the symmetric girl So Now By DeForest a algorithm if we apply RSK Permutations W Will get a certain sheds light on the number of Pairs of standard young tableau that they have slammed square and they planned the 1 would be there The length of the 1st right With the length of along increasing subsequent W And so The expectation of the like the ones in prisons Suffolk and just be disarmed that will not as a firstperson ask about this question but Torre said about the distribution of ice But in in general and in particular but the rate of broke The expectation that the 1st significant progress was made by Hammersley using sup added ergodic theory he showed 1972 The rate of growth consequences for revenge the limit is Anderson from India You can score would have and exists as some fine I constant which proved was between pi over to him conjectures that true and numerical evidence obtained by longtime collaborators supported this conjecture well this was actually approved Wisconsin is indeed too Independently In 1977 by Logan and chat and by year Girshick Carol exit Logan shot only through the more difficult equality Is greater than or equal to 2 You're Shaquille Ichiro found clever argument using RSK especially the idea that Use this Expression in terms of planned the number of standard young tableau should plan the number of turns in this song is very small Compared to the size of the number of petitions Obama small is is bigger than and factorial is much bigger than the purchase so E. event It don't approximately whenever factor of the largest Turk and being very precise here But this suggest that we want to find a lamb for which have Landed is maximized and figure out what its longest part the largest part you can take this maxim discrete maximization problem here And by using the someplace When an goes infinity you get a continuous problem Texas Variations but we I want to do is find this curve worry normalized area the curved ones so that we minimize logarithm of integrating Over under the curve At every point Distant West Mr. Ozal but the Problem reduced to and this was what Solved by looking chapter there should care or not so easy to guess this Curtis Turned back Pretty good eyesight to see that this is the equation given parametric played by But these equations as White to cosign data And wants to reply signed of mind status signed retreat at 0 upon the fact that it should be exit taxis to Merely proves this constant Is greater than or equal to 2 and I mentioned that The year should Caro Found this very nice Proof using to very elementary argument last year because of us solve the problem of the expectation and the next step is to try to get even better information but the actual distribution of the length of the longest increasing subsequent what to do that you need some kind of formula Distribution in case and let you caravan number Permutations such that The longest increasing such secrets of W like west put out And here because I'm going to be looking for relating total Trinity what was does it mean to be clear so we need some kind of Expression for this In order to Do it analytically tribes see what happens The committee now the 1st such result again do that Hammersley 72 It was at tour van The number of permutations with no Increasing substitute can't of 1 3 is travel and so this is 1 of the many Car motorial interpretations of cattle in the 1st minute another life Collecting these interpretations and But she now I have over 140 of them and there's way each rougher Higher values It's not so simple but Ira Gasol was the 1st of 4 over 1998 a generating function for these numbers fixed can select the look of this generating function some of the UK access to an Turns out In fact square The nominative the result intended to be just Take a bite determinant of church kind of that doesn't look so promising 1st the complicated actually extract good Asymptotic information from so 1 tables True death Dubai to determine the source of a determined is equal to expand that out And that's easy to see That indeed this is a generating function for Thailand numbers recovering the result of merciless now in arresting result the corollary to Gesell formula is that although there's no simple formula for UK event in general for richer each day
27:28
You can be computed Quickly It's so what's known as a P recursive functions fix It satisfies linear Returned with Colin no middle coefficients and years but you for a new fiber plant from the likes of course aren't you figure out what occurrences are The jury quick Column time to compute the value of 3rd there some interesting conjectures about the exact form of injured curses due to bearish of for her Take so Now that we have a Sort The These numbers UK event we can try to understand references and Infiniti and this is the pioneering work of Dies Council day from the limiting distribution properly scaled While the length of the longest increase subsequent misses also discussed just Perceived by Mrs. The flying of the finest Distribution hinted socalled of a true functions Look at this nonlinear differential equations tailormade to equations and He wanted the journey class The pressure equations that were classified by Tampa Bay and with certain Meshoppen dishes I'm Such its asymptotic say what happens if you this standard solution if you get rid of the nonlinear termed Harry function so I will need this Function to define this Tracy rhythm distribution before I do that on presents a little bit about The mathematician 4 I because he had a very interesting wife who was born in Paris in 1863 and who was an excellent mathematicians from shown by winning the concrete PC holds the key to 1890 in 1908 she was the 1st person in history of passenger in an airplane and set White duration record 17 minutes prick 2 years Silas Willie held a position of equivalent of being prime minister for him and to and the story he died 1933 we are going back to the mathematics will defined in terms of this panel of a function of X The probability distributions Tracy would on distribution FFT to is this book is completely over the air few have seen for why would anybody Think of such a probability distribution But it turned out this is exactly video distribution that describes Limiting behavior of a length of longest increase in subsequent would introduce scalar properly subtract being witches as prices were would've and abide by the standard deviation which turns out of order and the 1 Sex and the probability that this quantity Roster Any real number In goes infinity You have to proceed with distribution so this was a spectacular breakthrough in this subject and various nice corollary can be drawn about these distribution of increasing such sequences in particular No The length of along with that actually should be easy This to be the expectations of the E Expected length along the increasing subsequent remember whose asymptotic Twice as were revenge and this result Issued 2nd term constant times and the 1 6 iMac constant is the point in terms of the treaty with distribution about minus point what minus 1 . 7 7 1 So tiny you prove this Huron well Just over did all the comic torso North Florida I'm concerned after just analysis were Seth 99 per cent of the proof and blocked the details there but we could ask says Tracy when distribution which be written here would elevate function here But added Forward defined when big Director Hansen proved the so where did this come from 1st place this is going to give another 1 of these unexpected connections of increasing subsequent other topics as random matrices So Road person died kindness yesterday they dousing unitary ensemble a certain probability distribution on permission matrices and by an matrices New ways to find this way Not so circuit in here the exact Definition the system Marie standard natural Probability distributions matrices and Tracy rhythm showed that the largest I get value of random permission matrix chosen from the GUE model Properly stale normalized this way Also satisfies Tracy with distribution so here we have seemed like 2 completely different ways in which this division has arisen And in terms of increasing subsequent as their distribution and I can values the largest item value permission matrix we asked this connection just a coincidence Wurzer some connection Nanda The connection is was actually given by 100 Congo after 4 days of fuels metal here The what was about what he did Namely how you look at the fury of rant on apologies surfaces and the reason that are be true interpretations 2 places where the Tracy with distribution appears has to do with the fact that there are 2 ways and surface can be described as became glow Polygons along the the edges and build up the surface in that way and there This way In this theory of quantum gravity that said about this way the lamp surfaces shown be connected random matrices we can also think of a surface as a ramify covering others fear and then they come torch Permutations comes in 2 The description of the surface so extremely brief indication of why these 2 subjects related but days That finishes
35:39
Highlights The subject of increasing and decreasing subsequent permutations that we can think about generalizations and analyze finance many of these are discussed in my paper for this conference now I just . 1 years which is a joint work with these 4 Chinese coauthors Bill Chen even was Messina do and Katherine this is wrong will replace permutations With another commenter object matter so complete matching get to end points and will join them by hand arts no to courts with a common vertex here is complete matching she wants a way of providing joined points Walks To be teach sure them how to 0 properties matches that of matters that would be interested in a really pairs of edges of the match and crossings like this to adjust cross their interiors The last thing on 1 edge This contained MCI's now the total number of matching on the rocket to and which which means the numbers from 1 of the 2 It's easy to see that it too and minus 1 semi factorial the product of all the odd numbers from 1 to 2 and have another interpretation cavalier numbers as a number of matches on these 2 endpoints with no crossing and also number of matching with no nesting surprisingly both times Now I will give a sketch of proof of this theorem body Doing by Jackson between these matches if you wanna count those with no crossing and those with no mess things in something that's well known to be countered by Calin numbers namely socalled ballot sequences sequences of 2 and 1 thousand minus where every parcel Summers nonnative total song is 0 so and wants an end minus 1 3rd them water so that all parcels on While the by Jackson's between Imagine no crossings in these about sequences very simple are Matching without any crossings we just label every lefthanded and point guard by 1 every right in and by minors Very easy to and this gives a by ejection the sequence is about sequence give the by junction between these matching about is kind of surprising in exactly the same rule works for Matches with next of what points labeled by 1 of the right hand and point by minus 1 and still is a by ejection ballots answers to think about that for a few minutes at least 2 were that's true but the saliva debt Account numbers matter what would like to do it will develop a theory for matching analogous increasing and decreasing subsequent Permutations so why should be the correct analog well A 1st attempt would be that we can't think of a matching the very obviously has a fixed point your emotions actually it's a kind of permutations which is labeled a vertices 1 and 2 0 Numbers of being matched They were posed by a fixed point free pollution so just get this permutation W. Young associated with our matching Would shares And cycles of to ever did They Lewis justifying the increasing and decreasing subsequent of a matching the beating of the course funding increasing and decreasing subsequent as of this permutation well The water in this definition is no longer in symmetry between the 2 Statistics for permutations of obvious that increasing subsequent decreasing subsequent as have the same distribution contributors reversed permutations But actually restrict the permutations The bill Fixedpoint free evolution these distributions are actually different So we knew something else and this is what turned out for the most number of mutually crossing edges In the most number of mutually NASCAR So Loser Match N C ground across a number of them will be the largest share So that there's a cake frosting so that there exists Kelly edges any jewel which cancerrelated nesting number Of the match in any event will be the largest Such that into this picture but actually turns out that the last number is 1 half of the length of the longest decreasing subsequent this Permutations here Show The Associated imagines actually decreasing subsequent now is a good 1 But we need start increasing subsequently replaced crossed low It's certainly not clear that these are the same distribution like permutations were increasing and decreasing subsequent obviously and distribution money that this is the case of Not only do they have the same distribution but they have a symmetric Joint Distribution Aprilette half of an applied The number of matching 2 endpoints crossing number I and Nestor number jet At end S & J so particular A the number of matches with a during crossing number because a number of nesting aII the number matches the giving nests in check so the case tables z wrote When there were no crossings in domestic life Did previously shown that they were both equal to the cattle and number in here we have this generalization but Unlike the case for permutations were increasing and decreasing subsequent as obviously of the distribution and don't know a simple reason this is true arresting problem on the simple by Judge and matching transforms crossing number into the nest number What we have to do here is go through Are K Type argument pointed him on options that So the main tool now was going to be a generalization of standard young Temple which Oracle oscillating we can't think of a standard John tableau as a way of building up A diagram of a partition 1 square at a time The deal be square in scene and below which the 1 those his 1st than we had another square where the 2 of them in another square with 3 gone before oscillating tableau
44:14
You can add or remove which players and staff so here we have an arson tabloid we always or start empty shell each year in 8 steps and ended up at the shade 3 1 This shed 3 1 9 8 Every step by either lawyer Taken away always maintaining a dynamic partitions but There's no really simple would represent the 1 Kind of tableaux like for standard don't need this whole cuts will now How do oscillating below commented the theory of matches There is our matching an example of a matching red do something on almost completely analogous to what I did The RSK algorithm which we encoded permutation by a special kind of matching his matching his right hand and Contra war and we label the right hand and points of these Park From 1 day and from right to left 1 2 3 right hand and . decreasing order from left to right of left and points of the same label has the right hand and points and there going do the same procedure that we did for scary Wigan scandalous sequence of numbers from left to right the return receipt number for the 1st time that left The aim of the park He inserted by the RSK insertion will I'm received for the 2nd time we deleted search for work Answer to delete 4 Insert 3 sir want 3 lead to We sure going to get a certain sequence Health care We only want to remember their shaky that will be an oscillating tableau each step We knew at once were removed 1 square Is not Slater blow 2 steps in empty shell starts out with him to ship ends up with which I will be the oscillating Babylon Correspondent to this match and it's not hard to see bit tricky because Only a memory not the numbers in side of these shapes here but it turns out just from this knowledge of his shaky recoverable of these numbers in the entire match This man from matching oscillating By Jackson from all the matches on and point to be passing several pointed to an attempt to show wrote doughnuts a quick word about representation theory comes into this picture same way that it came into permutations picture the number of oscillating tableau of linked to an empty shell of them would be the number of matching on 1 of the 2 and is to and minus 1 double factorial That is the dimension of Brouwer algebra centralized algebra refined or some sector groups Operating on tend to power defining representation and this is a wrong algebra representation theory that plays a role rustling fell below the symmetric group Plays for standard tabloid but I won't need thinking more about that made sure we need here Ashens Hero from matching for permutations We apply desire algorithm However read off the length of the longest increasing and decreasing sequences and a completely analogous dirt There was true for matching we have matching him We look at the oscillating tableau them that we get The crossing number of em would be this is just saying the length of the longest Call any of these shade don't know where the necessary she wonders Pierce adding and removing Scrooge at every step of river does appear that will be crossing number Nesting number will be the length of the longest all these ships and the idea of the proof is eternal saying about really except that it would we can reduce it to what Mary RISK algorithm in new the ordinary Xinjiang fell for instance go back to this For example here The length of longest columnist 2 batters sea crossing number indeed too is the most number of Edges that pairwise crossed Incirlik delight along this road wished to that's going to be nest number and indeed these to mass edges and no more row now dividend or given this emotions said Is it a citywide across As number are average symmetric Joint Distribution supposed Elmhurst Crossing number nesting numbers Jed applying this out this Isolating Cabello algorithm here Now we can define a new national to be the 1 that corresponds to the answer will get a conjugate every shit still isolating tableau obviously transposed every should we still are just having removing square steps Why meet this a by the book By that Fuser by ejection will resist you need to prime such a few them trying to this castle blog but clearly If we transpose shape change the length of this column like The longest Rob So why should says theorem crossing number from of Jed be the new length of wanders column hearing last time so this map Prime is involution matching in urging the across nested was kind of complicated Andalusian and don't know us Some politeness Without going through this process Caballo ejection would be interesting to find a more direct injection And we now approved 0 that 2 distributions these 2 statistics have metric Joint Distribution And as open find analog of simple permutation reversals in a changing IS India what is an analogous Ejection interchanges the mast cross But chaser Now we can start thinking about the Christian the enumerating Matching with given nesting crossing number this is the ideologue over gasoline did for this You may have and given this determined Basel functions once we have such an enumeration we can try the figure of the asymptotic Behaviors in the Infiniti so but say that him as a matching crossing number and which can now means that in this
52:48
Associated isolating tableau the longest road lined the along column line is most
52:57
So these limitations broadest Kato nonnegative integers Rugari
53:06
These firms on for each of these petitions in this oscillating blog as capable of my negative integers and so
53:16
We are oscillating Lotus's certain war On into the can take tuples Nonnegative integers number The match 1 of the 2 and crossing number most his number of Linus passive life to and from origin to reorganize response starting out with empty ending up with a machete In this fundamental regional symmetrical but in this region where they cortisone not that we take increasing because we always have the shape of a partition free read the part Reverse order there'll be weekly increasing in each step of plus or minus Unit Lecter because disaster tableau at each step we had her subtract 1 square now this so major points well we be placed Ended the day with nonnegative real numbers cancer in nonnegative real numbers because nonnegative also is just a fundamental chamber For the bio of Type B I prodigy so do a certain kind of Random walk fundamental chamber of a buyout said studied Quite a bit In particular Degraffenreid Maggie Applied this Gesell Zeile Berger reflection principle which is his furry mice generalization famous 180 reflection principle to can't solve this lattice can these ladders and in this fundamental Chang And this is the result turns out to be again it's determined following Bessel functions but the turn of a difference between 2 best visit St. Basil's functions at period before in investors results If ever K and about this with the number Matches and to end is crossing numbers Most case again with generating function now it's just exit to an Roberto and structural Later here It's given by this determinant case by case determined difference of muscle function From on cable's wanted We're going to get 1 by 1 determined this difference and indeed we get to cattle and number Generating function agreeing with the result stated before and as a say this should be compared with desolate result for long increasing subsequent Were we got desk single determined rope Given this The term we can try to do the same kind of As part X big Dyffryn audiences With this 1 Indeed but this was done by bacon Rangel State in terms of crossing numbers of matching they did look at the determinant in another context and We end up with this result alive By financing result these limiting distribution of crossing number of matching endtoend point me now turned out to be a squirrel to and Together they seem deviations order and at once 6 stated this way The probability that C and miners were script and abided by 2 and 160 West key over to visitors Modified Tracy would on distribution after 1 have defined in this way screwed usual
57:35
Distribution in a little extra factor involved Campbell restated Tracy with distribution Hamel equation To a Wrote The last thing I Did mention is that 1 aspect of These matching that doesn't exist in permutations is that we can try to counter that wanted to end with abound on both across the and nesting number for pretensions as should they can remember bound on is increasing subsequent Nearly the length of the longest increasing subsequent but would not be interesting because at 0 4 and sufficiently large by the Irish Zachary notices Really Oakham wasn't a walk inside finite region what finite crashed so it can be done by
58:45
Principal at least Wellknown linear algebra methods this is the graft graphic all standard young tableaus of it Amid war Partition show bit a rectangle Edge between 2 shapes differ by a single square We want account walks empty set to the empty set went ahead because they were just counting oscillating tableau with constrained the line side this rectangle because we have abound on both think crossing number and last Kansas State as as is standard methods will give us A determined by the V 2 rational function denominator is essentially characteristic Parliament adjacency matrix of the crash in arresting about this I guess Like trying to comment on and but Grabner implicitly Found the values of this matrix a theory be trigger trigonometric song and allows us to deduce particularly It's a line certain certain Eldridge extension of rationalist different degree
1:00:13
To conclude that this Summer heat from the factor walk
1:00:18
Well that's factors degree dividing this small factor are some examples of perjury case equals 3
1:00:29
The denominator olfactory has an interesting open problem has It's not yet known When Adjacency matrix of this graph for which rectangles is as major hurdle in now we know I did values Of the Matrix and we also have a form of the multiplicity diving value that it's trivial whether convertible but these multiplicities are also triggered a metropolitan songs and Paso clear when the maybe there's a simpler way patterns problems so I will stop you Thank you