Linkage

If you’re coming to Southern California for STOC (June 25–29 in Los Angeles), you should stay through the end of the last day for the Workshop to Celebrate Vijay Vazirani’s Contributions to Theoretical Computer Science. See also the detailed schedule at the workshop web site.

The Hamiltonian puzzle (G+, more G+ comments). Fill 26 squares with the letters A–Z so that each two consecutive letters land in adjacent squares. Based on the 26-Fullerene graph; see Ed Pegg’s explanation of the underlying mathematics.

Magforming the Johnson Solids. Richard Elwes steals his kids’ toys and has some geometric adventures with them.

Solution to the random sorting network conjectures (G+). “Sorting network” here really means a wiring diagram or allowable sequence of permutations — almost the same thing as a pseudoline arrangement or a rhombic tiling of a regular polygon. Randomly chosen sorting networks are now proven to behave nicely. But as Gil says towards the end of his post, one of the major questions about their non-random behavior — how many crossings can occur at the middle level of the diagram — a pseudoline version of the \(k\)-set problem from discrete geometry — remains open.

Hansel and Gretel and algorithms (via). Short webcomic.

Éva Tardos will be this year’s Sonia Kovelevsky lecturer, at the July SIAM meeting.

The Witch of Angmar Endor Agnesi. In a paper from 2012, J. McKenzie Alexander asks the following (trick) question. We choose uniformly at random a line through the point \((1,1)\) in the Euclidean plane; suppose this line hits the horizontal axis at the point \((x,0)\). Based on this random value you get \(x\) dollars: if \(x\) is positive you win but if it is negative you have to pay \(-x\). How much should you pay up front for this to be a fair bet? The shape of the probability distribution for this experiment is given by the Witch. I posted the link as a way to beg readers to help me find a reference to a different fact about the witch, involving its osculating circle, but then I found it myself.

\(\forall \exists \mathbb{R}\)-completeness and area-universality. For some time now the first (existential) level of the theory of the real numbers has been very fruitful in classifying the complexity of problems in computational geometry and geometric graph theory. This paper from WG 2018 starts looking at the second level: an alternation between two levels of quantifiers. They conjecture that whether a planar graph has straight-line drawings of all possible face areas (that is, whether it is area-universal) is complete for this second level.

Could blockchain have solved the mystery of the romaine lettuce E. coli outbreak? (G+). Walmart has started using blockchain, not for cryptocurrency, but to secure and trace the provenance of the food it sells. The technology reduces the time to figure out where something originally came from (useful information in disease outbreaks, as the headline suggests) from roughly a week to seconds. But in the comments, Brian Slesinsky asks the age-old question: how is this any better than a standard distributed database?

Fun with orthoprojections! (G+, via). Joel David Hamkins asks kids to figure out how blocks are stacked together, from multiview projections. It’s also an amusing puzzle for adults.

A wartime aberration in copyright law caused German publications to become copyright-free in the US. The result was a significant increase in how highly cited they became. So if (like I think most academics) you care more about your research being read and cited than about someone else making a profit from it, you should prefer open access publication. See also the original research report by Barbara Biasi and Petra Moser and its summary.

The tennis ball theorem. The seam of a tennis ball (like that of a baseball) divides the surface into two pieces of equal areas. Whenever a smooth curve on a sphere does this, it has at least four inflection points (intuitively, points where it changes from turning left to turning right…but if it goes straight for a while, all those points also count as inflections). New article on Wikipedia.

Alphabetical name ordering is discriminatory and harmful to collaborations (via). Maybe, but that doesn’t mean we have to emulate other disciplines’ habit of encrypting other information in a noisy and low-bandwidth channel. See the “via” link for an interesting discussion of this issue and how it might affect mathematical subjects. Along with comments on the quality of the study, they include whether and how randomization can be made to work, and if so how to convince outsiders not to impute anything from author ordering.