• ## When does 2SAT have an integral relaxation?

In the 2-satisfiability problem, or 2SAT, the input is a system of constraints between pairs of Boolean variables, and the problem is to find a truth assignment satisfying all the constraints. Although the usual formulation writes the constraints as disjunctions (Boolean or), it’s convenient and equivalent to use implications instead, where each side of an implication can be either one of the variables or its negation. If you encode the variables as numbers, with $1$ for true and $0$ for false, then the negation of a variable $x$ is $1-x$ and the implication $x\rightarrow y$ can be encoded as the linear inequality $x\le y$. If we forget the restriction that the values are $0$ or $1$, this system of inequalities defines a convex polytope, which can be thought of as a relaxation of the given 2SAT problem. Each solution to the 2SAT problem corresponds to a vertex of this polytope but there might be other vertices as well, with fractional coordinates. We don’t want those; it’s more useful to have a polytope all of whose coordinates are integers, coming from solutions to the underlying 2SAT problem. When does this happen (without adding extra inequalities)?

• ## Counting grid polygonalizations

A polygonalization of a point set is a simple polygon having all the points as its vertices. Another way to think about it is that it’s a non-crossing Hamiltonian cycle in a complete geometric graph. My recent work on the hardness of counting polygon triangulations was motivated in large part by the problem of counting polygonalizations. Counting polygonalizations should also be hard, but I don’t know how to prove it, and I was hoping that proving other similar problems hard might either lead to more insights or at least provide something to prove a reduction from.

• ## Asymptotics of Recamán's sequence

Recamán’s sequence is a sequence of natural numbers in which the zeroth number is zero and the $n$th number adds or subtracts $n$ from the previous number, subtracting if that would lead to a new value and adding otherwise. It was popularized in a 2018 Numberphile video that showed both an interesting visualization of it using nested circles and a spooky piano composition obtained by using its values as notes.

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 $(d+2)$-colorings of $d$-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: