-
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 for true and for false, then the negation of a variable is and the implication can be encoded as the linear inequality . If we forget the restriction that the values are or , 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)?
-
Linkage
- Recently read: Robert Bosch’s Opt Art: From Mathematical Optimization to Visual Design, as reviewed in The Math Less Traveled (). Some others that are less mathematical: Susan Phillips The City Beneath (the rare book about graffiti where the words are more interesting than the photos); Kelly & Zach Weinersmith’s Soonish; Spectrum 26: The Best in Contemporary Fantastic Art.
-
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.
-
Year-end linkage
- Reign in graphs (). Interesting collection of 3d models of graphs
-
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 th number adds or subtracts 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.
-
Linkage
-
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.
subscribe via RSS