Milman–Szarek geometric lemma for easily covered polytopes

Let r(0,1]r\in(0,1]. A polytope P=conv(V)RnP=\operatorname{conv}(V)\subset\mathbb{R}^n contains rB2nrB_2^n when rB2nPrB_2^n\subset P, and N(P,B2n)N(P,B_2^n) denotes the covering number of PP by translates of the Euclidean unit ball. Milman–Szarek conjecture. There exists c=c(r)c=c(r) such that for every nNn\in\mathbb{N} and every polytope P=conv(V)RnP=\operatorname{conv}(V)\subset\mathbb{R}^n containing rB2nrB_2^n,

N(P,B2n)<ecn    V>ecn.N(P,B_2^n)<e^{cn}\implies |V|>e^{cn}.

In particular, the covering number and the number of vertices cannot both be subexponential in the dimension. Milman and Szarek showed that this conjecture implies the duality conjecture concerning covering numbers; although that duality conjecture has since been proved, the present conjecture remains open.

Sources & referencesView supporting material

Primary source

Dan I. Florentin and Tomer Milo, “On the Many Faces of Easily Covered Polytopes”, arXiv:2410.17811 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.