The Combinatorics of Cocycles and Borsuk’s Problem.

Posted on June 15, 2011 by Gil Kalai

Cocycles

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_4$ s 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?

This entry was posted in Combinatorics, Convexity, Open problems and tagged Borsuk's conjecture, Cocycles, Frankl-Rodl theorem, Frankl-Wilson theorem, Turan's problem. Bookmark the permalink.

	Gil Kalai on Gil’s Collegial Quantum…
	Louis on Ringel Conjecture, Solved! Con…
	adityaguharoy on Elchanan Mossel’s Amazin…
	sylvainjulien on Hoi Nguyen and Melanie Wood: R…
	Gil Kalai on Hoi Nguyen and Melanie Wood: R…
	shakeddown on Hoi Nguyen and Melanie Wood: R…
	Gil Kalai on Hoi Nguyen and Melanie Wood: R…
	Gil Kalai on Hoi Nguyen and Melanie Wood: R…
	Hoi Neguyen and Mela… on Konstantin Tikhomirov: The Pro…
	Ian Hailes on TYI 30: Expected number of Dic…
	Gil Kalai on The largest clique in the Pale…
	Gil Kalai on The largest clique in the Pale…