-
Linkage
- University of California to resume Elsevier talks after signing deals elsewhere (, via). We’ve been without access to newly-published Elsevier papers since last year (although old papers are still accessible) but it hasn’t affected me much. I hope the university negotiators continue to stand firm.
-
Linkage
-
An unflippable polygon
We have neither a polynomial-time algorithm for counting the polygonalizations of a point set, nor a proof that the problem is hard. Given this lack of knowledge, it is natural to ask whether the number of polygonalizations can at least be approximated efficiently. A well-known principle in this area states that approximate counting is almost the same as approximately-uniform random generation (an algorithm for one can often be converted to an algorithm for another). And a standard method for randomly generating combinatorial objects is to set up a Markov chain whose states are the objects and whose stationary distribution is the uniform distribution. A long-enough random walk in this Markov chain will then lead to a state that is approximately uniformly distributed. The hard part, though, is finding a Markov chain for which one can prove that “long enough” is only polynomially many steps; that is, it mixes rapidly.
-
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.
subscribe via RSS