If you like The Palindrome, please consider supporting me with a paid subscription. It’s $100 a year, or $10 a month, and in return you get well-researched machine learning/mathematics deep dives such as Machine Learning is Not Just Statistics, Matrices and Graphs, or Vectorization in Theory + Vectorization in Practice.
Your support makes it possible for me to create high value, high signal educational content. Thanks!
Hey! It’s Tivadar from The Palindrome.
In the past couple of weeks, I’ve been working hard on the upcoming Graph Theory for Visual Learners video. It’s estimated to be around 45 minutes long, and now I’m entering the final phase of production.
The video is made possible by your generous support. If you want to become a supporter of The Palindrome (and have your name credited in the video), consider upgrading your subscription.
I’m an independent, audience-funded content creator, and your support makes these high-quality educational posts/videos possible. Thanks!
It’s the longest video I have ever done, practically a mini-course on graph theory, packed with beautiful animations. I built a custom animation engine for my future videos (which I simply call The Palindraw), and Graph Theory for Visual Learners will be its debut.
Let me share a couple of teasers with you; I’m extremely excited about this. Here’s the Hamiltonian paths/cycles visualization on Hungary’s road network between its major cities.
Here’s an illustration of decision trees.
And finally, here’s the visualization of breadth-first search and depth-first search on the graph of Szeged (Hungary), my hometown. The timing and pace are a bit off here due to the lack of narration; this’ll be more action-packed in the final video. Sorry for that.
The full video is expected to be released within the next two weeks; will let you know about the exact timeline.
If you are interested in the details, here’s the exact topics I cover:
Graph modeling: Representing road networks, polyhedra, computations, and DNA fragments as graphs.
Basic definitions: Vertices, edges, simple graphs, drawings, isomorphism, vertex degree, and limitations of degree information.
Walks and paths: Definitions, eliminating repetitions, and the Königsberg bridge problem.
Connectivity: Reachability as an equivalence relation, connected components, and disconnection through edge removal.
Graph search: Adjacency lists, breadth-first search, depth-first search, component discovery, and shortest paths by edge count.
Cycles: Closed walks, trails, cycles, cycle detection, and resilience to edge removal.
Trees: Equivalent characterizations, unique paths, roots, levels, traversal, maze solving, and decision-tree classification.
Hamiltonian paths and cycles: Visiting every vertex once, computational difficulty, and genome assembly using overlap graphs.
Planarity: Planar drawings, Euler’s formula, the edge bound, the nonplanarity of the utility graph and the complete graph of five vertices, subdivisions, and Kuratowski’s theorem.
Vertex coloring: Proper colorings, chromatic number, clique lower bounds, Mycielski’s construction, map coloring, and the four-color theorem.
Edge coloring: Proper edge colorings, chromatic index, maximum-degree bounds, and Vizing’s theorem.
Ramsey theory: Monochromatic cliques, the pigeonhole argument for R(3,3) = 6, diagonal Ramsey numbers, and known bounds.
Directed and weighted graphs: Asymmetric relations, functions, computational graphs, derivative weights, weighted shortest paths, random walks, Markov chains, and transition versus adjacency matrices.
Graph measures: Stationary distributions, the connection to PageRank, vertex and edge betweenness centrality, and potential traffic bottlenecks.
Thanks for reading!
If you liked this post, you should support me with a paid subscription. It’s $100 a year, or $10 a month, and in return you get well-researched machine learning/mathematics deep dives such as Machine Learning is Not Just Statistics, Matrices and Graphs, or Vectorization in Theory + Vectorization in Practice.
Your support makes it possible for me to create high value, high signal educational content. Thanks!
My entire discrete mathematics course's graph theory summarised in an article!