• Dec 15, 2018

  Linkage

  This is my penultimate link roundup before I give up on Google+, rather than holding out for its rapidly-approaching demise.

• Dec 8, 2018

  General-position hypercube projections

  I recently posted about finding solutions to the no-three-in-line problem of finding large general-position subsets of grids, by using the probabilistic method or by throwing an integer linear program solver at the problem. Another potential method for finding solutions involves finding large general-position subsets in higher dimensions, where it’s easier (there’s more room to move the points out of the way of each other), and then projecting back down while being careful not to introduce any new collinearities.

• Dec 2, 2018

  Triply-Hamiltonian edge colorings

  Mark Jason Dominus recently made a blog post about the interesting observation that the regular dodecahedron can have its edges properly colored with three colors so that every two colors form a Hamiltonian cycle. Here’s another view of the same dodecahedral coloring:

• Nov 30, 2018

  Linkage

  In which I discover kramdown’s inability to pass raw vertical-bar characters to MathJax… (workaround: use \vert)

• Nov 15, 2018

  Linkage

  I’m gradually shifting weight to my Mastodon account and away from my doomed G+, but I hope to stick with both through the end of the year to provide a gradual transition. Today’s step: the Mastodon links go first.

• Nov 12, 2018

  Gurobi versus the no-three-in-line problem

  For the no-three-in-line problem, it has been known since the 1990s that $n\times n$ grids with $n\le 46$ have sets of $2n$ points with no three in line. Those results, by Achim Flammenkamp, were based on custom search software and a lot of compute time. I was curious to see how far one could get with more-modern but generic optimization codes, so this weekend I ran a little experiment.

• Nov 10, 2018

  Random no-three-in-line sets

  The UCI algorithms, combinatorics and optimization seminar this week featured a nice talk by local mathematician Nathan Kaplan on the no-three-in-line problem, which asks how many points you can choose from an $n\times n$ grid so that no three of them lie on a single line. For small $n$, such as the $10\times 10$ grid below, the answer is $2n$ (any more than that would lead to three points on a horizontal line) but it has long been conjectured that large enough grids have fewer points in their optimal solutions.

• Nov 1, 2018

  95 women of STEM

  As they did last February, Wikipedia’s WikiProject Women in Red just finished another successful monthly editathon for October, centered on Women in STEM. I didn’t quite make my goal of contributing 100 new articles, but I came close. Here are the new articles I added:

• Oct 31, 2018

  Linkage for Halloween

  • An upper bound for Lebesgue’s universal covering problem (G+, $\mathbb{M}$). Philip Gibbs makes progress on the smallest area needed to cover a congruent copy of every diameter-one curve in the plane, with additional contributions from John Baez, Karine Bagdasaryan, and Greg Egan. See Baez’s blog post for more.
• Oct 22, 2018

  Layered pathwidth and its obstacles

  There is a strong connection between the structural properties of the graphs in minor-closed families of graphs, and the properties of the graphs that are not in those families, their forbidden minors. A famous example of this is the proof by Robertson and Seymour (1986) that a minor-closed family of graphs has bounded treewidth if and only if at least one planar graph is not in the family. This is closely related to an earlier theorem of Halin on grid minors in infinite graphs, and Chekuri and Chuzhoy (STOC 2014) have proven a polynomial relation between the treewidth and the size of the excluded planar graph.

subscribe via RSS