
Linkage
 I was interested to see a familiarlooking graph drawing as one of the answers to the prompt “multiplicity” for the first entry in Mathober 2021 (\(\mathbb{M}\)). It’s a multigraph formed by a triangle with tripled edges, and looks a lot like the drawing I made for the Wikipedia Shannon multigraph article, prettied up by making an infinitely recessing sequence of these drawings rather than just one. Good choice for multiplicity.

Relevant neighbors
I have a new preprint, “Finding Relevant Points for NearestNeighbor Classification”, arXiv:2110.06163, to appear in January at the SIAM Symposium on Simplicity in Algorithms (SOSA22). It’s about points in Euclidean spaces of dimension three or more, but I thought it would make a good warmup to discuss here the onedimensional version of the same problem, solved (together with the 2d version) by Bremner, Demaine, Erickson, Iacono, Langerman, Morin, and Toussaint in their paper “Outputsensitive algorithms for computing nearestneighbour decision boundaries”, Discrete Comput. Geom. 2005.

Generating fibbinary numbers, three ways
I just added to Wikipedia two articles on the Jordan–Pólya numbers and fibbinary numbers, two integer sequences used in my recent paper on Egyptian fractions. Jordan–Pólya numbers are the products of factorials, while the fibbinary numbers are the ones with binary representations having no two consecutive 1’s. The OEIS page on the fibbinary numbers, A003714, lists many ways of generating this sequence algorithmically, of which most are boring or slow (generate all binary numbers and test which ones belong to the sequence; you can test if a variable
x
is fibbinary by checking thatx&(x>>1)
is zero). I thought it might be interesting to highlight two of those methods that are a little more clever and generate these numbers in small numbers of operations. 
Linkage
 Textbook company Pearson sues Chegg for copyright infringement, for selling solutions to textbook homework problems (\(\mathbb{M}\)). On the one hand, forprofit cheaterenablers like Chegg are a cancer on higher education. On the other, the solution to a problem is generally a concept, not a text, and should not be something that can be locked up under copyright. So I don’t know who to root for?

Multilayer tiles
You’re probably familiar with the fact that you can draw a convex octagon with corners in an integer grid, fitting into a \(3\times 3\) square. It’s not regular, because its side lengths alternate between \(1\) and \(\sqrt 2\), but it has the same angles as a regular octagon and looks close enough to it for some purposes.

Which integer sequences form denominators of Egyptian fractions?
I have a new paper out: “Egyptian Fractions with Denominators from Sequences Closed Under Doubling”, in the Journal of Integer Sequences. (There should also be an arXiv version soon but despite my long association with arXiv they made me get an endorser before I could upload to the number theory category, slowing down my submission there.)

Linkage
 Does anyone but me find it odd that car tire sizes are measured in millimeters for width, inches for inner radius, and a dimensionless number expressed as a percentage for (difference between inner and outer radius)/width (\(\mathbb{M}\))? Imagine the fun if we tried to do solid geometry this way.

Congratulations, Dr. Maxwell!
I took part today in the successful dissertation defense of Will Maxwell, a student of Amir Nayyeri and Cora Borradaile at Oregon State University. Will has also visited me at UC Irvine, and I’ve worked with him on two papers, on lowstretch spanning trees and Hanoi graph treewidth. But his dissertation has a different focus, his work on generalizations of graph algorithms to higherdimensional topological spaces.

Linkage
 Finding a stationary point of a smooth function (as can be done, eventually, by gradient descent) is complete for \(\mathsf{PPAD}\cap\mathsf{PLS}\) (\(\mathbb{M}\), via) as Fearnley, Goldberg, Hollender, and Savani write in STOC 2021 best paper “The complexity of gradient descent”. Gradient descent finds local minima quickly in many cases, but can be slow to navigate shallow labyrinthine optimization landscapes; this result suggests that there are unlikely to be much better shortcuts.

Doomed apartments
The University of California, Irvine, maintains a sprawling faculty housing complex, University Hills, in which I live, in order to make homes affordable in what would otherwise be a very expensive part of the country. Most of it is singlefamily homes, owned by faculty on longterm land leases, but it also has several clusters of rental units. The oldest of these, and the nearest to my office, is unimaginatively named Las Lomas (“the hills” in Spanish, a frequent language for California place names).
subscribe via RSS