# SoCG day 2

The second day of SoCG featured the first of two invited talks, a survey by Paco Santos (celebrating the 20th anniversary of his first SoCG) on the Hirsch conjecture and related questions concerning the diameter of polytopes. His own famous work disproving the conjecture is based on "spindle" polytopes (duals of prismatoids) in which two vertices are adjacent to all others; for three and four dimensions, the distance between these two vertices is at most the dimension, but that's not true for five-dimensional polytopes, and the counterexamples can be used to construct higher dimensional polytopes whose diameter is larger than the Hirsch bound. He also outlined a nice proof of the Hirsch conjecture for the duals of "flag" polytopes (simplicial polytopes whose graphs have no non-facial cliques), by giving the polytope boundary an alternative geometry in which each simplex is replaced by the intersection of an orthant with a sphere and applying a lemma of Gromov on the geodesic convexity of the resulting spaces.

I also particularly liked a talk by Piotr Indyk on a paper by James Lee and Daniel Poore (neither of whom could be here) concerning how much distortion you might need (in the worst case) to embed the shortest path metric of a weighted graph into an \( L_1 \) metric, a problem closely related to approximation of multicommodity flow. It's long been conjectured that the planar graphs have bounded distortion and more strongly that the graphs in a given family \( F \) have bounded distortion if and only if \( F \) has a forbidden minor. Among other things, this would imply that having bounded distortion is preserved by taking clique-sums (with bounded clique size) but this is only known for 1-clique-sums (for which it's trivial). This paper makes partial progress on the case of 2-clique-sums, or, if you prefer, SPQR trees. It defines a variant of distortion in which one pair of vertices must have their distance represented exactly, which combines better in 2-sums, and shows that the worst-case of the variant distortion for a given graph or graph family is asymptotically the same as the standard distortion for 2-sums of the graph or graph family. Among other things this implies that 2-sums of graphs of bounded size have bounded distortion, but it's not even known whether planar 3-trees have bounded distortion. So it seems that there's still plenty to do in this area.

Today was also the business meeting. I'll have a more detailed report later (as secretary of the SoCG steering committee I took minutes, although I didn't try to copy down everything that was already on the presentation slides) but for now here are some highlights: Overall attendance, submissions, and acceptances are in line with previous years, but student attendance is up, probably because of the very low student fees. Victor Alvarez and Raimund Seidel won the best paper award for their work on counting triangulations; the best student presentation will be decided tomorrow. This year's videos are all on YouTube. In 2014 we will be in Kyoto; in 2015, in Eindhoven (the Braunschweig gang's plan to advance their competing bid by getting Bettina drunk the previous evening so she couldn't prepare her slides was unsuccessful, as she spent most of her presentation talking about beer, which evidently appealed to the beerless audience), and in 2016, likely in the US somewhere together with STOC. And ACM is being more cooperative than it had been (particularly in allowing "in cooperation" status for non-US instances of the conference) as a consequence of which we'll be holding a third referendum on ACM and SoCG in October, after an internet discussion at makingsocg.wordpress.com.