Tropical lower bounds for extended formulations (Q745680)

Let \(A\in\mathbb{R}^{f\times n}\) and \(b\in\mathbb{R}^{f}\) and suppose that \(P\) is the polytope in \(\mathbb{R}^{n}\) consisting of all points \(x\) such that \(Ax\geq b\). If \(s_{1},\dots,s_{v}\) are the vertices of \(P\), we define \(S(P,A,b)\) as the \(f\times v\) matrix whose \(i\)th column is \(As_{i}-b\) and call this a slack matrix for \(P\). The extension complexity of \(P\) can be characterized as the least integer \(q\) such that \(S(P,A,b)\) can be written as a product of \(f\times q\) and \(q\times v\) nonnegative matrices [\textit{M. Yannakakis}, J. Comput. Syst. Sci. 43, No. 3, 441--466 (1991; Zbl 0748.90074)]. Now consider the Puiseux series \(\mathcal{R} :=\mathbb{R}[[t]]\) whose elements are formal series \(a(t)=\) \(\sum _{e\in\mathbb{R}}a_{e}t^{e}\) for which the support \(E\) is a well-ordered subset of \(\mathbb{R}\); define \(\deg a(t):=\min E\) (with \(\deg0=\infty\)) and let \(\mathcal{R}_{+}\) consist of all elements with \(\deg a(t)>0\). It is known that \(\mathcal{R}\) is a real closed field under the usual operations of \(+\) and \(\cdot\) for series. Since extension complexity is defined by a first-order formula, theorems concerning extension complexity over \(\mathbb{R}\) remain valid over \(\mathcal{R}\). The image of \(\mathcal{R}_{+}\) under the degree map \(\deg\) is \(\mathbb{R}_{+}\cup\left\{ \infty\right\} \) and the operations \(+\) and \(\cdot\) are mapped onto the tropical operations \(\oplus\) (minimum) and \(\otimes\) (usual \(+\)). The author is interested in showing how this latter map can be used to infer results about the extension complexity of a polytope. For example (Corollary 4.2), he shows that if \(\mathcal{P}\) is a polytope in \(\mathcal{R}^{n}\) and \(S\in\mathcal{R}^{m\times n}\) is a slack matrix for \(\mathcal{P}\), then the extension complexity of \(\mathcal{P}\) is not smaller than the tropical factorization rank of \(\deg S\).