Sublinear extensions of polygons
Yaroslav Shitov
%We show that every convex $n$-gon is the image of a polytope with $o(n)$ facets under a linear projection. %We show that every convex $n$-gon can be described with $o(n)$ linear inequalities up to a linear projection. Every convex $n$-gon is a projection of a polytope with $o(n)$ facets.
1412.0728.tex
\documentclass{amsart}
\sloppy

\newtheorem{thr}{Theorem}[section]
\newtheorem{lem}[thr]{Lemma}
\newtheorem{cor}[thr]{Corollary}
\newtheorem{pr}[thr]{Proposition}
\newtheorem{ob}[thr]{Observation}

\theoremstyle{definition}
\newtheorem{defn}[thr]{Definition}
\newtheorem{conv}[thr]{Convention}
\newtheorem{ex}[thr]{Example}
\newtheorem{quest}[thr]{Question}
\newtheorem{prob}[thr]{Problem}

\theoremstyle{remark}
\newtheorem{remr}[thr]{Remark}

\numberwithin{equation}{section}

\def\om{\{1,\ldots,m\}}
\def\on{\{1,\ldots,n\}}
\def\R{\mathbb{R}}
\def\Rp{\mathbb{R}_+}
\def\B{\mathcal{B}}
\def\P{{\mathcal P}}
\def\I{{\mathcal I}}
\def\Pr{{\mathbb P}}
\def\S{{\mathcal S}}
\def\A{{\mathcal A}}
\def\Rr{{\mathcal R}}
\def\D{{\mathcal D}}
\def\G{{\mathcal G}}
\def\op{\oplus}
\def\ot{\otimes}

\def\Supp{\operatorname{Supp}}

\newcommand{\abs}[1]{\lvert#1\rvert}

\begin{document}

\title{Sublinear extensions of polygons}

%    Information for first author
\author{Yaroslav Shitov}
\address{National Research University Higher School of Economics, 20 Myasnitskaya Ulitsa, Moscow 101000, Russia}
%\curraddr{}
\email{yaroslav-shitov@yandex.ru}

%\subjclass is required.
\subjclass[2000]{52B05, 52B12, 15A23}
\keywords{Convex polytope, extended formulation, nonnegative matrix factorization}

\begin{abstract}
%We show that every convex $n$-gon is the image of a polytope with $o(n)$ facets under a linear projection.
%We show that every convex $n$-gon can be described with $o(n)$ linear inequalities up to a linear projection.
Every convex $n$-gon is a projection of a polytope with $o(n)$ facets.
\end{abstract}

\maketitle

\section{Introduction}

A \textit{polytope} $P\subset\R^n$ is a convex hull of a finite subset of $\mathbb{R}^n$.
A \textit{linear extended formulation} (or \textit{extension}) of $P$ is a polytope $Q\subset\R^d$ such that $P$ can be obtained
from $Q$ as an image under a linear projection from $\R^d$ to $\R^n$. The \textit{size}
of extended formulation is the number of facets of $Q$. The \textit{extension complexity}
of a polytope $P$ is the smallest size of any extended formulation of $P$, that is, the minimal
possible number of inequalities in the representation of $Q$. Extended formulations of small size
are interesting in combinatorial optimization because they allow to reduce the complexity of
linear programming problems useful for numerous applications~\cite{CCZ, GPT}.

Extended formulations proved to be a powerful tool in combinatorial optimization after the 1991
paper by Yannakakis~\cite{Yan}, and they attract a significant amount of attention in present time.
However, there are many basic questions on extended formulations that remain unsolved. For instance,
consider a convex polygon, the simplest polytope from combinatorial point of view.
%Which values the extension complexity of it can take? In other words,
How small and how large the extension complexity of a convex $n$-gon can be? The first part of this
question has been answered in~\cite{B-TN}, it has been proved that the extension complexity of regular
$n$-gon is $\Theta(\log n)$. The question of worst-case complexity is still unsolved;
the following version of this question has been mentioned in~\cite{BP} as one of important
problems of extended formulations theory.

\begin{prob}\label{probiscomplexitylinear}
Does a convex polygon need a linear number of inequalities in any linear representation in the worst case?
\end{prob}

A thorough investigation of extensions of polygons has been undertaken in~\cite{FRT}, where
the worst-case extension complexity of $n$-gon has been bounded from below by $\Omega(\sqrt{n})$.
Actually, it has been proven that every \textit{generic} $n$-gon (that is, a polygon whose vertex
coordinates are algebraically independent over $\mathbb{Q}$) has extension complexity
at least $\sqrt{2n}$. The best upper bound for the worst-case extension complexity known so far
was $(6n+6)/7$, as shown in~\cite{ShiCom}. These papers left Problem~\ref{probiscomplexitylinear}
open, as well as~\cite{GG, PP}, which present geometric techniques of attacking the problem,
and~\cite{PW}, which shows that \textit{hidden vertices} are necessary to construct optimal extensions
of convex polygons. Actually, Problem~\ref{probiscomplexitylinear} has been open even for a more
general class of \textit{semidefinite formulations}, which have more expressive power than linear
formulations~\cite{GRT2}.

A linear algebraic characterization of extended formulations has been given by Yannakakis in~\cite{Yan}.
Recall that the \textit{nonnegative rank} of a \textit{nonnegative matrix} $M$ (that is, a matrix whose
entries are nonnegative) is the smallest $k$ such that $M$ is a sum of $k$ nonnegative rank one matrices.
Assume a polytope $P\subset\R^n$ %(with $v$ vertices and $f$ facets)
is defined by conditions $c_f(x)\geq \beta_f$, where $f$ runs over all facets of $P$, and every $c_f$
is a linear functional on $\R^n$. The entries of a \textit{slack matrix} of $P$ are defined by $S^f_v=c_f(v)-\beta_f$,
where $v$ runs over all vertices of $P$. It is not hard to see that the rank of $S$ is the dimension of $P$; the Yannakakis'
result states that the nonnegative rank of $S$ equals the extension complexity of $P$, see also Corollary~5 of~\cite{GG}.
These results provide a reformulation of Problem~\ref{probiscomplexitylinear}, which has been studied
in~\cite{BL, Hr, LC, VGGT} in linear algebraic terms but remained open.

In this paper we give a negative answer for Problem~\ref{probiscomplexitylinear} by showing that every convex $n$-gon
admits an extended formulation with $o(n)$ facets. As a corollary, we prove that the nonnegative rank of a nonnegative
rank three $m\times n$ matrix is $o(n)$.  Also, we provide an open set of convex $n$-gons which have extension complexity
$O(\sqrt{n})$, which shows that an $\Omega(\sqrt{n})$ lower bound for extension complexities of all generic $n$-gons,
obtained in~\cite{FRT}, cannot be improved.

\section{Preliminaries}

The following notation is used throughout our paper. We denote by $S_i^j$
the number located in the intersection of $i$th row and $j$th column of matrix $S$.
A submatrix of $S$ formed by rows with indexes from a set $R$ and columns with indexes
from $C$ will be denoted by $S[R|C]$. We refer to either a row or a column of a matrix
as a \textit{line} of it. We sometimes write $\exp_ab$ instead of $a^b$ to avoid
complicated expressions in upper indexes. By $\operatorname{conv}A$ we denote the convex
hull of a set $A$.

Let $h$ be a positive real and $r=(r_1,\ldots,r_n)$ a sequence of real numbers. We say
that $r$ is $h$\textit{-increasing} (or $h$\textit{-decreasing}) if $h r_i\leq r_{i+1}$
(or $r_i\geq h r_{i+1}$, respectively) holds for any $i$. A sequence is $h$-\textit{monotone}
if it is either $h$-increasing or $h$-decreasing.

For any three points $u_1,u_2,u_3\in\mathbb{R}^2$, we denote
by $\Delta(u_1,u_2,u_3)$ the oriented area of the parallelepiped
spanned by vectors $\overrightarrow{u_2u_1}$ and $\overrightarrow{u_2u_3}$.
Assume $v_1,\ldots,v_{n+1}\in\mathbb{R}^2$ and $v_{n+1}=v_1$; we say that $(v_1,\ldots,v_n)$ is
a \textit{proper sequence} if $\Delta(v_{1},v_{2},v_{3})>0$ and, for every $j$, the segment
$\operatorname{conv}\{v_j,v_{j+1}\}$ is an edge of $\operatorname{conv}\{v_1,\ldots,v_n\}$.
We define \textit{the slack matrix} $S$ of $(v_1,\ldots,v_n)$
by $S_i^j=\Delta(v_i,v_j,v_{j+1})$. The result of Yannakakis
states that the nonnegative rank of $S$ equals the extension complexity
of $\operatorname{conv}\{v_1,\ldots,v_n\}$. The following two propositions will be helpful in what follows.


\begin{lem}\label{lemeasy}
If $P_1$ and $P_2$ are convex polytopes, then the extension complexity of
$\operatorname{conv}\{P_1\cup P_2\}$ does not exceed the sum of those of $P_1$ and $P_2$.
\end{lem}

\begin{proof}
This is a special case of Proposition~2.8 of~\cite{GPT}.
\end{proof}

\begin{lem}\label{lemside}
Assume $w\in\mathbb{R}^2$ and $v=(v_1,\ldots,v_n)$ is a proper sequence. If there are distinct
indexes $p_1,p_2$ satisfying $\Delta(w,v_{p_i-1},v_{p_i})\Delta(w,v_{p_i},v_{p_i+1})<0$, then,
for any $q\notin\{p_1,p_2\}$, it holds that $\Delta(w,v_{q-1},v_{q})\Delta(w,v_{q},v_{q+1})>0$.
\end{lem}

\begin{proof}
The two supporting lines containing $w$ pass through $v_{p_1}$ and $v_{p_2}$, respectively.
It suffices to note that $\operatorname{conv}\{v_q,v_{q+1}\}$ and $w$ lie on the same side
of $\operatorname{conv}\{v_{p_1},v_{p_2}\}$ if, and only if, $w$ and $\operatorname{conv}v$
are separated by $\operatorname{conv}\{v_q,v_{q+1}\}$.
\end{proof}

The following concept is crucial for our further considerations. We say that a proper sequence
$(v_1,\ldots,v_n)$ is \textit{admissible} if, for any indexes $p,q,r,t$ satisfying either
%(i) $p>q>\max\{r+1,t\}$ or (ii) $q>p>\max\{r,t\}$, it holds that $S_t^pS_q^r>S_q^pS_r^t$.
(i) $\min\{p,q-1\}>r>t$ or (ii) $q>p>\max\{r,t\}$, it holds that $S_t^pS_q^r>S_q^pS_t^r$.

The rest of our paper has the following structure. We construct an extension of size $17\sqrt{n}$ for
any admissible $n$-gon in Section~3, and we give a technical characterization of admissible polygons in
Section~4. The existence of admissible polygons will be shown in Section~5. We will prove that, for any
$n$ fixed in advance, there is a sufficiently large $m$ such that the vertex set of every convex $m$-gon
has a subset $A$ of cardinality $n$ such that $\operatorname{conv}A$ is admissible. This will allow us
to prove the main results in Section~6.



\section{Admissible polygons and their extensions}

In this section we prove that, if the sequence of vertices of a convex $n$-gon is admissible,
then the extension complexity of it is at most $17\sqrt{n}$. The following lemma gives a bound
on the nonnegative ranks of certain submatrices of the slack matrix.

\begin{lem}\label{lemneg}
Let $(v_1,\ldots,v_n)$ be a proper sequence; denote $U=\{p,{p+1},\ldots,q\}$.
Assume $\alpha_{r}^{t}$ are non-positive numbers and define the entries of a
matrix $\mathcal{S}$ by $\mathcal{S}_{i}^j=S_i^j+\sum_{t\in U}\alpha_{i}^{t}S_t^j$,
for any $i\in \{1,\ldots,n\}\setminus U$ and $j\in U\setminus\{q\}$. If the entries of
$\mathcal{S}$ are nonnegative, then its nonnegative rank is at most eight.
\end{lem}

\begin{proof}
1. For $\star\in\{<,>\}$, we denote by $W_\star$ the set of all $w$ satisfying $\Delta(w,v_p,v_q)\star0$, $\Delta(w,v_{q-1},v_q)\star0$,
$\Delta(w,v_p,v_{p+1})\star0$, and by $\mathcal{W}_\star$ the closure of $W_\star$. Lemma~\ref{lemside} shows that $\Delta(w',v_j,v_{j+1})\star0$
holds for any $j\in U\setminus\{q\}$ and $w'\in\mathcal{W}_\star$. %and also $\Delta(w'',v_j,v_{j+1})\leq0$, for any $w''\in\mathcal{W}_<$.
Also, since $\mathcal{W}_\star$ is an intersection of three half-planes, any finite subset of $\mathcal{W}_\star$ lies in
the convex hull of at most four points from $\mathcal{W}_\star$.

2. Since matrices of nonnegative rank at least nine form an open subset within $n\times n$ nonnegative matrices,
we can assume that $a_i:=1+\sum_{t\in U}\alpha_i^t\neq0$, for any $i\in \{1,\ldots,n\}\setminus U$. Denote the
affine combination $v_i/a_i+\sum_{t\in U}\alpha_i^tv_t/a_i$ by $w_i$; then we have
%$\mathcal{S}_i^j=a_i\Delta(w_i,v_j,v_{j+1})$. %=S_i^j+\sum_{t\in U}\alpha_{i}^{t}S_t^j$.
$a_i\Delta(w_i,v_a,v_{b})=\Delta(v_i,v_a,v_{b})+\sum_{t\in U}\alpha_i^t\Delta(v_t,v_a,v_{b})$.
The lemma's assumption shows that $w_i\in\mathcal{W}_\star$ whenever $a_i\star0$; in particular,
we get $\mathcal{S}_i^j=a_i\Delta(w_i,v_j,v_{j+1})$.
From Step~1 it follows that there are $w_1^\star,\ldots,w_4^\star\in\mathcal{W}_\star$
such that, for every $i$ satisfying $a_i\star0$,
$w_i$ is a convex combination $\sum_{s=1}^4\lambda_i^sw_s^\star$, which implies
$\mathcal{S}_i^j=\sum_{s=1}^4a_i\lambda_i^s\Delta(w_s^\star,v_j,v_{j+1})=
\sum_{s=1}^4|a_i|\lambda_i^s\cdot\left|\Delta(w_s^\star,v_j,v_{j+1})\right|$.
\end{proof}

Now we prove the main result of the section in a special case when $n$ is a square.

\begin{lem}\label{lemadmis1}
Assume $m>3$ and $(v_0,\ldots,v_{m^2-1})$ is an admissible sequence. Then, the extension complexity
of $\operatorname{conv}\{v_0,\ldots,v_{m^2-1}\}$ does not exceed $15m-3$.
\end{lem}

\begin{proof}
Denote %$P_\sigma=[\sigma m+m-1]\setminus[\sigma m]$, $Q_\sigma=[\sigma m+m-2]\setminus[\sigma m]$,
$P_\sigma:=\{\sigma m+2,\ldots,\sigma m+m-2\}$, $P:=\bigcup_{\sigma=0}^{m-1}P_\sigma$. %$M_\sigma=\{\sigma m+1,\ldots,(\sigma+1) m\}$,
For any $r\in P_0$, we define the vectors $A^r,B_r\in\mathbb{R}^{m^2}$ by $A^r_i=0$ whenever $i-r\notin m\mathbb{Z}$,
$$A^r_{\sigma m+r}=\left(\prod\limits_{t=0}^{\sigma-1}S_{tm+r}^{(1+t)m}\right)^{-1}\left(\prod\limits_{\tau=\sigma+1}^{m-1}S_{\tau m+r}^{\tau m}\right)^{-1},$$
$$B_r^j=\left(\prod\limits_{t=0}^{[j/m]-1}S_{tm+r}^{(1+t)m}\right)\left(\prod\limits_{\tau=[j/m]+1}^{m-1}S_{\tau m+r}^{\tau m}\right)\cdot S_{r+[j/m]m}^j.$$
Now define $\mathcal{S}_i^j:=S_i^j-\sum_{r=2}^{m-2}A_i^rB_r^j$, for any $i,j\in\{0,\ldots,m^2-1\}$.
It is a routine to check that the entries of $\mathcal{S}$ are nonnegative, and submatrices $\mathcal{S}[P_\sigma|P_\sigma]$ are zero.
Since the matrix $\mathcal{S}[P|P]$ can be obtained from $S$ by subtracting $m-3$ nonnegative rank one matrices and removing $6m$ lines,
the nonnegative rank of $S$ can exceed that of $\mathcal{S}[P|P]$ by at most $7m-3$. Now it suffices to note that, by Lemma~\ref{lemneg},
the nonnegative rank of $\mathcal{S}[P\setminus P_\sigma|P_\sigma]$ does not exceed eight.
%=\mathcal{S}\left[P\setminus\{\sigma m+2,\ldots,\sigma m+m-1\}\left|\right.\sigma m+2,\ldots,\sigma m+m-2\right]$
\end{proof}

Now, the main result of this section follows from Lemma~\ref{lemeasy} and Lemma~\ref{lemadmis1} because $n-\left[\sqrt{n}\right]^2<2\sqrt{n}$.

\begin{thr}\label{thradmis1}
Let $(v_1,\ldots,v_{n})$ be an admissible sequence. Then, the extension complexity
of $\operatorname{conv}\{v_1,\ldots,v_{n}\}$ is less than $17\sqrt{n}$.
\end{thr}





\section{Characterization of admissible sequences}

In what follows we denote the distance between points $u$ and $v$ by
$d(u,v)$, denote the (absolute value of) measure
of the angle between $\overrightarrow{u_2u_1}$ and $\overrightarrow{u_2u_3}$
by $\alpha(u_1,u_2,u_3)$, and also $\beta(u_1,u_2,u_3)=\pi-\alpha(u_1,u_2,u_3)$.
Let $v=(v_1,\ldots,v_n)$ be a sequence of points. We define
the \textit{edge sequence} of $v$ as $d(v_1,v_2),\ldots,d(v_{n-1},v_n)$, the
\textit{angle sequence} as $\beta(v_1,v_2,v_3),\ldots,\beta(v_{n-2},v_{n-1},v_n)$,
and the \textit{edge-by-angle sequence} as
$d(v_2,v_3)\beta(v_1,v_2,v_3),\ldots,d(v_{n-1},v_n)\beta(v_{n-2},v_{n-1},v_n)$.
We say that $v$ is \textit{$\theta$-thin} if the sum of elements of angle sequence is at
most $\theta$. In the rest of our paper $n$ always denotes an integer, and we assume $n\geq 20$.

The main result of this section is a sufficient condition on $v$ to be admissible, stated in terms
of monotonicity of the edge, angle and edge-by-angle sequences. Let us prove two easy lemmas first.

\begin{lem}\label{lempqrt5}
Let $v=(v_1,\ldots,v_n)$ be a proper $\theta$-thin sequence.
Then, any subsequence of $v$ is $\theta$-thin. If $\theta<1$,
$h>2$, and the edge sequence of $v$ is $h$-decreasing, then
any subsequence of $v$ is has $(h-1)$-decreasing edge sequence.
\end{lem}

\begin{proof}
The first assertion follows from that $\sum_{k=2}^{n-1}\beta(v_{k-1},v_k,v_{k+1})=\alpha(v_2,v_1,v_n)+\alpha(v_1,v_n,v_{n-1})$.
Further, the assumption on $\theta$ guarantees that the angle $\alpha(v_p,v_{q-1},v_{q})$ is obtuse whenever $p<q-1$, so that
$d(v_p,v_{q})<d(v_{q-1},v_{q})$. Thus, $$\frac{d(v_p,v_q)}{h-1}\geq\sum_{t=1}^{+\infty}d(v_{q-1},v_q)h^{-t}>
\sum_{k=q}^{r-1}d(v_{k},v_{k+1})\geq d(v_q,v_r)$$ holds whenever $p<q<r$, and this proves the second assertion.
\end{proof}

\begin{lem}\label{lemesum}
For any proper $1$-thin sequence $(v_1,\ldots,v_n)$, it holds that
$2d(v_1,v_n)>d(v_1,v_2)+\ldots+d(v_{n-1},v_n)$.
\end{lem}

\begin{proof}
%The angle between $\overrightarrow{v_iv_j}$ and $\overrightarrow{v_1v_n}$ can not exceed $1$,
The projection of $\overrightarrow{v_iv_j}$ on $\overrightarrow{v_1v_n}$ has length at least $d(v_i,v_j)\cos1>0.5d(v_i,v_j)$.
\end{proof}

Now we prove the lower and upper bounds on $\beta(v_1,v_{n-1},v_n)$ and $\beta(v_1,v_{2},v_n)$
in terms of measures of angles and lengths of edges of $\operatorname{conv}v$.

\begin{lem}\label{lemasum}
Assume $\theta<0.5$ and $h>4$. If $(v_1,\ldots,v_n)$ is a proper $\theta$-thin sequence with $h$-decreasing edge sequence,
then $$\left(1-2h^{-1}\right)^n\leq\frac{\beta(v_1,v_{n-1},v_n)}{\sum_{k=2}^{n-1}\beta(v_{k-1},v_k,v_{k+1})}\leq 1,$$
$$\left(\frac{\sin\theta}{\theta}\right)^n\leq\frac{\beta(v_1,v_{2},v_n)d(v_2,v_n)}{\sum_{k=2}^{n-1}\beta(v_{k-1},v_k,v_{k+1})d(v_k,v_{k+1})}
\leq \left(\frac{h}{h-1}\right)^n.$$
\end{lem}

\begin{proof}
%Elementary techniques show that
Note that $\alpha(v_1,v_{n-1},v_{n-2})=\arcsin\left(\frac{d(v_1,v_{n-2})}{d(v_1,v_{n-1})}\sin\beta(v_1,v_{n-2},v_{n-1})\right)$.
Similarly to the proof of Lemma~\ref{lempqrt5}, we get $d(v_1,v_{n-2})<d(v_1,v_{n-1})$.
Also, $$d(v_1,v_{n-1})<d(v_1,v_{n-2})+d(v_{n-2},v_{n-1})\leq (1+h^{3-n})d(v_1,v_{n-2}),$$
so we get from Taylor expansion of $\arcsin(t\sin x)$ at $t=1$ that
$$(1-2h^{3-n})\beta(v_1,v_{n-2},v_{n-1})\leq\alpha(v_1,v_{n-1},v_{n-2})\leq \beta(v_1,v_{n-2},v_{n-1}),$$
so the first inequalities follow by induction from $\beta(v_1,v_{n-1},v_n)=\beta(v_{n-2},v_{n-1},v_n)+\alpha(v_1,v_{n-1},v_{n-2})$.

Similarly, we have $\alpha(v_n,v_{2},v_{3})=\arcsin\left(\frac{d(v_3,v_{n})}{d(v_2,v_{n})}\sin\beta(v_2,v_{3},v_{n})\right)$, and then
$$\frac{\sin \beta(v_2,v_{3},v_{n})}{\beta(v_2,v_{3},v_{n})}\leq \frac{\alpha(v_n,v_{2},v_{3})}{\frac{d(v_3,v_{n})}{d(v_2,v_{n})}
\beta(v_2,v_{3},v_{n})}\leq 1.$$ Combining this result with $\beta(v_1,v_{2},v_n)=\beta(v_1,v_2,v_3)+\alpha(v_n,v_{2},v_{3})$, we get
$$\frac{\sin\beta(v_2,v_{3},v_{n})}{\beta(v_2,v_{3},v_{n})}\leq\frac{\beta(v_1,v_{2},v_n)d(v_2,v_n)}
{\beta(v_1,v_2,v_3)d(v_2,v_3)+\beta(v_2,v_{3},v_{n})d(v_3,v_n)} \leq\frac{d(v_2,v_n)}{d(v_2,v_3)}.$$
By Lemma~\ref{lempqrt5} $\beta(v_2,v_{3},v_{n})\leq\theta$ and $(h-1)d(v_2,v_n)\leq h d(v_2,v_3)$, so
the second inequalities follow by induction.
\end{proof}

Lemma~\ref{lemasum} will allow us to prove the main result of the section. The following three lemmas are special cases of it.

\begin{lem}\label{lempqrt1}
Let $v=(v_1,\ldots,v_m)$ be a proper sequence. If indexes
$p,q,r,t$ satisfy $q>p>r>t$, then $S^p_tS^r_q>S^p_qS^r_t$.
\end{lem}

\begin{proof}
Note that $v'=(v_t,v_r,v_{r+1},v_p,v_{p+1},v_q)$ is a subsequence of $v$, so $v'$ is proper itself.
If $\overrightarrow{v_pv_{p+1}}$ and $\overrightarrow{v_rv_{r+1}}$ are collinear, the result is straightforward.
Otherwise, we act on $v$ with an appropriate affine transformation, and we get $v_p=(a,0)$, $v_{p+1}=(1,0)$, $v_r=(0,1)$,
$v_{r+1}=(0,b)$ with some positive $a$ and $b$. The rest is done by straightforward checking.
%If $a-1$ and $b-1$ have different signs, then $\operatorname{conv}\{v_r,v_{p+1}\}$ and $\operatorname{conv}\{v_p,v_{r+1}\}$ have nonempty intersection,
\end{proof}



\begin{lem}\label{lempqrt2}
Let $v=(v_1,\ldots,v_n)$ be a proper $n^{-1}$-thin sequence. Assume the edge sequence of $v$ is $n^2$-decreasing and angle
sequence of $v$ is monotone. Then, for any $p,q,r,t$ satisfying $p>q>r+1>t+1$, it holds that $S^p_tS^r_q>S^p_qS^r_t$.
\end{lem}

\begin{proof}
Note that $a>b>c$ implies $2\sin\beta(v_a,v_b,v_c)>\beta(v_a,v_b,v_c)$, and $$2S^i_j=d(v_i,v_{i+1})d(v_{i+1},v_j)\sin\beta(v_i,v_{i+1},v_j)=d(v_i,v_{i+1})d(v_i,v_j)\sin\beta(v_{i+1},v_i,v_j).$$
Consequently,
$$\frac{S^p_tS^r_q}{S^p_qS^r_t}>\frac{d(v_t,v_p)d(v_{r+1},v_q)}{4d(v_q,v_{p})d(v_{t},v_{r})}
\cdot\frac{\beta(v_t,v_p,v_{p+1})\beta(v_r,v_{r+1},v_{q})}{\beta(v_q,v_p,v_{p+1})\beta(v_t,v_r,v_{r+1})}.$$
Note that $\beta(v_r,v_{r+1},v_{q})\geq\beta(v_r,v_{r+1},v_{r+2})$ and $n\sin n^{-1}\geq1-n^{-2}$.
Denoting $\beta_k:=\beta(v_{k-1},v_k,v_{k+1})$ and using Lemma~\ref{lemasum}, we get
$$\frac{S^p_tS^r_q}{S^p_qS^r_t}> \frac{d(v_t,v_p)d(v_{r+1},v_q)}{d(v_q,v_p)d(v_{t},v_r)}
\cdot\frac{\left(\sum_{k=t+1}^p\beta_k\right)\beta_{r+1}}{\left(\sum_{k=q+1}^p\beta_k\right)
\left(\sum_{k=t+1}^r\beta_k\right)}\cdot\frac{\left(1-2n^{-2}\right)^n}{4}.$$
The first fraction is at least $n^2-1$ by Lemma~\ref{lempqrt5};
%because the edges of $v$ are $n^2$-decreasing;
since $(\beta_k)$ is a monotone sequence, we have
$n\beta_{r+1}>\min\left\{\sum_{k=q+1}^p\beta_k,\sum_{k=t+1}^r\beta_k\right\}$. This implies that
$\left(S^p_tS^r_q\right)/\left(S^p_qS^r_t\right)>0.25(n^2-1)(1-2n^{-2})^nn^{-1}>1$.
\end{proof}


\begin{lem}\label{lempqrt2'}
Let $v=(v_1,\ldots,v_n)$ be a proper $n^{-1}$-thin sequence. Assume the edge sequence of $v$ is $n^2$-decreasing and edge-by-angle
sequence of $v$ is monotone. Then, for any indexes $p,q,r,t$ satisfying $q>p>t>r$, it holds that $S^p_tS^r_q>S^p_qS^r_t$.
\end{lem}

\begin{proof}
%Since $\sin\beta(v_a,v_b,v_c)>2\beta(v_a,v_b,v_c)$ whenever $a>b>c$, we get
Similarly to the proof of Lemma~\ref{lempqrt2}, we get
$$\frac{S^p_tS^r_q}{S^p_qS^r_t}>\frac{d(v_t,v_p)d(v_{r+1},v_q)}{4d(v_q,v_{p+1})d(v_{t},v_{r+1})}
\cdot\frac{\beta(v_t,v_p,v_{p+1})\beta(v_r,v_{r+1},v_{q})}{\beta(v_p,v_{p+1},v_q)\beta(v_r,v_{r+1},v_{t})}.$$
Denoting $\gamma_k:=d(v_k,v_{k+1})\beta(v_{k-1},v_k,v_{k+1})$, we use Lemma~\ref{lemasum} and get
$$\frac{S^p_tS^r_q}{S^p_qS^r_t}>\frac{\left(\sum_{k=r+1}^{q-1}\gamma_k\right)\gamma_{p}}
{\left(\sum_{k=p+1}^{q-1}\gamma_k\right)\left(\sum_{k=r+1}^{t-1}\gamma_k\right)}\cdot\frac{d(v_t,v_p)}{d(v_p,v_{p+1})}
\cdot\frac{n^{3n}\left(\sin n^{-1}\right)^n}{4(n^2-1)^n}.$$
Again, the first fraction is at least $n^{-1}$ because $(\gamma_k)$ is a monotone sequence; the second fraction is at least $n^2$ because the
edges of $v$ are $n^2$-decreasing. Again, we can see that $\left(S^p_tS^r_q\right)/\left(S^p_qS^r_t\right)>1$.
%Now we see that $\left(S^p_tS^r_q\right)/\left(S^p_qS^r_t\right)\geq0.25n(1-n^{-2})^n>1$.
\end{proof}

Now we put the results of Lemmas~\ref{lempqrt1},~\ref{lempqrt2}, and~\ref{lempqrt2'} together.

\begin{cor}\label{coradmis}
Let $v=(v_1,\ldots,v_n)$ be a proper $n^{-1}$-thin sequence. Assume the edge sequence of $v$ is $n^2$-decreasing,
the angle sequence of $v$ is monotone, the edge-by-angle sequence of $v$ is monotone. Then, $v$ is admissible.
\end{cor}

\begin{proof}
Consider indexes $p,q,r,t$; note that $S^p_qS^r_t=0$ when either $p=q$ or $r=t$. Then, assume $p\neq q$ and $r\neq t$.
If $\min\{p,q-1\}>r>t$, then either $p>q>r+1>t+1$ or $q>p>r>t$. In the former case, Lemma~\ref{lempqrt2} implies $S^p_tS^r_q>S^p_qS^r_t$;
in the latter case, this follows from Lemma~\ref{lempqrt1}. If $q>p>\max\{r,t\}$, then either $q>p>r>t$ or $q>p>t>r$. Again, we deduce
$S^p_tS^r_q>S^p_qS^r_t$ from Lemma~\ref{lempqrt1} in the former case; in the latter case, this follows from Lemma~\ref{lempqrt2'}.
\end{proof}








\section{Extracting an admissible subsequence}

The goal of this section is to show that, for any $n$ fixed in advance,
any sufficiently large proper sequence contains an admissible subsequence of length $n$.

Let $r=(r_1,\ldots,r_m)$ be a sequence of reals and $\iota=(i_0,\ldots,i_t)$
a strictly increasing sequence of indexes. In the following lemma, we refer to
the sequence $\left(\sum_{k=i_0+1}^{i_1} r_k,\ldots, \sum_{k=i_{t-1}+1}^{i_t} r_k\right)$
as a \textit{sum-subsequence} of $r$ corresponding to $\iota$.

\begin{lem}\label{lemesumma}
Let $r=(r_1,\ldots,r_m)$ be a sequence of positive reals and $h,p,q$ positive integers.
If $m=\exp_2\left(\sum_{k=0}^{p-1}h^k+\sum_{k=0}^{q-1}h^k\right)$, then $r$ contains either
an $h$-increasing sum-subsequence of length $p$ or an $h$-decreasing sum-subsequence of length $q$.
\end{lem}

\begin{proof}
If $s$ was a non-decreasing sequence of length $\sum_{k=0}^{p-1}h^k$, then a sum-subsequence
of $s$ defined by $i_0=0$ and $i_\tau=\sum_{k=0}^{\tau-1}h^k$, for $\tau\in\{1,\ldots,p\}$,
would be $h$-increasing. This shows that proving the result for $h=1$ is sufficient, and we
do this by induction on $(p,q)$. If $p=q=1$, then the result is trivial, and we proceed by
assuming without a loss of generality that $\sum_{k=1}^{m/2}r_k\geq \sum_{k=m/2+1}^{m}r_k$.
By induction, we find either a non-decreasing sum-subsequence of length $p$ or a non-increasing
sum-subsequence of length $q-1$ in $(r_{m/2+1},\ldots,r_m)$. In the former case we are done;
if we denote by $j_0<\ldots<j_{q-1}$ the indexes defining the sum-subsequence from the latter case,
then the sum-subsequence defined by $0<j_0<\ldots<j_{q-1}$ is non-increasing.
\end{proof}

The following is a generalization of Lemma~\ref{lemasum}. We give lower and upper bounds on
$\beta(v_1,v_{p},v_n)$ in terms of measures of angles and lengths of edges of $\operatorname{conv}v$.

\begin{lem}\label{lempqrt3}
Let $v=(v_1,\ldots,v_n)$ be a proper $n^{-1}$-thin sequence. Assume the edge sequence of $v$ is $n^2$-decreasing.
Denote $\beta_k:=\beta(v_{k-1},v_k,v_{k+1})$ and $\gamma_k:=d(v_k,v_{k+1})\beta(v_{k-1},v_k,v_{k+1})$. Then, for
every $p$, we have

(1) $\beta(v_1,v_{p},v_n)\leq\sum_{k=2}^{p}\beta_k+0.1\sum_{k=p+1}^{n-1}\beta_k,$

(2) $\beta(v_1,v_{p},v_n)\geq0.9\sum_{k=2}^{p}\beta_k,$

(3) $\beta(v_1,v_{p},v_n)d(v_p,v_n)\leq0.1\sum_{k=2}^{p-1}\gamma_k+1.1\sum_{k=p}^{n-1}\gamma_k,$

(4) $\beta(v_1,v_{p},v_n)d(v_p,v_n)\geq0.9\sum_{k=p}^{n-1}\gamma_k.$
\end{lem}

\begin{proof}
The inequalities $(2)$ and $(4)$ follow from Lemma~\ref{lemasum} because $(1-2n^{-2})^n$ and $(n\sin n^{-1})^n$ are both greater than $0.9$.
To prove $(1)$, note that $\beta(v_1,v_{p},v_n)=\beta(v_1,v_p,v_{p+1})+\alpha(v_n,v_p,v_{p+1})$, and $\beta(v_1,v_p,v_{p+1})\leq\sum_{k=2}^{p}\beta_k$
by Lemma~\ref{lemasum}. Also, $\alpha(v_n,v_p,v_{p+1})$ equals $\arcsin\left(\frac{d(v_{p+1},v_{n})}{d(v_p,v_n)}\sin\beta(v_p,v_{p+1},v_n)\right)$, which
does not exceed $\frac{d(v_{p+1},v_n)}{d(v_p,v_n)}\beta(v_p,v_{p+1},v_n)$. Using Lemma~\ref{lemasum} again, we get
%$$\alpha(v_n,v_p,v_{p+1})\leq\sum_{k=p+1}^{n-1}\frac{d(v_k,v_{k+1})}{d(v_p,v_n)}\beta_k\leq
$$\frac{\alpha(v_n,v_p,v_{p+1})}{(1-n^{-2})^n}\leq\sum_{k=p+1}^{n-1}\frac{d(v_k,v_{k+1})}{d(v_p,v_n)}\beta_k\leq
\frac{d(v_{p+1},v_{p+2})}{d(v_p,v_n)}\sum_{k=p+1}^{n-1}\beta_k\leq n^{-2}\sum_{k=p+1}^{n-1}\beta_k.$$

To prove $(2)$, note that $\beta(v_1,v_{p},v_n)=\beta(v_{p-1},v_p,v_{n})+\alpha(v_{p-1},v_p,v_{1})$, and
$\beta(v_{p-1},v_p,v_{n})d(v_p,v_n)\leq1.1\sum_{k=p}^{n-1}\gamma_k$ by Lemma~\ref{lemasum}. Further, $\alpha(v_{p-1},v_p,v_{1})$
equals $\arcsin\left(\frac{d(v_{1},v_{p-1})}{d(v_1,v_p)}\sin\beta(v_1,v_{p-1},v_p)\right)\leq\beta(v_1,v_{p-1},v_p)$.
By Lemma~\ref{lemasum}, $$\alpha(v_{p-1},v_p,v_{1})d(v_p,v_n)\leq\sum_{k=2}^{p-1}\beta_kd(v_p,v_n)\leq
\sum_{k=2}^{p-1}\frac{d(v_p,v_n)\gamma_k}{d(v_k,v_{k+1})}\leq0.1\sum_{k=2}^{p-1}\gamma_k.$$
\end{proof}


The following lemma points out a sufficient condition for monotonicity of angles of a subsequence.

\begin{lem}\label{lempqrt4}
Let $v=(v_1,\ldots,v_n)$ be a proper $n^{-1}$-thin sequence.
Assume the edge sequence of $v$ is $n^2$-decreasing. If the angle %(or edge-by-angle, respectively)
sequence of $v$ is $3$-monotone, then any subsequence of $v$ has monotone angle %(edge-by-angle, respectively)
sequence.
\end{lem}

\begin{proof}
Assume $p,q,r,s\in\{1,\ldots,n\}$ and $p<q<r<s$. We use Lemma~\ref{lempqrt3} to see that, if $(\beta_k)$ is decreasing,
$$\beta(v_p,v_q,v_r)\geq0.9\sum_{k=p+1}^q\beta_k>\sum_{t=1}^{+\infty}3^{-t}\beta_q>\sum_{k=q+1}^{n-1}\beta_k>\beta(v_q,v_r,v_s).$$
If $(\beta_k)$ is increasing, we get $\beta(v_p,v_q,v_r)\leq\sum_{k=p+1}^q\beta_k+0.1\sum_{k=q+1}^{r-1}\beta_k$, thus
$$\beta(v_p,v_q,v_r)<\sum_{t=1}^{+\infty}3^{-t}\beta_{q+1}+0.1\sum_{k=q+1}^{r}\beta_k<0.9\sum_{k=q+1}^{r}\beta_k<\beta(v_q,v_r,v_s).$$
This shows that any subsequence of $v$ has a monotone angle sequence.
\end{proof}















The following lemmas help us finalize the proof of the main result.

\begin{lem}\label{lemthin}
If $N>2\pi nm$, then any proper sequence $u=(u_1,\ldots,u_{N})$ has an $n^{-1}$-thin subsequence of length $m$.
\end{lem}

\begin{proof}
Follows from that $\sum_{k=2}^{N-1}\beta(u_{k-1},u_k,u_{k+1})<2\pi$.
\end{proof}




\begin{lem}\label{lemedgemon}
Assume $N>2\pi n\exp_2 (2n)^{2n}$ and $u=(u_1,\ldots,u_{N})$ is a proper sequence. Then, $u$
has an $n^{-1}$-thin subsequence of length $n$ whose edge sequence is $n^2$-monotone.
\end{lem}

\begin{proof}
By Lemma~\ref{lemthin}, $u$ has an $n^{-1}$-thin subsequence $u'$ of length $\exp_2 (2n)^{2n}$.
By Lemma~\ref{lemesumma}, the edge sequence of $u'$ admits a $2n^2$-monotone sum-subsequence,
and the result follows from Lemma~\ref{lemesum}.
\end{proof}



\begin{lem}\label{lemanglemon}
Assume $N\geq\exp_2 \exp_6 n$ and $u=(u_1,\ldots,u_{N})$ is a proper $N^{-1}$-thin sequence whose edge sequence
is $N^2$-decreasing. Then, $u$ has a subsequence of length $n$ whose angle (or edge-by-angle) sequence is $3$-monotone.
\end{lem}

\begin{proof}
Denote $\beta_k:=\beta(u_{k-1},u_k,u_{k+1})$.
By Lemma~\ref{lemesumma}, there is an increasing sequence $i_1,\ldots,i_n$ such that the sequence
$(s_t)=\left(\sum_{k=i_t+1}^{i_{t+1}} \beta_k\right)$ is $6$-monotone. We will use Lemma~\ref{lempqrt3}
to show that $(u_{i_1},\ldots,u_{i_n})$ has $3$-monotone angle sequence. Actually, if $s$ is increasing,
then $$\beta(u_{i_{t-1}},u_{i_t},u_{i_{t+1}})\leq s_{t-1}+0.1s_t<0.3s_{t}\leq\beta(u_{i_{t}},u_{i_{t+1}},u_{i_{t+2}})/3.$$
Similarly, if $s$ was decreasing, we would have
$$\beta(u_{i_{t-1}},u_{i_t},u_{i_{t+1}})\geq 0.9s_{t-1}\geq3s_{t}+2.4s_{t+1}\geq3\beta(u_{i_{t}},u_{i_{t+1}},u_{i_{t+2}}).$$

To prove the statement for edge-by-angle sequences, denote $\gamma(a,b,c):=d(u_b,u_{c})\beta(u_{a},u_b,u_{c})$.
Again, Lemma~\ref{lemesumma} shows that there is an increasing sequence $j_1,\ldots,j_n$ such that the sequence
$(r_t)=\left(\sum_{k=j_t}^{j_{t+1}-1} \gamma(k-1,k,k+1)\right)$ is $6$-monotone. If $r$ is decreasing, we get
by Lemma~\ref{lempqrt3} $$\gamma(j_{t-1},j_t,j_{t+1})\geq 0.9r_t\geq 0.3r_t+3.6r_{t+1}\geq 3\gamma(j_t,j_{t+1},j_{t+2}),$$
and if $r$ is increasing, then $$\gamma(j_{t-1},j_t,j_{t+1})\leq 0.1r_{t-1}+1.1r_t\leq 0.2r_{t+1}\leq \gamma(j_t,j_{t+1},j_{t+2})/3,$$
so that $(u_{j_1},\ldots,u_{j_n})$ has $3$-monotone edge-by-angle sequence.
\end{proof}



We finalize the section with a proof of desired result.

\begin{thr}\label{lemadmimain}
If $m>\exp\exp3\exp_2\exp_6\exp_2\exp_6 n$, then any proper sequence $v$ of length $m$ has an admissible subsequence of length $n$.
\end{thr}

\begin{proof}
For positive $x$, we have $\exp\exp 3x>2\pi x\exp_2 (2x)^{2x}$, so by Lemma~\ref{lemedgemon}, there is an $N^{-1}$-thin subsequence of length
$N=\exp_2\exp_6\exp_2\exp_6 n$ whose edge sequence is $N^2$-monotone. Up to symmetry, we can assume that the edge sequence is decreasing,
and then by Lemma~\ref{lemanglemon} there is a subsequence $v'$ of length $\exp_2\exp_6 n$ whose angle sequence is $3$-monotone. Finally,
we find a subsequence $v''$ of $v'$ of length $n$ with monotone edge-by-angle sequence. The angle sequence of $v''$ is monotone by
Lemma~\ref{lempqrt4}, the edge sequence of $v''$ is $n^2$-decreasing by Lemma~\ref{lempqrt5}, and $v''$ is $n^{-1}$-thin again
by Lemma~\ref{lempqrt5}. Therefore, $v''$ is admissible by Lemma~\ref{coradmis}.
\end{proof}





%\begin{cor}\label{coradmismain}
%There exist admissible sequences of arbitrarily large length.
%\end{cor}


























\section{The main result}

We are ready to prove the main theorem. Recall that the results of Sections~4 and~5 were
proven under assumption that $n\geq 20$, which has been mentioned in the beginning of Section~4.

\begin{thr}\label{thrextcomp}
If $m>\exp\exp\exp\exp\exp\exp 40$, then the extension complexity of convex $m$-gon does not exceed $25m\left(\ln\ln\ln\ln\ln\ln m\right)^{-0.5}$.
\end{thr}

\begin{proof}
Let $n=\left[0.5\ln\ln\ln\ln\ln\ln m\right]$, then $n\geq20$ and Theorem~\ref{lemadmimain} is applicable. Therefore, the sequence of vertices
of a convex $m$-gon $P$ contains admissible disjoint subsequences $v_1,\ldots,v_k$ of length $n$ such that $m-kn\leq\exp\exp3\exp_2\exp_6\exp_2\exp_6 n$.
The extension complexity of $\operatorname{conv}v_i$ is at most $17\sqrt{n}$ by Theorem~\ref{thradmis1}. Finally, we use
Lemma~\ref{lemeasy} to bound the extension complexity of $P$ from above by $17m/\sqrt{n}+\exp\exp3\exp_2\exp_6\exp_2\exp_6n$.
\end{proof}

Also, let us follow the argument from~\cite{ShiCom} to deduce a linear algebraic formulation of Theorem~\ref{thrextcomp}. Let $A$
be a nonnegative $m$-by-$n$ matrix with classical rank equal to $3$. Consider the simplex $\Delta\subset\R^m$ consisting of points
with nonnegative coordinates which sum to $1$. Since $\Delta$ has $m$ facets, the intersection of $\Delta$ with the column space of
$A$ is a polygon $I$ with $k$ vertices, and $k\leq m$. Form a matrix $S$ of column coordinate vectors of vertices of $I$, then $A=SB$
with $B$ nonnegative. Since $S$ is a slack matrix for $I$, it has nonnegative rank at most $25m\left(\ln\ln\ln\ln\ln\ln m\right)^{-0.5}$,
and so does $A$.

Finally, let us remark that our paper shows the existence of a generic $n$-gon with extension complexity $O(\sqrt{n})$. To see this,
note that the set of admissible $n$-gons is open by its definition and non-empty by Theorem~\ref{lemadmimain}. Clearly, almost all
polygons from this open set are generic, and they have extensions of size at most $17\sqrt{n}$ by Theorem~\ref{thradmis1}. This result
shows that an $\Omega(\sqrt{n})$ lower bound for extension complexities of all generic $n$-gons, obtained in~\cite{FRT}, cannot be improved.







\begin{thebibliography}{99}

%\bibitem{AGG}
%{ M. Akian, S. Gaubert, A. Guterman, } Linear independence over
%tropical semirings and beyond, \textit{Contemp. Math.}, AMS, \textbf{495} (2009), 1--38.

\bibitem{BL}
{ L. B. Beasley, T. J. Laffey, } Real rank versus nonnegative rank, \textit{Linear Algebra Appl.}, \textbf{431} (2009), 2330--2335.

\bibitem{B-TN}
A. Ben-Tal, A. Nemirovski. On polyhedral approximations of the second-order cone, \textit{Math. Oper. Res.}, \textbf{26} (2001), 193--205.

\bibitem{BP}
Braun G., Pokutta S, Common information and unique disjointness, \textit{54th Annual Symposium on Foundations of Computer Science}, IEEE (2013), 688--697.

%\bibitem{CR}
%{ J. E. Cohen, U. G. Rothblum, } Nonnegative ranks, decompositions, and factorizations
%of nonnegative matrices, \textit{Linear Algebra Appl.}, \textbf{190} (1993), 149--168.

\bibitem{CCZ}
M. Conforti, G. Cornuejols, G. Zambelli, Extended
formulations in combinatorial optimization, \textit{4OR}, \textbf{8(1)} (2010), 1--48.

%\bibitem{FMPTdW}
%S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds,
%in \textit{Proc. 44th Symp. on Th. of Comp.}, 95--106, 2012, ACM.

\bibitem{FRT}
S. Fiorini, T. Rothvo{\ss}, H. R. Tiwary, Extended formulations for polygons, \textit{Discrete Comput. Geom.}, \textbf{48(3)} (2012), 1--11.

\bibitem{GPT}
J. Gouveia, P. A. Parillo, R. R. Thomas, Lifts of convex sets and cone factorizations, \textit{Math. Oper. Res.}, \textbf{38} (2013), 248--264.

%\bibitem{GRT}
%J. Gouveia, R. Z. Robinson, R. R. Thomas. Polytopes of minimum positive
%semidefinite rank. Arxiv preprint arXiv:1205.5306.

\bibitem{GRT2}
J. Gouveia, R. Z. Robinson, R. R. Thomas, Worst-case results for positive semidefinite rank, preprint (2013), arXiv:1305.4600.

\bibitem{GG}
{ N. Gillis, F. Glineur, } On the Geometric Interpretation of the Nonnegative Rank, \textit{Linear Algebra Appl.}, \textbf{437} (2012), 2685--2712.

\bibitem{Hr}
{ P. Hrube\v{s}, } On the nonnegative rank of distance matrices, \textit{Inform. Process. Lett.}, \textbf{112(11)} (2012), 457--461.

%\bibitem{Kai}
%V. Kaibel, Extended Formulations in Combinatorial Optimization, \textit{Optima} \textbf{85} (2011), 2--7.

\bibitem{LC}
{ M. M. Lin and M. T. Chu, } {On the nonnegative rank of Euclidean distance matrices}, \textit{Linear Algebra Appl.}, \textbf{433} (2010), 681--689.

\bibitem{PP}
A. Padrol, J. Pfeifle, Polygons as slices of higher-dimensional polytopes, preprint (2014), arXiv:1404.2443.

\bibitem{PW}
K. Pashkovich, S. Weltge, Hidden Vertices in Extensions of Polytopes, preprint (2014), arXiv:1404.2752.

\bibitem{ShiCom} Ya. Shitov, An upper bound for nonnegative rank, \textit{J. Comb. Theory A}, \textbf{122} (2014), 126--132.

\bibitem{VGGT}
A. Vandaele, N. Gillis, F. Glineur, D. Tuyttens, Heuristics for Exact Nonnegative Matrix Factorization, preprint (2014), arXiv:1411.7245.

%\bibitem{Vav}
%S. A. Vavasis, On the complexity of nonnegative matrix factorization, \textit{SIAM J. Opt.} \textbf{20(3)} (2009), 1364--1377.

\bibitem{Yan}
M. Yannakakis, Expressing combinatorial optimization problems by linear programs, \textit{Comput. System Sci.}, \textbf{43} (1991), 441--466.

\end{thebibliography}

\end{document}




1412.0728.extracted_bib
{AGG %{ M. Akian, S. Gaubert, A. Guterman, Linear independence over %tropical semirings and beyond, Contemp. Math., AMS, 495 (2009), 1--38.
1412.0728.extracted_bib
{BL { L. B. Beasley, T. J. Laffey, Real rank versus nonnegative rank, Linear Algebra Appl., 431 (2009), 2330--2335.
1412.0728.extracted_bib
{B-TN A. Ben-Tal, A. Nemirovski. On polyhedral approximations of the second-order cone, Math. Oper. Res., 26 (2001), 193--205.
1412.0728.extracted_bib
{BP Braun G., Pokutta S, Common information and unique disjointness, 54th Annual Symposium on Foundations of Computer Science, IEEE (2013), 688--697. %
1412.0728.extracted_bib
{CR %{ J. E. Cohen, U. G. Rothblum, Nonnegative ranks, decompositions, and factorizations %of nonnegative matrices, Linear Algebra Appl., 190 (1993), 149--168.
1412.0728.extracted_bib
{CCZ M. Conforti, G. Cornuejols, G. Zambelli, Extended formulations in combinatorial optimization, 4OR, 8(1) (2010), 1--48. %
1412.0728.extracted_bib
{FMPTdW %S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, %in Proc. 44th Symp. on Th. of Comp., 95--106, 2012, ACM.
1412.0728.extracted_bib
{FRT S. Fiorini, T. Rothvo{\ss, H. R. Tiwary, Extended formulations for polygons, Discrete Comput. Geom., 48(3) (2012), 1--11.
1412.0728.extracted_bib
{GPT J. Gouveia, P. A. Parillo, R. R. Thomas, Lifts of convex sets and cone factorizations, Math. Oper. Res., 38 (2013), 248--264. %
1412.0728.extracted_bib
{GRT %J. Gouveia, R. Z. Robinson, R. R. Thomas. Polytopes of minimum positive %semidefinite rank. Arxiv preprint arXiv:1205.5306.
1412.0728.extracted_bib
{GRT2 J. Gouveia, R. Z. Robinson, R. R. Thomas, Worst-case results for positive semidefinite rank, preprint (2013), arXiv:1305.4600.
1412.0728.extracted_bib
{GG { N. Gillis, F. Glineur, On the Geometric Interpretation of the Nonnegative Rank, Linear Algebra Appl., 437 (2012), 2685--2712.
1412.0728.extracted_bib
{Hr { P. Hrube\v{s, On the nonnegative rank of distance matrices, Inform. Process. Lett., 112(11) (2012), 457--461. %
1412.0728.extracted_bib
{Kai %V. Kaibel, Extended Formulations in Combinatorial Optimization, Optima 85 (2011), 2--7.
1412.0728.extracted_bib
{LC { M. M. Lin and M. T. Chu, {On the nonnegative rank of Euclidean distance matrices, Linear Algebra Appl., 433 (2010), 681--689.
1412.0728.extracted_bib
{PP A. Padrol, J. Pfeifle, Polygons as slices of higher-dimensional polytopes, preprint (2014), arXiv:1404.2443.
1412.0728.extracted_bib
{PW K. Pashkovich, S. Weltge, Hidden Vertices in Extensions of Polytopes, preprint (2014), arXiv:1404.2752.
1412.0728.extracted_bib
{ShiCom Ya. Shitov, An upper bound for nonnegative rank, J. Comb. Theory A, 122 (2014), 126--132.
1412.0728.extracted_bib
{VGGT A. Vandaele, N. Gillis, F. Glineur, D. Tuyttens, Heuristics for Exact Nonnegative Matrix Factorization, preprint (2014), arXiv:1411.7245. %
1412.0728.extracted_bib
{Vav %S. A. Vavasis, On the complexity of nonnegative matrix factorization, SIAM J. Opt. 20(3) (2009), 1364--1377.
1412.0728.extracted_bib
{Yan M. Yannakakis, Expressing combinatorial optimization problems by linear programs, Comput. System Sci., 43 (1991), 441--466.