Milman–Szarek geometric lemma for easily covered polytopes

About 2 years old · traced to

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 rB2n⊂PrB_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 n∈Nn\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.

References

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.