Linkage

Goodbye Insta (\(\mathbb{M}\)). I don’t have an Instagram account. I don’t want to join yet another closed system for capturing my data and sending it to a corporation. But there were a few people whose Instagram accounts I would check out semi-regularly. No longer. Now Instagram won’t show me any posts not-logged-in. If you’re going to fence yourself off from the Internet, then you’re fencing yourself off from me. If you think this is going to encourage me to make an account, the opposite is true.

Four pages are indeed necessary for planar graphs (\(\mathbb{M}\)). At STOC 1986, Yannakakis proved that planar graphs have 4-page book embeddings, and announced an example requiring 4 pages, but never published the example. Finally now Bekos et al. have provided detailed constructions for planar graphs requiring 4 pages. Still lost in limbo: Unger’s claim from 1992 that testing 3-page embeddability with fixed vertex ordering is polynomial.

Universities are starting to see the costs of the lockdown (\(\mathbb{M}\)), in lost revenue from students and medical centers and extra expenses from the transition to remote learning — the linked story is on the University of California, but other universities are likely in similar or worse shape. So far my campus has not announced any specific cuts but colleagues predict that a hiring freeze, at least, is likely to come.

Subgraph densities in a surface (\(\mathbb{M}\)). In 1993 I published a paper “Connectivity, graph minors, and subgraph multiplicity” showing that a planar graph \(G\) can have at most linearly many copies in larger planar graphs if and only if \(G\) is 3-connected. I thought it was long-forgotten, but now Huynh, Joret and Wood have generalized it in two ways: other surfaces than the plane, and other exponents than one in the number of copies.

Fix boyer_moore_searcher with the Rytter correction (\(\mathbb{M}\), via). A 40-year-old bugfix to an even older linear-time string matching algorithm finally makes it to production code, with an admonishment that this should have been mentioned in more recent explanations of the algorithm such as Wikipedia’s (since added).

To cheer you up in difficult times II: Mysterious matching news (\(\mathbb{M}\)). Gil Kalai blogs about two recent papers: one by Gal Beniamini and Noam Nisan on a polynomial that is one for bipartite graphs with perfect matchings and zero otherwise and one by UCI colleagues Vijay Vazirani and Thorben Tröbst extending it to test whether a subgraph of a weighted complete bipartite graph contains a minimum-weight perfect matching.

Inkscape 1.0 (release candidate) now runs natively on OS X (\(\mathbb{M}\), via). I still haven’t tried it, and the discussion suggests it still needs some tuning. But it seems pretty popular in free-software circles, and it’s good to know that there are free vector drawing programs out there that can compete with the (expensive) one I use, Adobe Illustrator.

Antoine Chambert-Loir asks for an explanation of the Schläfli graph’s Hamiltonicity, or more specifically how the Wikipedia article’s infobox illustration can be related to more standard constructions of the graph.

The eggbox puzzle (\(\mathbb{M}\)). The Aperiodical has been posting “Big Lock-Down Math-Off” posts, double-headers with a vote for which “made you say Aha! the loudest”. I chose this one with James Munro’s eggbox puzzle because the illustrations made me say Aha! This state space is a median graph!

To find the median of three \(k\)-egg placements, put the \(k\)th egg in the median of its three positions. In fact, it’s a distributive lattice where the meet of two placements is to move each egg to the rightmost of its two positions and the join is to move each egg to the leftmost of the two. Of course that doesn’t help much in solving the actual puzzle…

Another MDPI journal editorial board resigns (\(\mathbb{M}\); “another” because of the 2018 Nutrients mass resignation). The topic appears to be related to chemical engineering. The resigning editor-in-chief describes the reason: “MDPI has stated that it will not modify the current plan for rapid, quota-driven growth, while the Editorial Board will not compromise its overarching goals of publication quality and scholarly contribution.”

I had been using Wunderlist for to-do lists of review/submit deadlines, a shared family grocery list, etc but as I posted earlier, it is being strangled by new owner Microsoft to push you to their other thing. So after comparing other cross-platform shareable to-do-list apps I chose todoist because of its similar workflow and Wunderlist import feature (\(\mathbb{M}\)). Close second was Tom Hull’s suggestion, Trello. Not as close: Microsoft.

Can’t I please just visit one friend? (\(\mathbb{M}\)) Or, how graph drawing helps us understand the importance of maintaining strict isolation.

ICANN blocks .org sale (\(\mathbb{M}\), via). This is very good news, and follows onto their delay of the sale a couple of weeks ago after the intervention of the California attorney general.