The Hidden Law of Crossing Paths
Audience: high-schoolundergraduategraduate
Tags: combinatoricslinear-algebradiscrete-math
This video walks through various grid counting scenarios including the basic paths on a grid, Catalan Numbers and culminates to an explanation of the Lindstrom-Gessel-Viennot (LGV) Lemma, a fundamental result in algebraic combinatorics for counting non-intersecting paths on a directed acyclic graph (DAG). The video is self-contained and requires no prior knowledge of advanced combinatorics.
Analytics
Comments
Incredible explanation of a simple to state yet nontrivial problem, great job!
Ridiculously cool, presented cleanly and clearly!
I really enjoyed watching it. Keep up the good work
Okay, so, I do like this video a lot, but I will say you lost me at chapter 3. Your explanation started to get pretty involved and you started mentioning things like Catalan Numbers without ever explaining what they are. It’s always difficult to gauge what does or doesn’t need explaining in advanced math topics like these, but even a brief aside or visual footnote explaining X or Y concept would help with that without slowing the video down.
All that said, your enthusiasm shows and it’s pretty infectious. The animations are smooth and the voiceover is clean. Great job!
Nice video with good explanations, smooth animations and surprisingly neat explanation at the end. I wasn’t particularly convinced by the motivation of the general’s supply lines. You mention at the end the result actually applies to general DAGs - it would have been nice to see more of that (at least getting the full statement of the lemma) and maybe even for the whole video to have not been on a grid.
Small note about the animations - the circles at around 11 mins were a bit janky and out of time of the commentary and confused me for a bit.
Great work overall!
Bit hard to follow for high school students/teachers.
Superb video. Explains Dyck paths and LGV beautifully.
Minor comments: I think the “avoiding war” overlay was a bit too tacky for my taste.
At the end when you say that LGV applies for general dags, the animation to illustrate this point distorts the grid graph, but doesn’t actually change the graph structure, just the R2 embedding.
I love the retro video game sound effects! And the enthusiasm, very captivating.
Overall, very good. But it didn’t really go anywhere, it just sort of ended.
Great title Like the intro to combinatorics, but for those that don’t know how to calculate 10 choose 5, a formula would’ve been nice. generally i feel a little more explanation to why the numbers work the way they do would be useful for a beginner trying to follow a long. a bit of extra logic as to why the flip works instead of forcing the viewer to rely on logic and intuition also the level of the video seems unclear. it starts without expecting combinatorics and jumps to matrices, but still a banger if you have the math knowledge to understand. the editing was also fantastic along with the pacing and structure
The topic is interesting, and the presentation is very clear and well-motivated. My one suggestion would be to choose a more colorblind-friendly set of colors than red, orange, and green.
Truly fantastic video! I really love the way you split it into chapters that build on each other, and showed a lot of wisdom in breaking it down for the viewer step by step. (The little animations between chapters were also funny). The first place things where I noticed some potential improvement was the reflection principle for counting the forbidden zone…I think this one the explanation was good but the meta-explanation was not enough to let the user see what you are doing. Like you explained the reflection very well, but the idea of building a bijection only came later…the clarity could be improved slightly by telling people “we are going to show that XYZ is counted by XYZ” first, then they are ready to recieve the argument. (There’s a quote from Aristotle “Tell them what you’re going to tell them, tell them and tell them what you’ve told them”…the first bit of telling what you are going to tell has room for improvement!) Tge Catalan numbers could also have a bit more care for people who have never seen them before. (Instead of “this happens to be the catalan number”, something like “there is a famous sequence of numbers called the Catalan numbers, and its given by this!”) The final proof of the LGV lemma is also nicely done; great visuals for the start and the end points. This is a topic I’ve seen before (actually was used in my PhD thesis) and this video is by far the most accessible introduction to the topic I’ve encountered. Really nicely done! My last mathematical comment is that there is a is a bit of room at the end of the video to hook onto even more math: the LGV theorem is the start of the theory for a whole range of things called “determinatal processes” (where the determinant is exactly the LGV determinant) which is useful for random matrices and in physics and many other things. A previous SoME winner on the longest increasing subsequence is based on these, and so I think there is room to hook your video topic onto this larger area and leave viewers with a sense of wonder that a simple problem about generals can lead to some serious math.
Extremely clear and straightforward explanation.
Extremely fun video! I loved how concrete the animations made it, and I love the choice to warm up with easier problems before getting more and more general variations—the fact that it works for any DAG blew my mind. The sound effects were also fun.
I think the “flip about the pivot point” operations were a bit under-explained, and it could have been better emphasized in words that we only start at the first vertex of concern, or show a couple more examples to double-check our intuition. Maybe it could’ve been easier to understand if it was animated as the new colors sliding onto the existing paths rather than having paths move around.
The thumbnail made me think this would involve game theory, so that felt a bit misleading.
But overall, beautifully done!
There were some minor issues with the animations, such as objects appearing before the audio, but in general you did a great job keeping the audience engaged during the whole video. I really enjoyed your video.
That video was a great blend of something that start out with an intuitive description and extends it to more in a way that gets less intuitive and at bit less clear but made me want to “get my hands dirty” and make things clearer to me! It also left me wondering about various generalizations, one of which, they cover - more generals. What about higher dimensional regular grids? Limits as the graphs come from finer and finer regular grids?
A small improvement would be to make the last graph not be simply a geometric distortion of the directed, acyclic graphs arising from a regular grid. Just add (or subtract) a few nodes/edges along with some geometric distortion.