Todays IPG seminar had Fritz Eisenbrand (the Disctete Opt chair, Math department EPFL) talking about Diameter of Polyhedra:Limits of Abstraction. I don’t think I followed the topic too well, but this is a share of what I understood.

The topic is about a convex geometric problem on the diameter of a polyhedra. The question of whether the diameter of a polyhedron is polynomial or not seemed to be a longstanding open problem. The largest diameter ${\Delta_{u}(d,n)}$ of a ${d}$ dimensional polyhedron with ${n}$ facets has known upper and lower bounds.

${n-d+\lfloor d/5 \rfloor \le \Delta_{u}(d,n) \le n^{\log d +1}}$.

The lower bound is due to Klee and Walkup and upper bound to Kalai and Kleitman. These bounds also hold good for combinatorial abstractions of the 1-skeleton of non-degenerate polyhedra (Polyhedron here is called non-degenrate). What Fritz and his colleagues have done is to look into the gap between these known lower and upper bounds. Apparently, the gap is wide and they have made some progress to get a super linear lower bound ${\Delta_{u}(d,n) \le \Omega\left(n^{3/2}\right)}$ if ${d}$ is allowed to grow with ${n}$.

The way they showed this bound is by establishing the bound for the largest diemeter of a graph in a base abstraction family. Let us say, the abstraction family of connected graphs be denoted by ${\mathcal{B}_{d,n}}$.The largest diameter of a graph in ${\mathcal{B}_{d,n}}$ is denoted by ${D(d,n)}$. They find that,${D(d,n) =\Omega\left(n^{3/2}\right)}$ and then using the fact that ${\Delta_{u}(d,n) \le D(d,n)}$, they conclude the bound ${\Delta_{u}(d,n) \le \Omega\left(n^{3/2}\right)}$

I have not had a chance to see their paper yet. I must say, the proof was not all that within my grab during the talk. However it appeared that it is based on some layering and combinatorics. He said some applications to covering problem, in particular disjoint covering design which I didn’t follow that well. Sometimes I get the feeling that I am a little dumb to grasp these ideas during a talk. I wonder whether others understand it very well on a first shot presentation. I have put it in my agenda (among the millions of other papers to read) to see through this problem and proof, one day! His presentation was very clear and legible though.