Linkage

For the new year, I’ve decided to try to get back into taking photos more frequently, and to make it lower-overhead I’m making individual Mastodon posts for some of them rather than writing a longer blog post for every batch of photos. So that’s why you see a couple of those images inline here.

• Fitting in (\(\mathbb{M}\)). Animated GIF of 124 disks packed (supposedly optimally) on a sphere and then steregraphically projected to the plane, by Clayton Shonkwiler.

• More animated GIFs of fluids with splashy frothy surfaces by Bruno Levy (\(\mathbb{M}\)). The fluids are modeled as power diagrams of systems of discrete points and simulated using methods from arXiv:1605.00568. See follow-up tweets for source code and long explanatory video.

• Lots of charts and plots of the growth of arXiv.org through 2018 (\(\mathbb{M}\)). In the area I moderate (cs.DS, algorithms and data structures) the number of preprints grew from 1597 in 2017 to 1767 in 2018, but this was a little below the 14% growth rate for arXiv overall, and was far outpaced by the rapid growth in cs.CV (computer vision), cs.LG (machine learning), and cs.CL (natural language processing).

• Matsya And The Great Deluge (\(\mathbb{M}\)). Street art from Fort Bragg illustrating an ancient Indian folk tale.

  

• Orange peels and fresnel integrals! Train sets! The urinal problem! (\(\mathbb{M}\)). Metafilter discovers Interesting Esoterica.

• Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) (\(\mathbb{M}\)). My favorite talk from the first day of SODA was “Extremal and probabilistic results for order types” (Jie Han, Yoshiharu Kohayakawa, Marcelo T. Sales, and Henrique Stagni). Its main results are
  1. the probability that a random point set has a specific order type is upper and lower bounded by functions of the smallest size of a grid containing the order type, and
  2. every nontrivial hereditary property of point sets has probability \(1/\exp\bigl(\Theta(n\log n)\bigr)\) of being true of random point sets.

• Iran arrests demographers, the latest target amid an escalating crackdown on academics and activists (\(\mathbb{M}\)). One of the two arrestees is an Iranian-Australian dual citizen; the other is director of the Iranian National Institute of Population Research. The apparent reason for the arrest is that their research contradicted a political narrative of Iranian hardliners according to which Iran is suffering a population crash and must increase fertility.

• The first sighting of one of my Wikipedia illustrations in a SODA talk goes to Michał Włodarczyk’s “Losing treewidth by separating subsets” (\(\mathbb{M}\)). It concerns removing few graph vertices to reach a subgraph with some desired property. If the optimal solution removes \(k\) vertices and graphs with the property have treewidth \(\le t\), then his solution removes \(O(k\log t)\) vertices and takes the same time as exactly solving \(O(\log n)\) subproblems of size \(O(t\log t)\).

• Michael Mitzenmacher blogs about SODA, SOSA, ALENEX, and ANALCO (\(\mathbb{M}\)). Michael was PC co-chair of SOSA, which I was skeptical about (shouldn’t all the best algorithms be simple?), but the session I attended favorably impressed me. Here’s an example, a simple algorithm for 2-approximating maximum genus oriented graph embedding: greedily remove 2-edge paths while preserving connectivity. \(\text{#paths} \le \text{max genus} \le 2\cdot\text{#paths}\).

• My SODA talk slides on finding laminar 3-vertex separators (\(\mathbb{M}\)). At the talk, someone asked about finding a maximum set of laminar 3-separators. It’s NP-complete: use Uehara’s “NP-complete problems on a 3-connected cubic graph and their applications” to find cubic planar graphs whose \(\le 3\)-separators are vertex neighborhoods (so laminar separators = neighbors of independent vertices) in which maximum independent set is hard.

• Spotted on the Cambridge University Press display table at SODA (\(\mathbb{M}\)):

  

• Marble Marcher (\(\mathbb{M}\), via). A game of guiding a marble across a dynamically changing fractal surface. The key is to use the recursive structure of the fractal to make a data structure that can handle the interactions between the marble and the fractal surface quickly enough to run in realtime.

• A list of (respectable) open access journals in mathematics (\(\mathbb{M}\)). JGAA and JoCG not yet listed but maybe soon?

• Wacław Szpakowski’s space-filling curve art (\(\mathbb{M}\)).

• The De Bruijn–Erdős theorem (\(\mathbb{M}\)): when all finite subgraphs of an infinite graph are \(k\)-colorable, so is the whole graph. Now a Good Article on Wikipedia.