Linkage

Here’s a silly but probably new proof that the harmonic series diverges (\(\mathbb{M}\)). The expected number of comparisons used by randomized quicksort on an input of size \(n\) is at most \(2nH_n\), where \(H_n\) is the \(n\)th partial sum of the harmonic series (see Cormen et al, Introduction to Algorithms, Chapter 7). However, every comparison sorting algorithm requires at least \(\log_2n!=n\log_2n-O(n)\) comparisons, by the standard decision tree argument (Cormen et al, Section 8.1). Therefore, \(H_n=\Omega(\log n)\).

To be fair, the lecture hall I teach in this term doesn’t look quite so much like a prison if you enter by the main door at the top of the hall instead of the back door by the stage (\(\mathbb{M}\)).

Maximum flow and minimum-cost flow in almost-linear time (\(\mathbb{M}\)). New arXiv preprint by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva. It assumes integer capacities but that’s enough to get near-linear bipartite maximum matching, itself a breakthrough.

In early March, UC Berkeley was ordered to drastically cut enrollment under California’s strict environmental impact review laws (\(\mathbb{M}\)). In practice these laws are often used as a pretext for lawsuits to shake down or stop public developments for reasons unrelated to environmental impact (this is a heavily built-up area already; the impact is that it would have more students living in it and the people suing wanted to shake down UC for non-university-related low-income housing expansion). By mid-March, the state legislature had passed emergency legislation to temporarily sidestep the issue.

Another batch of Wikipedia Good Articles (\(\mathbb{M}\)):

• Fibonacci nim: subtraction game with a Fibonacci number based strategy.

• Kepler triangle: not the shape of the great pyramid of Giza, but one of its other properties inspired me to make the illustration below.

  

• Connected components of undirected graphs: saving this batch from complete frivolity.

New book in discrete geometry (\(\mathbb{M}\)): Polynomial Methods and Incidence Geometry, Adam Sheffer, Cambridge University Press. See Adam’s announcement and an early draft with missing chapters.

When I’ve been thinking recently about who I might know who is Ukrainian or Ukrainian-American, the first to mind was Andrea Danyluk, with whom I went to grad school. We lost touch later, but she had a long distinguished career at Williams College. Sadly, she died a few days ago (\(\mathbb{M}\)). The Computing Research Association chose her as the 2022 winner of their A. Nico Habermann Award for increasing diversity in computing research, shortly before her death.

The SET card game is not accessible to the color-impaired, its manufacturer shows no interest in fixing it or providing accessible alternatives, and is actively blocking any attempts by others to do the same. Sadly, this makes it unusable as a classroom activity.

What’s with Wikipedia and women? Things are changing, little by little, at the open-source encyclopedia (\(\mathbb{M}\)). New article from the American Society for Biochemistry and Molecular Biology mentions in passing my efforts creating articles on women in STEM and patrolling deletion discussions on them.

In pursuit of perfect pinnacles (\(\mathbb{M}\)). Why do spiky shapes form in nature, for instance in limestone and ice? Leif Ristroph, Jinzi Mac Huang, and Michael Shelley survey recent research in this SIAM News column.

Another Wikipedia Good Article, on an important rather than recreational topic: harmonic series (\(\mathbb{M}\)) on the divergent series

While cleaning it up I learned that the term “harmonic number” and notation for its partial sums comes from Knuth, and also that the “crossing the desert” puzzle, one of the standard examples for harmonic series, dates to long before the harmonic series itself.

Bad but interesting mathematical notation (\(\mathbb{M}\)). Minimal subsystems of arithmetic aside, Mark-Jason Dominus wrestles with the problem of finding an intuitive visual representation for expressions that combine a single associative operation with two mutually inverse unary operations.

Wikimedia foundation VP Maggie Dennis warns Wikipedia editors writing about the Russian invasion of Ukraine that they are likely to be doxxed (\(\mathbb{M}\), via), especially when their “activities are seen as opposing the Russian narrative of the war”. One assumes by the Russians, although she does not say that explicitly.

A wiki on combinatorial reconfiguration problems (\(\mathbb{M}\)). The main content at this point appears to be their extensive bibliography of papers on the topic, available both on-wiki and at a linked overleaf site. I can’t tell whether the wiki or overleaf version of the .bib file is supposed to be primary, though.