• A weak ordering (\(\mathbb{M}\)) is just a linear order with ties. On \(n\) items, there are obviously at least \(n!\) of them (don’t use ties); here’s a simple combinatorial proof that there are at most \((n+1)^{n-1}\), also provable using parking functions (below). In the complete graph \(K_{n+1}\), choose one vertex as root. By Cayley’s formula, it has exactly \((n+1)^{n-1}\) spanning trees. Each spanning tree can be used to weak order the non-root vertices by their distance from the root. Each weak order on non-root vertices arises from a rooted spanning tree in this way by setting the parent of each non-root vertex to be any of its immediate predecessors, or the root if it has none. Anyone happen to know whether this proof has been published anywhere?

  • The bitter lesson (\(\mathbb{M}\)): domain knowledge initially helps in machine learning but then just gets in the way.

  • Is it just me or has Google Scholar’s coverage become spottier recently (\(\mathbb{M}\))? I used to think of Google Scholar as the one-stop shop for full-text queries of the scientific literature: enter a double-quoted phrase and it would find everything there was to be found (except maybe when there was so much to find that you could not go through it all). But lately more and more I’ve been noticing instances where Google Scholar was unable to find publications that it should have been able to find, and that could be found elsewhere.

    A case in point: in a recent post, @divbyzero asked about the origin of a limerick about Klein bottles, supposedly attributed to Leo Moser, and citing a 1963 Gardner “Mathematical Games” column. Searching Google Scholar for the first line of the limerick, restricted to pre-1980 publications, found nothing of interest. Curious what Gardner had said about it, and knowing his columns were available on JSTOR, I searched for the same line on JSTOR. It found not only his 1963 column, but two other relevant references, another one from Scientific American in 1950 and one from the American Mathematical Monthly in 1973, that had been nowhere to be seen when I searched Google Scholar.

    Has this been happening all along and I’m only now starting to notice the problem? Or is this sort of omission (as my impression suggests) a recent deterioration of Google Scholar, within the last few years?

  • The dumbest election recount ever Chris Staecker, Youtube, \(\mathbb{M}\)), or, why instant runoff voting makes it very hard to test whether an election result was so close that a recount is worthwhile. (But not in this real-world instance, where it definitely was not worthwhile.)

  • Today in git tips & tricks (\(\mathbb{M}\)): how to make your Mac-using collaborators unable to use your git repository. Just make it contain two files with names that differ only in their capitalization! For extra confusion, have them be different files with different uses rather than merely being different versions of the same file.

  • Every two triangulations of the same polygon have a common stellar subdivision (\(\mathbb{M}\)). Blog post by Igor Pak and preprint by Pak and Karim Adiprasito. Here triangulations are allowed to have vertices interior to the polygon. A stellar subdivision is what you get by repeatedly performing two subdivision operations that split triangles into three triangles or pairs of triangles into four triangles. The actual new result is much more general, applying to analogous subdivisions of simplicial complexes in \(\mathbb{R}^d\). It has an application to common blowups of toric varieties (“Oda’s conjecture”); see the preprint for details. Igor’s blog post also discusses another new preprint, “Monotone parameters on Cayley graphs of finitely generated groups”, with Martin Kassabov.

  • Robin Houston packs quarter-circles into a square, or, if you like, oatcakes into a tin.

  • New Wikipedia article: parking function (\(\mathbb{M}\)). These are sequences of \(n\) numbers from 1 to \(n\) (like a permutation), but allowing repetitions and omissions. A sequence is a parking function if, after sorting it, the \(i\)th number in the sorted sequence is at most \(i\). (Thus, one can quickly recognize parking functions using bucket sorting.)

    You might think that I discovered this gap in Wikipedia when covering linear probing hash tables recently in my data structures course. Parking functions describe the hash functions that pack \(n\) keys into a hash table with \(n\) cells, using linear probing without wraparound, and can help analyze the behavior of smaller blocks of cells in linear probing. But actually the genesis of the new article was the post above using Cayley’s spanning tree formula to show a simple upper bound of \((n+1)^{n-1}\) on weak orderings. Searching for references to include this bound in Wikipedia, I found arXiv:2305.15554, which credits the following observation to Williams College undergraduate Kimberly P. Hadaway: the number of “unit interval” parking functions for which (when used for hashing in the same way) each key is mapped either to its assigned hash value or to the next cell in the hash table is exactly the number of weak orderings. (The number of unrestricted parking functions is exactly \((n+1)^{n-1}\).) The equivalence between unit interval parking functions and weak orderings has a simple bijective proof: order the keys that are mapped to their own hash value by their position, and make each remaining key be tied with its predecessor in the hash table.

    The new article is very incomplete. Much expansion is possible.

  • Martin Bullinger on Vijay Vazirani’s four-decade quest to fully prove correctness of the Micali-Vazirani matching algorithm (\(\mathbb{M}\)).

  • An alphabet of heptagons (\(\mathbb{M}\), via), many Reuleaux heptagon coins from different nations, and a few other seven-sided ones that are not Reuleaux.

  • I wouldn’t have expected to see the idea of gliders in cellular automata inspiring research on the Hamiltonicity of symmetric graphs (\(\mathbb{M}\)), but: Gil Kalai reports on a STOC 2023 paper by Merino, Mütze, and Namrata proving that all Kneser graphs except the Petersen graph are Hamiltonian.

  • Open problems on twin-width (\(\mathbb{M}\)). Twin-width is a graph parameter related to treewidth Edouard Bonnet and others at ENS Lyon have been leading the research effort on this topic, and Bonnet has put together both links above. I’m not sure how up-to-date this is but as far as I know at least the first two problems (FPT approximation and an explicit construction of bounded-degree graphs with unbounded twin-width) are both still open and important to this topic.

  • El País on the questionable self-citation habits of AI/cybersecurity researcher Juan Manuel Corchado (\(\mathbb{M}\), via, see also), the sole candidate for rector at the University of Salamanca.

  • Dan Piker finds a possibly-new triply periodic minimal surface based on the hexastix packing of four parallel families of hexagonal prisms in space.

  • ChatGPT runs into European regulations that all companies that maintain personal information on EU citizens give full access to the data when requested and provide redress for incorrect data (\(\mathbb{M}\)).