Linkage

Square-difference-free set (\(\mathbb{M}\)), now a Good Article on Wikipedia. As the name suggests, these are sets of integers no two of which differ by a square. My favorite such set consists of the losing positions in subtract-a-square, where each move removes a square number of coins from a pile of coins, winning by taking the last coin. This general class of sets and the subtract-a-square set have \(o(n)\) elements up to \(n\), but their maximum density remains unknown.

Can a convex polyhedron have an odd number of faces, all congruent (\(\mathbb{M}\)). If so the faces would have to all be kites, per comments at the link. Which raises the question: can a convex polyhedron with congruent kite faces avoid being either a trapezohedron or formed from deltahedron (a polyhedron with equilateral triangle faces) by subdividing each triangle into three kites? Both automatically have evenly many faces.

You might know about regular numbers (\(\mathbb{M}\)), of the form \(2^i\cdot 3^j\cdot 5^k\), from Babylonian mathematics, music theory, Plato, or as a test case for functional programming. But did you know that they come up in biology, as numbers of years between mass flowering in certain types of bamboo? See Veller, Nowak and Davis, “Extended flowering intervals of bamboos evolved by discrete multiplication”, Ecol. Lett. 2015, via Andrey Zabolotskiy at OEIS A051037.

My new paper “Finding relevant points for nearest-neighbor classification”, has won the best paper award of the SIAM Symposium on Simplicity in Algorithms, SOSA22 (\(\mathbb{M}\)). Woo! In other news, the lists of accepted papers at SOSA, SODA, and ALENEX are online.

Animation of the minimum-weight matchings of increasingly many points of two colors in a unit square (\(\mathbb{M}\)). Because the color densities fluctuate, the matching develops regions of many parallel long edges transporting excess density from one place to another. This is reflected mathematically in the fact that the expected length is \(\Theta(\sqrt{n\log n})\) compared to \(\Theta(\sqrt{n})\) for non-bipartite matching; see Ajtai, Komlós, and Tusnády, “On optimal matchings”, Combinatorica 1984.

Jacob E. Goodman, famed as a discrete and computational geometer and cofounder of the top journal in the field, Discrete & Computational Geometry, died on October 10 (\(\mathbb{M}\), see also).

The classical CS interview question of destructively reversing a singly-linked list goes back at least to Ed McCreight in 1973 (\(\mathbb{M}\)). But if you generalize a singly-linked list to a zipper (directed out in both directions from a finger into it) then reversal is trivial and you get the classical algorithm by moving your finger from start to end. I don’t know of references; maybe the zipper people are too focused on functional/non-destructive/reentrant methods to mention this?

I recently learned that the name “Thomsen graph” for comes from the work of Danish chemist Julius Thomsen (\(\mathbb{M}\)) who proposed in 1886 that it describes the structure of benzene. Thomsen was late to the party: Kekulé had already proposed the benzene ring in 1865. But the name for the graph stuck.

My UCI colleague Vijay Vazirani is looking for a postdoc in algorithmic design / algorithmic game theory (\(\mathbb{M}\)). One-year, renewable.

Fairmandering: generating fairness-optimized political districts (\(\mathbb{M}\)), Wes Gurnee and David Shmoys. If you generate a hierarchically-organized and large family of partitions of a state into contiguous equal-population regions, you can then optimize over the hierarchy for fairness. Gurnee and Shmoys choose to optimize the efficiency gap but their method is a two-edged sword: it would work equally well to optimize for partisan advantage.

What high-order regular polygons do you have lying around your house?

In praise of non-deductive puzzles (\(\mathbb{M}\)). I’m not sure I agree that logic puzzles solved by intuition and guessing are better than ones where you have to make sufficiently deep deductions, but they both beat blind backtracking. I do agree that numberlinks should fill the grid as a natural consequence of connecting the numbers, not an extra constraint. And that non-unique generators for puzzles whose solutions should be unique are an abomination.

Preserving the history of applied mathematics (\(\mathbb{M}\)), John Boyd in SIAM News.

University of Florida blocks faculty from being expert witnesses on voting rights, claiming that lawsuits against the state create a conflict of interest (\(\mathbb{M}\), also, also). Beyond being an assault on academic freedom, this appears to violate the 1st amendment. US states can limit on-the-job speech, but here they would have testified on their own time, a routine activity that was blocked only because of its content.