# SoCG day 4

Benjamin Burton always gives entertaining talks and the two he gave on Thursday morning were no exception. The first was on finding an essential surface for a given knot: this is a 2-manifold that doesn't touch the knot at all, isn't just a torus parallel to the knot, and doesn't have any useless topology (technically, it must be incompressible). For a conference on theoretical computer science, his results had the interesting property of making negative progress on reducing the gap between theory and practice: the problem was and still is doubly exponential in the worst case, but he showed that it can be solved in practice, at least for all knots of a dozen or fewer crossings and some with up to 20. The key tool he used to make this work, crushing, was the subject of his second talk: this is an operation that splits a 3-manifold along a surface and then contracts the two copies of the split surface. It can change the topology, but only in limited and easy-to-detect ways (at least, when the surface is a disk or sphere and the 3-manifold meets some technical conditions). He presented a simple new proof of this fact based on serializing the topology changes made by a crushing operation into a sequence of simple collapses.

The other one of Thursday's talks that caught my attention was by Pat Morin, on robust spanners (graphs that contain short paths between pairs of points in a geometric space even after being somewhat damaged). Usually this robustness is measured in terms of the vertex connectivity of the graph: how many vertices can be deleted while still containing (short) paths between all remaining vertices. However Pat argued that this does not adequately capture, for instance, the difference in connectivity between a square grid and a ladder. Both are 2-connected, but the only way to disconnect a square grid by deleting two vertices is to cut off one vertex at a corner, while the ladder has many more significant 2-separations. Instead he defined a graph to be \( f(k) \)-robust if the removal of k vertices can disconnect only \( f(k) \) vertices from the rest of the graph; for instance, the square grid is \( O(k^2) \)-robust. He showed tight bounds for robust spanners in one dimension and less-tight bounds in higher dimensions.

Completing both the conference and my roundup of the conference was the announcement of the best student presentation award. I had been wondering how the award ballots (a score for each presentation in the range from 1 to 10, plus comments) would be tallied; the answer was that the award committee tried several choices, including averaging the scores and counting first-place scores, but were not able to settle on a single winner. Instead they gave two awards, to João Paixão for his work on parametric discrete Morse theory and to Luis Barba for his work on bichromatic matching. Sadly, I seem to have missed both talks so can't summarize their work in any more detail. Congratulations to both winners, and thanks to all for an excellent conference.