Linkage

University of California to resume Elsevier talks after signing deals elsewhere (\(\mathbb{M}\), via). We’ve been without access to newly-published Elsevier papers since last year (although old papers are still accessible) but it hasn’t affected me much. I hope the university negotiators continue to stand firm.

TikZJax (\(\mathbb{M}\)). Render your TikZ diagrams online in web pages.

An algorithm whose termination cannot be proven in Peano arithmetic (brief announcement by Gabriel Nivasch of forthcoming work with Jeff Erickson and Junyan Xu). Just try to compute the following recurrence in the obvious way:

Did Newton invent convex hulls? (\(\mathbb{M}\)). I haven’t received any useful answers yet from my post to the HSM stackexchange but maybe someone beyond that site knows something relevant.

New arXiv preprint: Simplifying activity-on-edge graphs (\(\mathbb{M}\)), with Daniel Frishberg and Elham Havvaei. It’s on graphs whose vertices represent project milestones and edges represent either tasks or ordering constraints between milestones. I already wrote a blog post on simplification rules for these graphs, but now we can prove that these rules produce an optimal equivalent graph in polynomial time.

The plum trees (or cherry? I don’t know) have been in bloom outside the building I work in (\(\mathbb{M}\)).

Schnittpunkte (\(\mathbb{M}\)). Hans Walser extends his book 99 Points of Intersection to over 800 geometric constructions involving points where three or more lines, circles, or other curves all cross each other. The text is in German but that doesn’t matter because there’s so little of it. Most of the content is a figure for each point of intersection, with three smaller figures showing its construction.

Triangle dissection, no shared edges (\(\mathbb{M}\), via). The question is how to divide a triangle into smaller triangles, no two sharing a whole edge, but the solutions shown also have no separating triangles and a straight angle at each interior vertex. Double-counting angles and combining with Euler shows that, with these conditions, \(F=V-1\). Do all internally-4-connected planar graphs with \(F=V-1\) work?

Visualize how much junk from third-party sites you download when you visit your favorite web site (\(\mathbb{M}\)). Mathstodon.xyz: Completely clean. Wikipedia: only a few small bits and pieces from other Wikimedia sites. Some other sites that I visit regularly: lots of junk. Adblockers help, but attention to keeping things slim in site design would help more.

Big cuts to most US research funding agencies in Trump’s proposed 2021 budget (\(\mathbb{M}\)). And the targets for these big proposed budget cuts also include the Centers for Disease Control and the part of the CDC that handles animal-to-human disease transmission (like the current coronavirus outbreak; via). The only not-so-bad news here is that actual federal budgets have to start in the House of Representatives, not the White House. But this is probably a warning of budget battles to come soon.

The list of accepted papers for this year’s Symposium on Computational Geometry (late June in Zürich) is online (\(\mathbb{M}\)). So far there are only authors and titles (by the date of the conference the full papers will be online open access) but probably for many of them you can search for the title and find more.

How to generate all flats of the cycle matroid of a graph (\(\mathbb{M}\)). A flat is a partition of vertices into connected induced subgraphs. If you give edges distinct weights and look at the minimum spanning forests of the flats, you get a nice tree structure on the space of all flats where the parent of a flat removes the heaviest edge from its forest (partitioning one tree and therefore one subgraph into two). This leads to efficient enumeration algorithms using reverse search.

Jorge Hirsch repudiates the h-index he invented (\(\mathbb{M}\)): “I have now come to believe that it can also fail spectacularly and have severe unintended negative consequences. I can understand how the sorcerer’s apprentice must have felt.” (This is an aside; the actual linked article is about Hirsch’s difficulty in breaching the orthodox consensus on superconductivity.)

A quasi-polynomial algorithm for well-spaced hyperbolic TSP (\(\mathbb{M}\)). This new preprint by Sándor Kisfaludi-Bak (accepted to SoCG) caught my attention. TSP is NP-hard for Euclidean points or close-together hyperbolic points. This paper shows that it’s much easier when the points are widely spaced in the hyperbolic plane. The idea is to separate the input by a short line segment that the solution crosses few times and apply dynamic programming.

The world’s hardest irregular sudoku (\(\mathbb{M}\)). The joke is that the puzzle itself is easy. “Hardest” means only that it has few givens. The meta-puzzle is to construct the puzzle: a 9x9 grid divided into 9 9-ominoes (analogous to the 3x3 blogs of standard sudoku), with as few grid cells as possible specified as givens so that there is a unique solution.