The Longest Increasing Subsequence

[@StrawEgg]

It's incredible how we've developed math able to distill the "uniform" parts of randomness into more deterministic objects at larger scales! I think this is pretty much the overall strategy as constructions like the central limit theorem - and just as beautiful. Hadn't heard of the Tracy-Widom distribution though. Great video!

[@diffusegd]

I'd like to give an additional note regarding the end of the video: In problems with a lot of independence, the normal distribution arises quite often (central limit theorem, for example) This type of independence is intimately related to the commutativity of random variables: XY is distributed the same as YX If we instead consider random variables that aren't commutative anymore (For example, random matrices), we get out an entirely different theory of probability, known as *Free Probability Theory*. This theory was only developed very recently in mathematics (1970-80) The notion of independence we get is no longer the original E(X)E(Y) = E(XY), but a (more complicated) "Free Independence" which works for non commutative random variables. It turns out, under this new theory: - a central limit theorm exists, which is the SEMICIRCULAR DISTRIBUTION - Random matrices like Wigner Ensembles have limiting distribution equal to the semicircle Id recommend reading Chapter 1-2 of "Free probability and Random Matrices" by Mingo and Speicher to look at the relation between Commutative/Non commutative and Normal/Semicircular distributions

[@jean-baptistelemen3681]

"High level" science vulgarisation is one of the most beautiful things the internet era will have brought to mankind. This channel is yet another example out of many. Thanks a lot!

[@codescent9569]

What are your other favourite examples?

[@Kualinar]

This reminds me of my second problem in my first programming class : Find the longest and shortest, increasing and decreasing subsequences of uniform difference in a list of numbers. That list was not a permutation of an ordered list. Several numbers appeared multiple times. That was to be programmed in FORTRAN, submitted to a remote mainframe as batch work.

[@amirnuriev9092]

basically ancient competitive programming

[@minerscale]

I cannot believe there is a book called "The Surprising Mathematics of Longest Increasing Subsequences"

[@SpectralCollective]

Surprising, right?

[@johnchessant3012]

9:44 Also interesting here is the fact that these probabilities sum to 1 gives the neat result that the sum of the squares of the different numbers of Young tableaux equals n!. I had seen this before using representation theory of symmetric groups, but this is an amazing new perspective on it.

[@sidneyali]

Great video. Regarding your comment at the end, about how in math you can go from not knowing anything about a particular field, to understanding the statement of an active research problem in about thirty minutes is really spot on and I couldn't agree more. One of my professors researches polynomial automorphisms. He explained to me, after my first year of college, what the field is about and the Jacobian conjecture in thirty to fourty minutes.. That's really how quick it can be to reach the edge of human knowledge.

[@Alceste_]

I really liked the incremental introduction that lead to the frame at 1:30.

[@JediJess1]

Did not expect the Gaussian curve to show up at the end. I've kinda grown on it and the math of statistics in recent years. This was a fascinating video. For something that seemed ludicrous to prove, like x×2^(1/2), you did a great job showing an intuitive proof for it. Very nice video!

[@larspos8264]

Just like last year, one of the better some3 submissions

[@AB-gf4ue]

very good video, well done. i loved your percolation video and watched it last night to sleep. thank you. so good to see you make more maths videos

[@kayleighlehrman9566]

I cant remember who the quote is attributed to but in a math book i read a few years ago there was a great heuristic about rigorous mathematical proofs: "you should never try to prove something whose truth is not almost obvious"

[@pdf5774]

Very well done video! Thanks for pushing the frontier of my knowledge.

[@tanchienhao]

Another masterpiece!

[@pablodelafuente4810]

Beautiful work

[@benmaghsoodi2067]

4:24 why is the area of the box n, and not n^2?

[@SamuelLiJ]

At 11:45, shouldn't the Limit Shape Theorem state that the probability goes to 1?

[@SpectralCollective]

Yes, it should, good catch!

[@malcolm7436]

When you reframe the problem as random points in a box, surely there's an issue with some points possibly being collinear. Perhaps it has probability zero so does not matter?

[@pdf5774]

Any co-linearity occurs in a lower dimensional (affine) manifold of the full space, therefore probability zero, so the (finite) union of all possible co-linearities is still probability zero.

[@kch8919]

One minute and my brain already hurts

[@drdca8263]

Eyy, I heard a little about the Tracey-Widom distribution when I was (misguidedly) trying to come up with a notion of a uniform distribution on the set of permutations over the natural numbers. Cool to see it again. (I have since concluded that there probably isn’t such a distribution, because I’m pretty sure that that group isn’t compact under the topology on it one gets from viewing it as a limit of permutation groups. So, the thing I was attempting presumably doesn’t work. But I do still wonder if, in the same way that there is no uniform probability distribution over the reals, the Gaussian distributions of increasing stddev are sorta kinda what one might naturally use instead as a natural prior over the reals, whether there might be a similarly natural family of distributions over permutations of the set of natural numbers?)

[@SpectralCollective]

I'm trying to think of one, but so far I've got nothing!

[@jake5331]

How is the group of permutations of N a limit of permutation groups?

[@drdca8263]

@@jake5331 you can embed S_n in S_{n+1} (so, e.g. {(1,3),(2,1),(3,2)} would get sent to {(1,3),(2,1),(3,2),(4,4)} ) And, with this directed system of groups and group homomorphisms, one can take the direct limit. (So, take the union over all the groups, and then if one of the homomorphisms sends x to y, identify x and y. This works as a group because, for any two elements from different groups in the directed system, find a group where there is a homomorphism in the system from each of the two groups to that one, and then take the image of the two elements there, and then apply the group operation there. This probably wasn’t a very good explanation of direct limits. Wikipedia has a better one.)

[@OMGYavani]

Permutarions of natural numbers are exactly like reals in cardinality so there is no wonder that there isnt uniform distribution for them

[@drdca8263]

@@OMGYavani That doesn’t necessarily prevent it. The group U(1) also has cardinality of the reals (it is isomorphic to R/Z), and, as a compact group, it has a normalized Haar measure. The issue isn’t one of cardinality, but is instead (I think) for the same reason that the group of integers under addition has no uniform probability distribution : because it isn’t compact.

[@meiliyinhua7486]

I'd love to see a vid on the connection between the table structure and the representation of the symmetric group briefly mentioned

[@astriiix]

i love your videos so much, you are able to implement a clear explanation with amazing visuals that catch the eye, and thereby the attention. Are you planning to cover different subjects other than graph theory related stuff? I'd love to see what you are able to do with number theory or abstract algebra, but again keep up the good work!

[@SpectralCollective]

Thank you! I (Vilas) am currently a PhD student studying probability theory, so it’s unlikely that I’ll make a long video about anything too distant from my research. Not impossible, but don’t get your hopes up!

[@astriiix]

@@SpectralCollective Oh thats cool! I'll take this as motivation to maybe make something myself! I'm still studying in high school but I managed to teach myself a lot of algebra and number theory, and the more incomprehensible a definition or a theorem is, the more I want to go down the rabbithole. Since on youtube I can't always find everything I wanna know, I'm looking forward to produce something by myself, and you're videos are just the perfect example of what I would like to do! You really deserve a lil more attention in the educational maths community.

[@fibbooo1123]

Fantastic video!

[@NoNameAtAll2]

11:41 so it isn't square with a quater circle cut out?

[@SpectralCollective]

That’s right, the curve is not a quarter circle

[@LeonhardEulerShades]

Very interesting video! I have a couple of questions if you don't mind. At the end, the crystallization animation has white diagonal lines. Is this a visual artifact? Should the Robinson-Schensted algorithm feel intuitive (could I have come up with it)? I was surprised that Young tableaux/diagrams were the key to that proof. Interestingly enough, Young diagrams are absolutely necessary to understand the representation theory of the symmetric group. Perhaps permutations and Young diagrams have a deeper connection than I thought.

[@SpectralCollective]

The "crystal" simulation is a model called ballistic deposition, where blocks are raining from the sky in columns (like tetris) but the blocks will also stick to each other on the side. Every white pixel is a hole in the crystal caused by some blocks not falling all the way to the bottom of their column. The lines that you see are actually emergent behavior, and I can't really explain why these "canyons" form. Here's a cool video about this model: kzbin.info/www/bejne/kGe7gWakYridn9k I wouldn't say you should be able to come up with the Robinson-Schensted algorithm by yourself necessarily, it's not that obvious. But it is only one step away from something called "patience sorting" which may be easier to come up with.

[@vaclavrozhon7776]

Great video! Is there some simple heuristic/intuition why the constant is equal to 2? If you approximate the process by a uniform grid of points, it looks like the constant is in that ballpark but I am wondering if there is a more precise heuristic argument one can make.

[@SpectralCollective]

The heuristic in the video explains why the constant is equal to 2: the maximal length up-right path through a box of area n has length 2*sqrt(n)

[@adityakhanna113]

It's always lovely seeing RSK and young tableaux in the wild! Haven't watched the video yet but am sure it would be wonderful. How long did it take you to make the video?

[@SpectralCollective]

This one took about 3 weeks of consistent work to make. I had been thinking about the script and coming up with ideas for animations for a few months before that though.

[@vivianobernosterer9307]

Awesome video!

[@Tititototo]

what are the possible applications of that subject, please ?

[@potato5848]

This is the best video I've seen this month. Been trying to find a book on mathematics behind algorithms. Like proofs and such things. Can you recommend any similar books?

[@BorisNVM]

this is so cool

[@TymexComputing]

OMG - there is a whole book about it ???

[@SpectralCollective]

Yes there is! And it is very detailed and well-written…

[@samuelfamilusi7899]

your video quality is amazing, also what font is that?

[@SpectralCollective]

It’s just the standard LaTeX font

[@MichaelDarrow-tr1mn]

can you make a video of just the zooming out of a box

[@SpectralCollective]

that animation takes quite a lot of computer time to make, so probably not in the near future, but maybe eventually!

[@diffusegd]

I'm currently researching Random matrix theory (although a different area) and I love this video! I knew about the longest increasing subsequence problem before and its relation to TW, but I didnt know how that connection was made. However, Young Tableaux arise in relation to non-crossing partitions of sets, which again are related to GUEs. I'm wondering, is the Young Diagrams limit shape being semicircular related to the Semicircular distribution?

[@SpectralCollective]

Actually, the curved portion of the limit shape is not quite a segment of a circle, so I don’t think this is related to the semicircle law at all. The proof of the limit shape theorem works by carefully analyzing the plancherel distribution and proving a large deviation type result about the shape of the (finite) Young diagrams

[@MatteoMucciconi]

The semicircle law and the limit shape of a random Young diagram are related in the sense that they are found as minimizers of closely related functionals. In the case of GUE random matrices the semicircle optimizes a quadratic form f -> + , while in the case of random Young diagram, the limit shape minimizes another quadratic form + . The difference between the quadratic forms is only in the linear part. If one studies the edge of the limit shapes related such quadratic forms (including potentials more general than V or W) one is guaranteed to obtain the Tracy-Widom distribution.

[@dsagman]

fantastic animation. how did you do it? also very clear and well explained.

[@SpectralCollective]

Almost all of the animations were made using Manim, which is a python library for mathematical animation

[@NotKyleChicago]

Why doesn't the "65" in "1276589" break the subsequence to be a length of three?

[@SpectralCollective]

What do you mean?

[@NotKyleChicago]

@SpectralCollective 6 is less than 7, so the increasing subsequence is broken at that point. The longest increasing subsequence in "1276589" is "127", which is a length of three. The video seemed to include the "89" after "65" to give a length of five. Perhaps I don't know the definition of "subsequence " that is being used.

[@SpectralCollective]

Oh I see, yes in this video a subsequence doesn’t have to be contiguous, there can be gaps

[@alex_zetsu]

You didn't need to go the extra mile and explain the fluctuations. Just knowing the asymptotic behavior is usually good enough for these random processes.

[@SpectralCollective]

I think it depends on what you're trying to do with it. Personally, I find the fluctuations interesting as well!

[@rushoffman965]

Babe wakeup

[@lgooch]

Before watching the video let me guess what this video is about by the title: my guess is the Erdos-Szekeres Theorem

[@SpectralCollective]

not exactly, but that theorem is quite related!

[@lgooch]

@@SpectralCollective yea but this topic is also very interesting, nice video!

[@konee0]

First!

[@korigamik]

I liked your visualisations. Can you share your code for this video? I assume you are using manim, a git repository would be ideal. 😊