Week 12: Ramsey theory, Crane et al.’s heat method

Note: Week 12 covers April 6 through 12 of 2026

Ramsey theory

A few months ago, I watched N Is a Number: A Portrait of Paul Erdős, a documentary on late Hungarian mathematician Paul Erdős. During a discussion of the party puzzle and Ramsey theory, an article co-authored by Ronald L. Graham came up. I figured they were referring to this July 1990 Scientific American Magazine article¹. I hadn’t read it in its entirety, even though I downloaded it in October/November 2025.

The article has some pop-sci-like quotes:

“any structure will necessarily contain an orderly substructure.”

“… complete disorder is an impossibility.”

But it also lands the Ramsey theory down to earth:

“We can then describe the full Ramsey theorem. If the number of objects in a set is sufficiently large and each pair of objects has a one of a number of relations, then there is always a subset containing a certain number of objects where each pair has the same relation.”

I found the article quite interesting:

• I especially enjoyed Erdős’ probabilistic method for determining the lower bound of the Ramsey number for a certain \(R(r,b)\). It’s more or a less a “nasty trick”, in a good sense, as Angela Collier says. It’s true: I didn’t fully grasp it, but it was quite cool.

• I loved the derivation of van der Waerden’s theorem from the result obtained by Hales and Jewett in 1963 from tic-tac-toe in higher n-dimensional spaces. It’s such an awesome result/insight.

• I was introduced to the Ackermann hierarchy, of which I, surprisingly, didn’t know anything beyond the name. Shame, shame on me.

The heat method for distance computation

Some interesting quotes from the article (Crane, Keenan, Clarisse Weischedel, and Max Wardetzky. 2017. ‘The Heat Method for Distance Computation’. Communications of the ACM 60 (11): 90–99. https://doi.org/10.1145/3131280):

• On how the algorithm has a different running time in practice:

  Mitchell et al. give an \(O(n^2 \log n)\) algorithm for computing the exact polyhedral distance from a single source to all other vertices of a triangulated surface. Surazhsky et al. demonstrate that this algorithm tends to run in sub-quadratic time in practice, and present an approximate \(O(n \log n)\) version of the algorithm with guaranteed error bounds.

• Applications of the heat method:

  Recently, the heat method has facilitated a variety of tasks in computational science and data analysis. For example, Huth et al. use fast distance queries to optimize a probabilistic model of cortical organization; van Pelt et al. use the heat method to assist cerebral aneurysm assessment; Zou et al. use the heat method for efficient tool path planning; Solomon et al. leverage our approach to efficiently solve optimal transport problems on geometric domains; Lin et al. apply this approach to vector-valued data in the context of manifold learning.

• On how to get a smooth function with boundary conditions (see also Matt Ferraro’s 2021 blog post “Poisson’s Equation is the Most Powerful Tool not yet in your Toolbox”):

  Boundary conditions do however alter the behavior of our smoothed distance. Although there is no well-defined “correct” behavior for this smoothed function, we advocate the use of boundary conditions obtained by taking the mean of the Neumann solution \(u_N\) and the Dirichlet solution \(u_D\), that is, \(u = \frac{1}{2}(u_N + u_D)\). The intuition behind this behavior again stems from a random walker interpretation: zero Dirichlet conditions absorb heat, causing walkers to “fall off” the edge of the domain. Neumann conditions prevent heat from flowing out of the domain, effectively “reflecting” random walkers. Averaged conditions mimic the behavior of a domain without boundary: the number of walkers leaving equals the number of walkers returning.