Extension complexity of (convex) polygons

Importance: Medium ✭✭
Subject: Geometry
» Polytopes
Recomm. for undergrads: no
Posted by: DOT
on: August 13th, 2011

The extension complexity of a polytope $P$ is the minimum number $q$ for which there exists a polytope $Q$ with $q$ facets and an affine mapping $\pi$ with $\pi(Q) = P$.

\begin{question} Does there exists, for infinitely many integers $n$, a convex polygon on $n$ vertices whose extension complexity is $\Omega(n)$? \end{question}

The extension complexity of a polytope is bounded from above by its number of vertices. Thus, a convex polygon with $n$ vertices has extension complexity $O(n)$.

Some regular convex polygons have extension complexity $O(\log n)$ [BTN].

A convex polygon whose points are drawn randomly on a circle has extension complexity $\Omega(\sqrt n)$ with probability one (follows from [FRT]).

The question asks for the maximal extension complexity of a convex polygon.

A strongly related question is the following.

\begin{question} What is the extension complexity of an $n$-vertex convex polygon whose vertices are drawn randomly on a circle? \end{question}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

*[BTN] Ben-Tal, A and Nemirovski, A. On polyhedral approximations of the second-order cone. Math. Oper. Res. 26:2 193-205 (2001)

[FRT] Fiorini, S. and Rothvoss, T. and Tiwary, H.R. Extended formulations of polygons. arXiv:1107.0371

* indicates original appearance(s) of problem.