A246427 -id:A246427 - cp's OEIS frontend

2, 4, 16, 56, 368, 116764, 217093472

Offset: 1

Victor S. Miller, Jan 10 2014

The correlation polytope of degree n is the set of symmetric n X n matrices, P such that P[i,j] = Prob(X[i] = 1 and X[j] = 1) where (X[1],...,X[n]) is a sequence of 0/1 valued random variables (not necessarily independent). It is the convex hull of all n X n symmetric 0/1 matrices of rank 1.
The correlation polytope COR(n) is affinely equivalent to CUT(n+1), where CUT(n) is the cut polytope of complete graph on n vertices -- the convex hull of indicator vectors of a cut delta(S) -- where S is a subset of the vertices. The cut delta(S) is the set of edges with one end point in S and one endpoint not in S.
According to the SMAPO database it is conjectured that a(8) = 12246651158320. This database also says that the above value of a(7) is conjectural, but Ziegler lists it as known.

			a(2) corresponds to 0 <= p[1,2] <= p[1,1],p[2,2] and p[1,1] + p[2,2] - p[1,2] <= 1.

M. M. Deza and M. Laurent, Geometry of Cuts and Metrics, Springer, 1997, pp. 52-54.
G. Kalai and G. Ziegler, ed. "Polytopes: Combinatorics and Computation", Springer, 2000, Chapter 1, pp 1-41.

T. Christof, The SMAPO database about the CUT polytope
Michel Deza and Mathieu Dutour Sikirić, Enumeration of the facets of cut polytopes over some highly symmetric graphs, Intl. Trans. in Op. Res., 23 (2016), 853-860; arXiv:1501.05407 [math.CO], 2015. [Confirms the value of a(7).]
Stefan Forcey, Encyclopedia of Combinatorial Polytope Sequences: Cut Polytope.
G. Ziegler, Lectures on 0/1 Polytopes, arXiv:math/9909177 [math.CO], 1999, p 22-28.

Cf. A053043, A246427.

def Correlation(n):
   if n == 0:
      yield (tuple([]),tuple([]))
      return
   for x,y in Correlation(n-1):
      yield (x + (0,),y + (n-1)*(0,))
      yield (x + (1,),y + x)
def CorrelationPolytope(n):
   return Polyhedron(vertices=[x + y for x,y in Correlation(n)])
def a(n):
   return len(CorrelationPolytope(n).Hrepresentation())

cp's OEIS Frontend

A235459 Number of facets of the correlation polytope of degree n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Sage