Tag Archives: Frankl-Rodl theorem

The Combinatorics of Cocycles and Borsuk’s Problem.

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.

Continue reading

The Cap-Set Problem and Frankl-Rodl Theorem (C)

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here is an open discussion post around Roth theorem (March 2009). Here are two “open discussion” posts on the cap set problem (first, and second) from Gowers’s blog (January 2011). These posts include several interesting Fourier theoretic approaches towards improvement of the Roth-Meshulam bound. The second post describes a startling example by Seva Lev.

Suppose that the maximum size of a cap set in \Gamma(n)=\{1,2,3\}^n is n/g(n).  Here is an obvious fact:

The maximum size of a set F in G with the property that every x,y\in G (x \ne y) satisfy x+y \notin G is at most the maximum size of a cap set in G

Proof: Indeed the condition for F is stronger than being a cap set. We require for every x,y \in F x \ne y not only that x+y \notin F but even x+y \notin G.  

Part C.  A more direct relation between Frankl-Rodl’s theorem and the cap set problem and all sorts of fine gradings on subsets of {1,2,…,n}.

In part A we moved from sets avoiding affine lines (cap sets) to sets avoiding “modular lines” and used the Frankl-Rodl theorem to deal with the latter. This may look artificial. Here is a simpler connection between the cap set problem and the Frankl-Rodl theorem.

17. Why weaker forms of the Frankl-Rodl Theorem follow from upper bounds on cap sets.

Consider Continue reading