+
Today's new Wikipedia articles: Hanner polytopes and Kalai's 3d conjecture.The 3d conjecture states that a centrally symmetric d-dimensional polytope must have at least 3d faces (of all dimensions including the d-dimensional polytope itself as a face but not including the –1-dimensional empty set). For instance, the cube has 8 vertices, 12 edges, 6 squares, and 1 cube as faces; 8 + 12 + 6 + 1 = 27 = 33.The Hanner polytopes include the cubes, are closed under Cartesian products and duality, […]
+
I have another new preprint: Combinatorial Pair Testing: Distinguishing Workers from Slackers (with Mike Goodrich and Dan Hirschberg), arXiv:1305.0110, to appear at WADS.The story in this one is that we have students in a pair programming class, some of whom will do the work and some of whom will let their partner do all the work. But if two of the slackers get paired together, we can catch them, because then nobody does the work. So how do we choose partners for the assignments to be sure of […]
+
If you make a graph with a vertex for each permutation of length n, and an edge for two permutations related by a swap of adjacent values, it looks like this:It has some nice properties: it's a Hamiltonian partial cube with isometric dimension n(n − 1)/2, and the graph of an n − 1-dimensional polytope (the permutohedron) There's an easy way to compute distances in this graph (count the inversions). But what if we consider a subset of the permutations, the ones […]
+
I have a new preprint out with Michael Bannister and Sergio Cabello, "Parameterized complexity of 1-planarity", arXiv:1304.5591, to appear at WADS.A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge; the hope is that this style of drawing can be more versatile than completely forbidding crossings while still being constrained enough to keep the drawings readable. However, finding a 1-planar drawing is NP-hard. Our goal in this paper was to explore restrictions […]
+
The list of accepted papers for WADS 2013 is out. No abstracts, just titles and authors, but some of the papers can be found online elsewhere as preprints. (Not mine yet, but soon.)
