# What’s up with the Graph Laplacian?

This is a guest post written by my friend, Jeremy Kun! He’s the author of the popular blog Math ∩ Programming, your go-to site for learning about algorithms, machine learning, cryptography, and so much more.

There’s a deep connection in mathematics between a graph (a set of vertices and edges), and the algebraic properties of special matrices associated with that graph.

Here’s the simplest example of this phenomenon. Say you take an undirected graph $G = (V, E)$ and you let $A = (a_{i,j})$ be its adjacency matrix, where $a_{i,j} = 1$ if $(i,j) \in E$ is an edge, and $a_{i,j} = 0$ otherwise. The matrix $A$ is an $n \times n$ square matrix with $n = |V|$. The remarkable fact is that the $i,j$ entry of $A^k$ contains the number of walks of length $k$ from $i$ to $j$. In this example, the cube of the adjacency matrix counts the number of length-3 walks (paths where you can repeat vertices/edges) between all pairs of nodes. So there is one walk from 5 to 3, and four walks from 1 to 4.

Advertisements

# The Four Color Problem

With an amusing history spanning over 150 years, the four color problem is one of the most famous problems in mathematics and computer science. The four color theorem states that the regions of a map (a plane separated into contiguous regions) can be marked with four colors in such a way that regions sharing a border are different colors. source: emaze.com/@ALFOCWOC

# Finding Adam

This post will outline the paper Finding Adam in random growing trees by Bubeck, Devroye, and Lugosi. The main question examined in this paper is simply stated and relatively unstudied: given a tree, which has been generated under some attachment model, find the first vertex. “First” here meaning oldest. Think about the spread of a rumor, or disease. In these situations, the resulting distribution is known, but the starting point is not.

# Triangle Removal Lemma

The triangle removal lemma shows that if a lot of edges must be removed to make a graph triangle-free, then there must have been a lot of triangles in the original graph. While this observation may not sound ground breaking, it is a very useful tool in combinatorics.