Correlation polytopes: Their geometry and complexity (Q1176573): Difference between revisions

The author is dealing with the facial structure of the correlation polytope \(P\), which can be defined as follows: for an integer \(n\) let \(S\subseteq K_ n=\{(i,j)\mid 1\leq i<j\leq n\}\) and \[ {\mathcal R}(n,S):=\{u(\varepsilon)=(u_ 1(\varepsilon),\dots,u_ n(\varepsilon),u_{12}(\varepsilon),\dots, u_{ij}(\varepsilon), \dots,u_{n-ln}(\varepsilon)\mid \] \[ u_ i(\varepsilon)=\varepsilon\hbox{ for }i=1, \dots,n; u_{ij}(\varepsilon)= \varepsilon_ i\cdot\varepsilon_ j\hbox{ for all }(i,j)\in S, \varepsilon=(\varepsilon_ 1,\dots,\varepsilon_ n)\in\{0,1\}^ n\} \] a set of vectors corresponding to \(S\); then \(P(n,S)\) is the convex hull of \({\mathcal R}(n,S)\) and especially \(P\) the convex hull of \({\mathcal R}(n,K_ n)\). It is shown that \(P(n,S)\) has a non-empty interior and that its facial structure has a large symmetric group; thus one gets an exponential number of different facets by application of the symmetries. Some facets are determined. Furthermore the author proves that the corresponding decision problem (given a vector \(p\in\mathbb{R}_ +^{n(n+1)/2}\); is \(p\in P\)?) is \(NP\)-complete. This means that unless \(NP=co-NP\) deriving all the inequalities for \(P\) is an ``impossible'' task. The name ``correlation polytope'' stems from the fact that every point of \(P(n,S)\) can be interpreted in terms of certain probability assignments.