
Linkage

Loops, degrees, and matchings
A student in my graph algorithms class asked how selfloops in undirected graphs affect the vertex degrees and matchings of a graph. The standard answer is that a selfloop adds two to the degree (because each edge has two endpoints) and that they are useless in matching because matchings should have at most one incidence to each vertex, not two. But that’s just a convention; one could reasonably declare that the contribution of a selfloop to the degree is one, and I’m pretty sure I’ve seen sources that do just that. With that alternative convention, it should be possible to include a selfloop in a matching, and use it to match only a single vertex.

Lattice Borromean rings
A lot of topology is finding ways to prove things that are really obvious but where explaining why they’re obvious can be difficult. So I want to do this for a discrete analogue of ropelength, the length of the shortest lattice representation, for the Borromean rings. You can find several pretty lattice (and nonlattice) representations of the Borromean rings in a paper by Verhoeff & Verhoeff, “Three families of mitered Borromean ring sculptures” [Bridges, 2015]; the one in the middle of their figure 2, thinned down to use only lattice edges and not thick solid components, is the one I have in mind. It is formed by three \(2\times 4\) rectangles, shown below next to Jessen’s icosahedron which has the same vertex coordinates. (You can do the same thing with a regular icosahedron but then you get nonlattice golden rectangles.)

Linkage
 Let’s not dumb down the history of computer science (\(\mathbb{M}\), via). A 2014 plea from Knuth to historians of computer science to stop ignoring the technical parts of the history, reprinted this month in CACM.

Linkage
 Hilbert’s 13th, unsolved (\(\mathbb{M}\)). You can solve polynomials of degree at most four using oneargument algebraic functions like \(\sqrt x\). If \(RD(n)\) denotes the number of arguments needed for degree\(n\) polynomials, then \(RD(4)=1\). Hilbert asked whether \(RD(7)=2\). Vladimir Arnold showed in the 1950s that you can solve all polynomials with twovariable continuous (but not algebraic) functions, but mathematicians are only now catching on that the algebraic problem is still open. See also some recent bounds on \(RD\).

Which inducedsubgraph problems are easy, and which are hard?
My latest preprint, arXiv:2101.09918 with Sid Gupta and Elham Havvaei, has a mouthful of a title: “Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes”. It’s about finding large induced subgraphs with a given property within a larger graph, such as in an earlier paper I wrote on finding large planar induced subgraphs.

Bracing squaregraphs (and other rhombus tilings)
A bookshelf or other structure made only of vertical and horizontal beams will easily fall over unless its joints are very strong, because axisparallel structures are not inherently rigid. The vertical beams can tilt away from being perpendicular to the horizontals, without changing the relative spacing of the joints, and that can lead to books all over the floor. Here’s an example from a 2011 earthquake at the Smithsonian that didn’t get quite that far, but did damage some shelves beyond repair:

Linkage
 Rigid heptagon linkage (\(\mathbb{M}\)). Improvements in the size of unit distance graphs whose unit distance representation is forced to contain a regular heptagon, from 59 to 35 edges. Based on a math stackexchange question. See also an old page on the same problem from Erich Friedman’s site, moved from its old location at Stetson University.

Yearend linkage
 A mathematician’s unanticipated journey through the physical world (\(\mathbb{M}\)). Quanta profiles Lauren Williams and discusses her work on enumerating cells of Grassmannians and its unexpected connections with intersection patterns of solitons.

Linkage
 3dprinted models of the chaotic attractors from dynamical systems (\(\mathbb{M}\)). Stephen K. Lucas, Evelyn Sander, and Laura Taalman in the cover article of the latest Notices.
subscribe via RSS