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.
Let be the maximum number of edges in a
-uniform hypergraph which does not contain all the
-subsets of some
-set. When
finding or even estimating
is very difficult. An old conjecture of mine is:
Conjecture: For every even and every
,
is attained (only) by cocycles.
For the question is related to yet another well-known problem: that of the crossing number of a complete graph on
vertices. It is conjectured that the hypergraph whose 4-sets correspond to planar
s in the proposed construction for
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 by
matrix
with
entries. Your hypergraph vertices will correspond to rows and columns of
. 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
matrix is
. 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
.
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 for all
-dimensional unit vectors
.
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 where
is a
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 be a unit vector whose coordinates are indexed by
-subsets of elements from
. Consider the vector indexed by
-subsets whose $S$-coordinate is
for all
-subsets of
. Let
be the set of all such vectors and
be their convex hull.
is a sort of linear-programming relaxation of
-cocycles. I don’t know if for larger odd
‘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 from
, such that for every quadruple
,
. 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 from
, such that
=
and for every $(k+1)$-set
the product of
for all
is 1.
This seems to give a different “relaxation” even for .
Another way to replace hypergraphs by continuous objects is via hypegraph limits.
Question: What are the hypergraph limits of -cocycles for odd
.
We can also ask:
Question: Can flag-algebras shed light on Problem 1?
Pingback: Some old and new problems in combinatorics and geometry | Combinatorics and more
Pingback: Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture | Combinatorics and more
Pingback: Equiangular lines with a fixed angle and other breakthroughs from Yufei Zhao’s blog | Combinatorics and more