The Combinatorics of Cocycles and Borsuk’s Problem.


Definition:  A k-cocycle is a collection of (k+1)-subsets such that every (k+2)-set T contains an even number of sets in the collection.

Alternative definition: Start with a collection \cal G of k-sets and consider all (k+1)-sets that contain an odd number of members in \cal G.

It is easy to see that the two definitions are equivalent. (This equivalence expresses the fact that the k-cohomology of a simplex is zero.) Note that the symmetric difference of two cocycles is a cocycle. In other words, the set of k-cocycles form a subspace over Z/2Z, i.e., a linear binary code.

1-cocycles correspond to the set of edges of a complete bipartite graph. (Or, in other words, to cuts in the complete graphs.) The number of edges of a complete bipartite graph on n vertices is of the form k(n-k). There are 2^{n-1} 1-cocycles on n vertices altogether, and there are n \choose k cocycles with k(n-k) edges.

2-cocycles were studied under the name “two-graphs”. Their study was initiated by J. J. Seidel.

Let e(k,n) be the number of k-cocycles.

Lemma: Two collections of k-sets (in the second definition) generate the same k-cocycle if and only if  their symmetric difference is a (k-1)-cocycle.

It follows that e(k,n)= 2^{{n}\choose {k}}/e(k-1,n). So e(k,n)= 2^{{n-1} \choose {k}}.

A very basic question is:

Problem 1: For k odd what is the maximum number f(k,n) of (k+1)-sets  of a k-cocycle with n vertices?

When k is even, the set of all (k+1)-subsets of {1,2,…,n} is a cocycle.

Problem 2: What is the value of m such that the number ef(k,n,m) of k-cocycles with n vertices and m k-sets is maximum?

When k is even the complement of a cocycle is a cocycle and hence ef(k,n,m)=ef(k,n,{{n}\choose{k+1}}-m). It is likely that in this case ef(k,n,m) is a unimodal sequence (apart from zeroes), but I don’t know if this is known. When k is odd it is quite possible that (again, ignoring zero entries) ef(n,m) is unimodal attaining its maximum when m=1/2 {{n} \choose {k+1}}.

Borsuk’s conjecture, Larman’s conjecture and bipartite graphs

Karol Borsuk conjectured in 1933 that every bounded set in R^d can be covered by d+1 sets of smaller diameter. David Larman proposed a purely combinatorial special case (that looked much less correct than the full conjecture.)

Larman’s conjecture: Let \cal F be an $latex r$-intersecting  family of k-subsets of \{1,2,\dots, n\}, namely \cal F has the property that every two sets in the family have at least r elements in common. Then $\cal F$ can be divided into n (r+1)-intersecting families.

Larman’s conjecture is a special case of Borsuk’s conjecture: Just consider the set of characteristic vectors of the sets in the family (and note that they all belong to a hyperplane.) The case r=1 of Larman’s conjecture is open and very interesting.

A slightly more general case of Borsuk’s conjecture is for sets of 0-1 vectors (or equivalently \pm 1 vectors. Again you can consider the question in terms of covering a family of sets by subfamilies. Instead of intersection we should consider symmetric differences.

Borsuk 0-1 conjecture: Let \cal F be a family of subsets of \{1,2,\dots, n\}, and suppose that the symmetric difference between every two sets in \cal F has at most t elements. Then $\cal F$ can be divided into n+1  families such that the symmetric difference between any pair of sets in the same family is at most t-1.

Cuts and complete bipartite graphs

The construction of Jeff Kahn and myself can be described as follows:

Construction 1: The ground set is the set of edges of the complete graph on 4p vertices. The family \cal F consists of all subsets of edges which represent the edge sets of a complete bipartite graph with 2p vertices in every part. In this case, n={{4p} \choose {2}}, k=4p^2, and r=2p^2.

It turns out (as observed by A. Nilli) that there is no need to restrict ourselves to  balanced bipartite graphs. A very similar construction which performs even slightly better is:

Construction 2: The ground set is the set of edges of the complete graph on 4p vertices. The family \cal F consists of all subsets of edges which represent the edge set of a complete bipartite graph.

Let f(d) be the smallest integer such that every set of diameter 1 in R^d can be covered by f(d) sets of smaller diameter. Constructions 1 and 2 show that f(d) >exp (K\sqrt d). We would like to replace d^{1/2} by a larger exponent.

The proposed constructions.

To get better bounds for Borsuk’s problem we propose to replace complete bipartite graphs with higher odd-dimensional cocycles.

Construction A: Consider all (2k-1)-dimensional cocycles  of maximum size (or of another fixed size) on the ground set \{1,2,\dots,n\}.

Construction B: Consider all (2k-1)-dimensional cocycles on the ground set \{1,2,\dots,n\}.

A Frankl-Wilson/Frankl-Rodl type problem for cocycles

Conjecture: Let \alpha be a positive real number. There is \beta = \beta (k,\alpha)<1 with the following property. Suppose that

(*) The number of k-cocycles on n vertices with m edges is not zero

and that

(**) m>\alpha\cdot {{n}\choose {k+1}}, and m<(1-\alpha){{n}\choose {k+1}}. (The second inequality is not needed for odd-dimensional cocycles.)

Let \cal F be a family of k-cocycles such that no symmetric difference between two cocycles in \cal F has precisely m sets. Then

|{\cal F}| \le 2^{\beta {{n}\choose {k}}}.

If true even for 3-dimensional cocycles this conjecture will improve the asymptotic lower bounds for Borsuk’s problem.  For example,  if true for 3-cocycles it will imply that f(d) \ge exp (K d^{3/4}). The Frankl-Wilson and Frankl-Rodl theorems have a large number of other applications, and an extension to cocycles may also have other applications.

Crossing number of complete graphs, Turan’s (2k+1,2k) problems, and cocycles

The question on the maximum number of sets in a k-cocycle when k is odd is related to several other (notorious) open problems.

Let T(n,r,k) be the maximum number of edges in a k-uniform hypergraph which does not contain all the k-subsets of some r-set. When k>2 finding or even estimating T(n,r,k) is very difficult. An old conjecture of mine is:

Conjecture: For every even k and every n, T(n,k+1,k) is attained (only) by cocycles.

For k=4 the question is related to yet another well-known problem: that of the crossing number of a complete graph on n vertices. It is conjectured that the hypergraph whose 4-sets correspond to planar K_4s in the proposed construction for K_n with minimum number of crossings is optimal also for the Turan (4,5) problem and also for the maximum size of a 3-cocycle on n vertices.


Belated update (Dec 2014): 

In 1988 D. de Caen, D. Kreher, and J. Wiseman \cite {dCKW} found a better, beautiful example: consider a n/2 by n/2 matrix M with \pm 1 entries. Your hypergraph vertices will correspond to rows and columns of M. It will include all 4-tuples with 3 rows or with 3 columns and also all sets with 2 rows and 2 columns such that the product of the four matrix entries is -1. The expected number of edges in the hypergraph for a random \pm 1 matrix is (11/16 +o(1)) {{n} \choose {4}}As for upper bounds, the best-known upper bounds are stronger for cocycles. Yuval Peled  used in his M. Sc. thesis a flag-algebras technique to show that f(n,4) \le {{n} \choose {4}} (0.6916+o(1)).

Relaxation: what could be the analog of tensor powers and positive definite matrices

Another variation of constructions 1 and 2 is

Construction 3: The set x\otimes x for all n-dimensional unit vectors x.

This set is simply the set of (normalized) rank-1 definite matrices and its convex hull is the unti ball in the set of all  definite matrices. It is quite possible that this set will give better bounds than construction 2 (which can be regarded as the subset of vectors x\otimes x where x is a \pm 1 vector), which will reduce the lowest dimension where Borsuk’s conjecture is false to below 100. This will follow from the conjecture on subsets of the unit spheres without two orthogonal vectors, which we discussed on this post. (See also this post.)

What could be an analog of Construction 3 for higher-dimensional cocycles?

Construction C?: Let x be a unit vector whose coordinates are indexed by k-subsets of elements from \{1,2,\dots,n\}. Consider the vector indexed by (k+1)-subsets whose $S$-coordinate is \prod x_R for all k-subsets of S. Let X be the set of all such vectors and Y be their convex hull.

X is a sort of linear-programming relaxation of k-cocycles. I don’t know if for larger odd k‘s this is the “correct”  relaxation of the set of cocycles and if the diameter is increased when we move from cocycles to Y.

Seidel’s original definition of 2-graphs was as a function f from {\Omega \choose 3}\to {-1,1}, such that for every quadruple \alpha,\beta,\gamma,\delta, f(\alpha,\beta,\gamma)f(\alpha,\beta,\delta)f(\alpha,\gamma,\delta)f(\beta,\gamma,\delta)=1. Construction C is based on trying to relax the second definition of cocycles. We can try instead to relax the first definition by replacing the $\latex \pm$ vectors by arbitrary real vectors of the same norm.

Construction D?: Consider all functions f from {\Omega \choose k} \to R, such that \sum f^2(x) = n\choose k and for every $(k+1)$-set T the product of f(S) for all S \subset T, |S|=k is 1.

This seems to give a different “relaxation” even for k=2.

Another way to replace hypergraphs by continuous objects is via hypegraph limits.

Question: What are the hypergraph limits of k-cocycles for odd k.

We can also ask:

Question: Can flag-algebras shed light on Problem 1?

About these ads

2 thoughts on “The Combinatorics of Cocycles and Borsuk’s Problem.

  1. Pingback: Some old and new problems in combinatorics and geometry | Combinatorics and more

  2. Pingback: Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s