## Cocycles

**Definition**: A -cocycle is a collection of -subsets such that every -set contains an even number of sets in the collection.

**Alternative definition:** Start with a collection of -sets and consider all -sets that contain an odd number of members in .

It is easy to see that the two definitions are equivalent. (This equivalence expresses the fact that the -cohomology of a simplex is zero.) Note that the symmetric difference of two cocycles is a cocycle. In other words, the set of -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 vertices is of the form . There are 1-cocycles on vertices altogether, and there are cocycles with edges.

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

Let be the number of -cocycles.

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

It follows that So .

A very basic question is:

**Problem 1:** For odd what is the maximum number of -sets of a -cocycle with vertices?

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

**Problem 2:** What is the value of such that the number of -cocycles with vertices and -sets is maximum?

When is even the complement of a cocycle is a cocycle and hence . It is likely that in this case is a unimodal sequence (apart from zeroes), but I don’t know if this is known. When is odd it is quite possible that (again, ignoring zero entries) is unimodal attaining its maximum when .

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

Karol Borsuk conjectured in 1933 that every bounded set in can be covered by 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 be an $latex r$-intersecting family of -subsets of , namely has the property that every two sets in the family have at least elements in common. Then $\cal F$ can be divided into -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 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 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 be a family of subsets of , and suppose that the symmetric difference between every two sets in has at most elements. Then $\cal F$ can be divided into families such that the symmetric difference between any pair of sets in the same family is at most .

## 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 vertices. The family consists of all subsets of edges which represent the edge sets of a complete bipartite graph with vertices in every part. In this case, , , and .

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 vertices. The family consists of all subsets of edges which represent the edge set of a complete bipartite graph.

Let be the smallest integer such that every set of diameter 1 in can be covered by sets of smaller diameter. Constructions 1 and 2 show that . We would like to replace 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 -dimensional cocycles of maximum size (or of another fixed size) on the ground set .

**Construction B:** Consider all -dimensional cocycles on the ground set .

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

**Conjecture:** Let be a positive real number. There is with the following property. Suppose that

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

and that

(**) , and . (The second inequality is not needed for odd-dimensional cocycles.)

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

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 . 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 -cocycle when is odd is related to several other (notorious) open problems.

Continue reading →