-
Linkage
- The early history of continued fractions (\(\mathbb{M}\)). Includes the equivalences of infinitude with irrationality and periodicity with quadraticness, and the work of Euler and Gauss on continued fractions for values with nice series expansions.
-
Pathbreaking for intervals
The use of Nash’s Hex lemma in my previous post, according to which any 2-coloring of a triangular grid has a long monochromatic path, naturally raises the question: for which graphs other than the triangular grid is this true? In that post I mentioned that it is also true for certain outerplanar graphs, but false for bipartite graphs and for subcubic graphs. Here’s another class of graphs for which it is false: the graphs of bounded pathwidth. These graphs can always be 2-colored in a way that breaks up all long paths, leaving the remaining monochromatic paths of bounded size.
-
Hex, books, and queues
My latest preprint is “Stack-number is not bounded by queue-number”, arXiv:2011.04195, with Vida Dujmović, Robert Hickingbotham, Pat Morin, and David R. Wood; Hickingbotham is a postgraduate student of Wood at Monash University. It solves a question implicit in the work of Heath, Leighton and Rosenberg (1992) on whether graphs of bounded queue number have bounded stack number (they don’t), disproves a conjecture of Blankenship and Oporowski (1999) on whether subdividing a graph of unbounded stack number can reduce its stack number to bounded (it can), and answers a question of Bonnet, Geniet, Kim, Thomassé, and Watrigant (to appear at SODA 2021) on whether graphs of unbounded stacknumber can have bounded sparse twin-width (they can). And it does so in part using an old trick from combinatorial game theory from a mathematician who won a Nobel prize for his work in game theory. But what are stack number and queue number? And what could combinatorial games possibly have to do with these sorts of questions in structural graph theory?
-
Constant width from involutes of pseudotriangles
In his online collection of fun stuff, Jeff Edmonds recently posted a method of constructing curves of constant width by spinning a pencil on a flat surface, with a varying axis, and tracking the movement of its ends. It is pretty similar to the classical method of crossed lines described by Martin Gardner in The Unexpected Hanging, in which one constructs an arrangement of lines in the plane, sorts them in circular order by slope, and builds a curve out of circular arcs centered at the crossing points of consecutive lines in this sorted order. However, it grows the curve at both ends simultaneously, rather than only at one end, and chooses the lines dynamically rather than in advance. Regardless, the result is the same: a piecewise-circular constant-width curve.
-
Linkage for a trick-or-treat-less Halloween
- 3d flythrough of a near-optimal TSP tour through a dataset of nearly 221 stars (\(\mathbb{M}\), via). I found the “full view of tour” a lot easier to navigate than the mini-view on the main page.
-
Graphs whose cycles all touch
An interesting recent question on MathOverflow asks about graphs in which all cycles touch. Here, touching is meant in the same sense as a bramble in graph structure theory: every two cycles either share a vertex or contain the two endpoints of an edge from one cycle to the other. The graphs with this property include all the complete graphs (girth 3), complete bipartite graphs (girth 4), and theta graphs (arbitrarily high girth but very simple structure). As originally phrased, it asked whether there exists \(g\) such that graphs of girth \(\ge g\) with all cycles touching have bounded treewidth. Partial results given there by Tony Huynh and me show that the condition of bounded treewidth can be replaced by bounded vertex cover number or a bounded number of vertex-disjoint cycles without changing the answer.
-
The graphs of stably matchable pairs
The stable matching problem takes as input the preferences from two groups of agents (most famously medical students and supervisors of internships), and pairs up agents from each group in a way that encourages everyone to play along: no pair of agents would rather go their own way together than take the pairings they were both given. A solution can always be found by the Gale–Shapley algorithm, but there are generally many solutions, described by the lattice of stable matchings. Some pairs of agents are included in at least one stable matching, while some other pairs are never matched. In this way, each instance of stable matchings gives rise to a graph, the graph of stably matchable pairs. This graph is the subject and title of my latest preprint, arXiv:2010.09230, which asks: Which graphs can arise this way? How hard is it to recognize these graphs, and infer a stable matching instance that might have generated them? How does the graph structure relate to the lattice structure?
-
Polyhedra without disjoint faces
Some research I’ve been doing led me to consider the (prism,\(K_{3,3}\))-minor-free graphs. It’s not always easy to go from forbidden minors to the graphs that forbid them, or vice versa, but in this case I think there’s a nice characterization, which I’m posting here because it doesn’t fit into the research writeup: these are the graphs whose nontrivial triconnected components are \(K_5\), wheel graphs, or the graph \(K_5-e\) of the triangular bipyramid. The illustration below shows an example of a graph with this structure, with its nontrivial triconnected components colored red and yellow. There’s a simpler and more geometric way to say almost the same thing: the only convex polyhedra that do not have two vertex-disjoint faces are the pyramids and the triangular bipyramid.
-
Linkage
- Mirzakhani and meanders (\(\mathbb{M}\)). On some more-than-coincidental similarities in formulas found by Mirzakhani for numbers of geodesics on hyperbolic surfaces and by Vincent Delecroix, Elise Goujard, Peter Zograf, and Anton Zorich in a new preprint for numbers of meanders, closed curves with a given number of intersections with a line.
-
Linkage
- A new algorithm for graph crossings, hiding in plain sight (\(\mathbb{M}\)). Dynamic graph planarity testing, in Quanta. The original papers are arXiv:1910.09005, in SODA 2020 and arXiv:1911.03449, in STOC 2020, by Jacob Holm and Eva Rotenberg.
subscribe via RSS