Applying for a job in France, part 2

For CNRS, good informal advice can be found in this text written by Bruno Durand a few years ago: here. In French, more recent information (for the year 2012) is here and there, with pointers to the current two sections in computer science, 6 and 7.

The diameter of the flip graph of triangulations

Consider the graph whose nodes correspond to triangulations of a convex n-vertex polygon and whose edges correspond to a "flip" of the diagonal edge between two adjacent triangles of the triangulation. In 1988 Sleator, Tarjan and Thurston proved, with an argument using hyperbolic geometry, that that graph has diameter 2n-10 for n large enough. Since then, finding a purely combinatorial proof has been an open problem.

A few years later, Thurston suggested to me a combinatorial approach based on a linear programming relaxation and a lower bound proved by writing the LP dual and exhibiting a dual feasible solution. I implemented his suggestions and the resulting draft was somewhat hastily submitted to a conference, from which it was rejected. Disappointed by the lack of interest of the community evidenced by that rejection, I put the manuscript in the bottom of a drawer and tried to forget about it.

But somehow, word got out, and every year or two I got a request for the manuscript. Some PhD student somewhere would want to work on the question, heard that I had worked on it, and contacted me about it. I systematically sent them the draft wile disclaiming the result since I had not proofread it and neither had anyone else. Eventually, I decided that I must resolve this and, last year, asked a student at Brown to look into it. He tried to read the manuscript with me, reconstructing the ideas, but got bogged down, as I had several times before, writing out the dual feasible solution. Undeterred, he proceeded to code it up, and then discovered that the construction was actually incomplete. I had left some dual variables undefined, and it was not clear how to define them while respecting all the constraints. He spent a good amount of time on it, but could not resolve it. It now appeared that the approach was problematic.

So, I was excited to hear a couple of months ago that Lionel Pournin found a purely combinatorial proof. Today he gave a seminar, and here are the slides. So simple ! In one hour at a slow pace, we got all the ideas and most of the proof details. Anyone junior level undergraduate could read it. And now, that long-standing open problem is finally resolved, with elementary means ! Amazing.

Anyone interested in the problem really should spend a few minutes pouring over those slides.