|
|
A235459
|
|
Number of facets of the correlation polytope of degree n.
|
|
2
|
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
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.
|
|
REFERENCES
|
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.
|
|
LINKS
|
|
|
EXAMPLE
|
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.
|
|
PROG
|
(Sage)
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())
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|