-
Linkage
- Hoffman’s packing puzzle, and its connection to the inequality of arithmetic and geometric means (). The one I have is not quite so colorful as the illustration for this new Wikipedia article. My father-in-law made it for me some 30 years ago; you can see it in a corner of the photo at this post. I don’t unpack it very often, though, because I lost track of the handwritten table of solutions that I made when I first got it and it’s quite difficult to re-pack.
-
Recoloring infinite paths
Suppose you have a uniformly random 3-coloring of a doubly-infinite path graph. This can be generated by choosing any one vertex, choosing any one of the three colors for it, and then propagating the coloring outwards from it, choosing one of the two available colors for each successive vertex. It’s convenient to imagine the three colors as being represented by the three numbers 0, 1, and 2 mod 3. Now perform the following process, repeatedly: change the color of every cell whose two neighbors both have the color that is one plus its color (mod 3). In other words, the middle vertex of a triple of vertices that is colored 1–0–1 changes to color 2, the middle vertex of 2–1–2 changes to 0, and the middle vertex of 0–2–0 changes to 1. What does this do to the coloring?
-
Reconfiguring 3-colorings
I talked briefly about how to get from one 3-coloring of a grid graph to another by changing one vertex color at a time, in a recent blog post about analogous problems for origami folding patterns. It turns out that this problem of reconfiguring 3-colorings has been treated in much greater generality in the 2007 doctoral dissertation of Luis Cereceda, “Mixing graph colourings”, as I discovered when I read the dissertation in the process of writing a new Wikipedia article on Cereceda’s conjecture, the conjecture that the space of -colorings of -degenerate graphs (under moves that change the color of one vertex at a time) has at most quadratic diameter. Here’s an illustration from the new article showing the space of 3-colorings of a path graph:
-
Linkage
- OMICS Group now charging for article withdrawals (): a new way for predatory journals to be predatory. It’s probably even legal: they have begun providing you with a service (reviewing of your paper) and told you up front what the charges are. Whether it’s ethical for scientific publishing is an entirely different question… So let this be a lesson to be careful where you submit, because unsubmitting could be difficult.
-
Halloween linkage
- Quasiperiodic bobbin lace patterns (, via). Veronika Irvine, Therese Biedl, and Craig S. Kaplan make aperiodic tilings in fiber arts.
-
Don't walk
Like many UC Irvine faculty I live in University Hills, a faculty housing complex associated with UC Irvine. It’s a great place to live: the prices are significantly lower than the surrounding area, I like my neighbors, and I love living so close to my office (ten minutes by foot) that I can walk to work instead of having to deal with the twin headaches of Southern California traffic and university parking.
-
MathJax 3 in Jekyll and Kramdown
The mathematical equations in my blog posts, and the ones you see on many other web sites, are formatted with MathJax, a JavaScript library that lets web developers write LaTeX formulas and turns them within your browser into nicely formatted math. The web pages of my blog are generated by Jekyll, a static web site generation system (meaning that it doesn’t go querying a database for its content, they are just web pages stored in files somewhere). I can write my posts in more than one format, but since the April 2017 LiveJournal apocalypse I’ve been writing them using kramdown, a system built into Jekyll for transforming marked-up text files into html ready for browsers to read and display. And so far mostly those different systems have been getting along really well together. Kramdown knows about MathJax and can handle equations in its input without trying to interpret their syntax as kramdown codes, Jekyll only needs me to modify a template somewhere so that my blog pages include an invocation of the MathJax library, and MathJax in your browser happily formats the equations in my posts. But recently, the MathJax people released MathJax version 3.0.0, and that doesn’t work so well with Jekyll and Kramdown. Despite some difficulty, I seem to have gotten them working again. So I thought it might be helpful to post here what went wrong and how I fixed it, in case others run into the same issues.
-
From one fold to another
If an origami crease pattern tells you where to put the folds, but not which way to fold them, you may have many choices left to make. A familiar example is the square grid. You can pleat (accordion-fold) the horizontal lines of the grid, and then pleat the resulting folded strip of paper along the vertical lines; the result will be that each horizontal line is consistently a mountain fold or a valley fold, but each vertical line has folds that alternate between mountain and valley. Or you could pleat the vertical lines first, and then the horizontal lines, getting a different folded state. There are many other choices beyond these two.
-
Linkage
- Spanning Trees with Low (Shallow) Stabbing Number () is the master’s thesis of Johannes Obenaus at the Free University of Berlin and ETH Zürich. The stabbing number of a tree is how many edges a line can cross. Any points in have a tree with stabbing number , useful in some data structures. The thesis includes a solution to Open Problem 17.5 of my book Forbidden Configurations in Discrete Geometry: removing points from a point set might cause the minimum stabbing number of a spanning tree to increase.
-
Hardness of planar Hamiltonian decomposition and linear arboricity
I was getting ready to start writing a paper proving that Hamiltonian decomposition and linear arboricity are both -complete for planar graphs of maximum degree four. But then I realized that there’s a trivial proof, based on known results:
subscribe via RSS