Everyone who is interested is welcome to attend this CWI public lecture of Stefan.
Abstract: Let P be any polytope contained in [0,1]^n and S be the set of
its integer points. We prove that P has bounded Chvátal-Gomory rank
(CG-rank) provided that S has bounded pitch and bounded gap, where the
pitch is the minimum integer p such that all p-dimensional faces of [0,1]^n
have a nonempty intersection with S, and the gap is a measure of the size
of the facet coefficients of conv(S). Let H[S] denote the subgraph of the
n-cube induced by the vertices not in S. We prove that if H[S] does not
contain a subdivision of a large complete graph, then both the pitch and
the gap are bounded. By our main result, this implies that the CG-rank of
R is bounded as a function of the treewidth of H[S]. This generalizes a
recent theorem of Cornuéjols and Lee (2016), who proved that the CG-rank is
always bounded if the treewidth of H[S] is at most 2. This is joint work
with Yohann Benchetrit, Samuel Fiorini and Tony Huynh.
