• Linkage

  • 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

  • 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

subscribe via RSS