A053043 -id:A053043 - cp's OEIS frontend

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

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())

A246427 Number of facets of the cone defined by the zero-one inclusion matrix of pairs versus triples on an n-set.

Original entry on oeis.org

10, 70, 896, 52367

Offset: 5

Peter J. Dukes, Aug 26 2014

Equivalently, this is the number of integer weightings of the edges of the complete graph K_n which are: (1) nonnegative on all triangles; (2) maximally vanishing on triangles; and (3) have gcd of weights equal to one.

This also gives the degree of each anticut in the metric polytope (see link below) for n points.

			For n = 5, the 10 facet normals are defined by the choice of a (2,3)-partition.  Weight 2 is assigned to edges within each part and weight -1 is assigned to edges crossing the partition.  Every triangle has weight 0, except for one which inherits weight 6.

A. Deza, Metric Polytopes and Metric Cones
P. Dukes, Nearly complete count of isomorphism types for n = 9
P. Dukes and R. M. Wilson, The cone condition and t-designs, European J. Combin. 28 (2007), 1610-1625.
Peter J. Dukes, K. Garaschuk, On the cone of weighted graphs generated by triangles, arXiv preprint arXiv:1608.06017 [math.CO], 2016.
K. Garaschuk, Linear methods for rational triangle decompositions, Ph.D. Dissertation, University of Victoria, 2014.

Cf. A053043, A235459.

def A246427(n):
    T = Combinations(range(n),2)
    K = Combinations(range(n),3)
    W = matrix(ZZ,binomial(n,2),binomial(n,3),lambda i,j:Set(T[i]).issubset(Set(K[j])))
    C = Cone(W.transpose())
    return len(C.facet_normals())
[A246427(n) for n in range(5,8)]

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