Linkage

Creating weaving patterns from subdivision schemes (\(\mathbb{M}\)), new paper by Lipschütz, Reitebuch, Skrodzi, and Polthier, and explanatory thread by Skrodzi.

How would you make a sphere from three circles?, asks Peter Rowlett after his son said he could do it.

Counting 3colorings and followup post (\(\mathbb{M}\)). Like all “natural” \(\mathsf{NP}\)complete problems (and many easier problems), the 3coloring problem should have a \(\#\mathsf{P}\)complete counting version, but the gadgets needed to prove it are a little subtle and tracking down the history of proof of this result took some effort.

Polyhedra in which all but one edge have a right angle (\(\mathbb{M}\)), 3dprinted based on a construction used by Sydler to study Dehn invariants. Achieving this property leads to surprisingly complicated polyhedra.

Two years ago I linked to a post by Adam Goucher, solving an old MathOverflow question by showing that it is possible to find a dodecahedron, combinatorially equivalent to a regular one, with rational coordinates, inscribed in a unit sphere. But now there are infinitely many (\(\mathbb{M}\))! Some messy algebra, and then some work with elliptic curve group operations, eventually simplifies down to a parametric family with a dodecahedron for each integer right triangle.

For integer \(A\), a grid of \(n\) points has roughly \(n^2\sigma(A)/A\) area\(A\) triangles, where \(\sigma\) is the sum of divisors (\(\mathbb{M}\)); see Erdős & Purdy 1971 who used nonsquare grids and factorial \(A\) to find points with \(\Omega(n\log\log n)\) unitarea triangles. So how big is \(\sigma(A)/A\)? It depends on the Riemann hypothesis! If RH is true, at most \(e^\gamma\log\log A\) for \(A>5040\). If not, slightly larger infinitely often.

Slides from my talk on “Graphs in Nature” (\(\mathbb{M}\)) at the International Colloquium on Graph Theory and Combinatorics in Montpellier, France.

Prince Rupert’s cube (\(\mathbb{M}\)): a cube can fit through a square hole drilled through another cube its size, or even slightly smaller. Now a Good Article on Wikipedia. I’ve been wondering: is it possible to make Prince Rupert’s Borromean rings, by drilling square holes into three unit cubes, each simultaneously passing through the hole in the next one?

On the CSTheory stackexchange, Alexey Milovanov asks for updates on the (as far as I know still unknown) complexity of an old problem, finding shortest addition chains (\(\mathbb{M}\)). This highlights something I love about editing Wikipedia: if you take the effort to track down a repeated error in the literature, and document it properly in the right Wikipedia article, then maybe 14 years later the correction rather than the error can be common knowledge.

The MAA reviews Joe O’Rourke’s new book, PopUp Geometry: The Mathematics Behind PopUp Cards (\(\mathbb{M}\)).

Killing a vortex (\(\mathbb{M}\)), by Thilikos and Wiederrecht. Robertson and Seymour’s structural decomposition of minorclosed graph families glues together surfaceembedded graphs, a few arbitrarilyconnected “apex” vertices, and “vortices”, boundedpathwidth graphs attached to faces. For graph matching, vortices are problematic. This new preprint describes the families that don’t need them and shows that they are exactly the ones whose matchings can be counted quickly.

Scott Aaronson, quantum complexity theorist and debunker of quantum hype on his blog, is also a target of trolls who have pushed him to back down from his freespeech principles and restrict comments (\(\mathbb{M}\)). Boaz Barak gives some support. Via Boaz I refound Scott’s 2005 “NPcomplete Problems and Physical Reality” debunking soap bubble and rubber band solvers for hard optimization problems. Worth a reread!

I tend to pick technologically better solutions over popular ones, despite popularity’s importance for longterm viability (\(\mathbb{M}\)). Which is why I just switched from a gas range to induction. It has all the responsiveness of gas (vs the glacial response of conventional electric), is more efficient, has a smaller carbon footprint, fewer noxious emissions, etc. These are still uncommon in Southern California, but new laws require electric appliances for new construction, and I hope that with familiarity they will become better liked as well.

Seriously bad data in Google’s GoEmotions dataset (\(\mathbb{M}\), via), some 58K reddit comments categorized by affect. Opinions in the post and comments vary on why the categorization was so inaccurate, including lack of context, farming it out to poorlypaid workers in countries less likely to be familiar with the specific idioms used in the comments, or maybe just that it’s a hard problem.