login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A235459 Number of facets of the correlation polytope of degree n. 1
2, 4, 16, 56, 368, 116764, 217093472 (list; graph; refs; listen; history; text; internal format)
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) = 12,246,651,158,320. This database also says that the above value of a(7) is conjectural, but Ziegler lists it as known.

REFERENCES

G. Kalai and G. Ziegler, ed. "Polytopes: Combinatorics and Computation", Springer, 2000, Chapter 1, pp 1-41.

M. M. Deza, and M. Laurent, Geometry of Cuts and Metrics, Springer, 1997, pp. 52-54

LINKS

Table of n, a(n) for n=1..7.

T. Christof, The SMAPO database about the CUT polytope

G. Ziegler, Lectures on 0/1 Polytopes, arXiv:math/9909177v1 (1999), p 22-28

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

Sequence in context: A009624 A009161 A009290 * A081919 A232664 A153954

Adjacent sequences:  A235456 A235457 A235458 * A235460 A235461 A235462

KEYWORD

nonn,hard,more

AUTHOR

Victor S. Miller, Jan 10 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 21 23:04 EDT 2019. Contains 326169 sequences. (Running on oeis4.)