
Congratulations, Dr. Frishberg!
My student Daniel Frishberg successfully passed his dissertation defense today!

Permutation supersequences and shortest paths
You may have heard of permutation superpatterns and superpermutations, but have you heard of permutation supersequences? They turn out to be closely related to how quickly we can find shortest paths in graphs with negative edge weights using the Bellman–Ford algorithm.

Linkage with new kittens
 Numberphile on book embeddings of graphs (\(\mathbb{M}\)), and on the longawaited proof of the claim that some planar graphs require 4 pages. For more reading on this, see the Wikipedia article on book embeddings.

Coloring the plane for generic norms
Noga Alon recently stopped by my department earlier this month to give two talks. During his visit, he pointed me to some interesting recent work he had done on coloring the plane, buried in the discussion at the end of his preprint “Unit and distinct distances in typical norms” (arXiv:2302.09058, with Matija Bucić and Lisa Sauermann). Recall that the stillunsolved Hadwiger–Nelson problem asks how many colors are needed to color the points of the plane so that no two points at distance one from each other have the same color. The figure below shows a 7coloring in the pattern of a hexagonal tiling, with this property, so at most seven colors are needed. The black unit distance graph outlined in the same figure, the Moser spindle, requires four colors, but by now much larger and more complicated unit distance graphs are known that force the number of colors to be at least five.

Linkage
 We’ve already seen AIgenerated peerreview for Wikipedia articles (\(\mathbb{M}\)), with such brilliant insight as:

A fractal arbelos
If you nest a triangle in a hexagon in a dodecagon, etc., doubling the number of sides each time, you get a triangulation. This sequence of nested polygons was already known to Archimedes, who took it all the way up to 96 sides in order to calculate an accurate approximation of \(\pi\).

Linkage
 Two recent posts by Dave Richeson on connections between stamp folding and the design of circular labyrinths and their combinatorial enumeration as meanders (\(\mathbb{M}\)). See also Wikipedia on map folding and meanders.

Linkage with two breakthroughs
 An exponential improvement for diagonal Ramsey (\(\mathbb{M}\)). The number of vertices needed to force either a \(k\)vertex clique or independent set is now down to \((4\varepsilon)^k\) for a small \(\varepsilon\). New preprint by Sahasrabudhe, Morris, Griffiths and Campos.

Logic engines and product graphs
The graph product structure theorem of Dujmović et al.^{1} states that every planar graph can be represented as a subgraph of a special kind of graph product: the strong product of a path graph and a graph of bounded treewidth. Like other graph products, the strong product \(G\boxtimes H\) of two graphs \(G\) and \(H\) has a vertex for each pair of a vertex in \(G\) and a vertex in \(H\). You can move in the strong product by moving along an edge in one of the factors and staying put in the other (like the Cartesian product) but also by moving along an edge in each factor (like the tensor product). So, for instance, the graph of king moves on a chessboard is a strong product of two paths, one representing the sequence of rows along which the king can move and the other representing the sequence of columns.

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood (2020), “Planar graphs have bounded queuenumber”, JACM 67 (4): Art. 22, doi:10.1145/3385731, arXiv:1904.04791. ↩


Linkage for the day after π day
…although I guess \(\pi+1\) day would be April 14? My site generator doesn’t appear to like putting formulas or markup in article titles; probably that’s a good thing.
subscribe via RSS