cp's OEIS Frontend

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

%I A235459 #39 Sep 06 2023 01:28:26
%S A235459 2,4,16,56,368,116764,217093472
%N A235459 Number of facets of the correlation polytope of degree n.
%C A235459 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.
%C A235459 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.
%C A235459 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.
%D A235459 M. M. Deza and M. Laurent, Geometry of Cuts and Metrics, Springer, 1997, pp. 52-54.
%D A235459 G. Kalai and G. Ziegler, ed. "Polytopes: Combinatorics and Computation", Springer, 2000, Chapter 1, pp 1-41.
%H A235459 T. Christof, <a href="http://comopt.ifi.uni-heidelberg.de/software/SMAPO/cut/cut.html">The SMAPO database about the CUT polytope</a>
%H A235459 Michel Deza and Mathieu Dutour Sikirić, <a href="https://doi.org/10.1111/itor.12194">Enumeration of the facets of cut polytopes over some highly symmetric graphs</a>, Intl. Trans. in Op. Res., 23 (2016), 853-860; arXiv:<a href="https://arxiv.org/abs/1501.05407">1501.05407</a> [math.CO], 2015. [Confirms the value of a(7).]
%H A235459 Stefan Forcey, <a href="https://sforcey.github.io/sf34/hedra.htm#CutPolytope">Encyclopedia of Combinatorial Polytope Sequences: Cut Polytope</a>.
%H A235459 G. Ziegler, <a href="https://arxiv.org/abs/math/9909177">Lectures on 0/1 Polytopes</a>, arXiv:math/9909177 [math.CO], 1999, p 22-28.
%e A235459 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.
%o A235459 (Sage)
%o A235459 def Correlation(n):
%o A235459    if n == 0:
%o A235459       yield (tuple([]),tuple([]))
%o A235459       return
%o A235459    for x,y in Correlation(n-1):
%o A235459       yield (x + (0,),y + (n-1)*(0,))
%o A235459       yield (x + (1,),y + x)
%o A235459 def CorrelationPolytope(n):
%o A235459    return Polyhedron(vertices=[x + y for x,y in Correlation(n)])
%o A235459 def a(n):
%o A235459    return len(CorrelationPolytope(n).Hrepresentation())
%Y A235459 Cf. A053043, A246427.
%K A235459 nonn,hard,more
%O A235459 1,1
%A A235459 _Victor S. Miller_, Jan 10 2014