# 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.

# Is Backgammon in P?

## The Complexity of Zero-Sum Stochastic Games with Perfect Information

Is there a polynomial time algorithm for chess?  Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is “no”. But if we wish to consider the complexity in terms of the number of all possible positions then it is easy to go backward over all positions and determine what is the outcome of the game when we start with each given position.

# Polynomial Hirsch Conjecture 5: Abstractions and Counterexamples.

This is the 5th research thread of polymath3 studying the polynomial Hirsch conjecture. As you may remember, we are mainly interested in an abstract form of the problem about families of sets. (And a related version about families of multisets.)

The 4th research thread was, in my opinion, fruitful. An interesting further abstraction was offered and for this abstraction a counterexample was found. I will review these developments below.

There are several reasons why the positive direction is more tempting than the negative one. (And as usual, it does not make much of a difference which direction you study. The practices for trying to prove a statement and trying to disprove it are quite similar.) But perhaps we should try to make also some more pointed attempts towards counterexamples?

Over the years, I devoted much effort including a few desperate attempts to try to come up with counterexamples. (For a slightly less abstract version than that of EHRR.) I tried to base one on the Towers of Hanoi game. One can translate the positions of the game into a graph labelled by subsets. But the diameter is exponential! So maybe there is a way to change the “ground set”? I did not find any. I even tried to look at games (in game stores!) where the player is required to move from one position to another to see if this leads to an interesting abstract example. These were, while romantic, very long shots.

Two more things: First, I enjoyed meeting in Lausanne for the first time Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss. (EHR of EHRR.) Second, Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick proved (mildly) subexponential lower bounds for certain randomized pivot steps for the simplex algorithm. We discussed it in this post.  The underlying polytopes in their examples are combinatorial cubes. So this has no direct bearing on our problem. (But it is interesting to see if geometric or abstract examples coming from more general games of the type they consider may be relevant.)

So let me summarize PHC4 excitements and, as usual, if I missed something please add it.

# Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

I missed Tom by a few minutes at Mittag-Leffler Institute a year and a half ago

Suppose that $R_n$ is a subset of $\{1,2,\dots, n \}$ of maximum cardinality not containing an arithmetic progression of length 3. Let $g(n)=n/|R_n|$.

Roth proved that $g(n) \ge log logn$. Szemeredi and Heath-Brown improved it to $g(n) \ge log^cn$ for some 0″ src=”http://l.wordpress.com/latex.php?latex=c%3E0&bg=ffffff&fg=000000&s=0&#8243; alt=”c>0″ /> (Szemeredi’s argument gave $c=1/4$.) Jean Bourgain improved the bound in 1999 to $c=1/2$ and in 2008 to $c=2/3$ (up to lower order terms).

Erdös and Turan who posed the problem in 1936 described a set not containing an arithmetic progression of size $n^c$.  Salem and Spencer improved this bound to $g(n) \le e^{logn/ loglogn}$. Behrend’s upper bound from 1946 is of the form $g(n) \le e^{C\sqrt {\log n}}$. A small improvement was achieved recently by Elkin and is discussed here.  (Look also at the remarks following that post.)

In an earlier post we asked: How does $g(n)$ behave? Since we do not really know, will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is? (I still don’t know if softly discussing this or other mathematical problems is a fruitful idea, but it can be enjoyable.)

We even had a poll collecting people’s predictions about $g(n)$.  Somewhat surprisingly 18.18% of answerers predicted that $g(n)$ behaves like $(\log n)^c$ for some $c<1$. Be the answer as it may be, reaching  the logarithmic barrier was considered extremely difficult.

A couple of months ago Tom Sanders was able to refine Bourgain’s argument and proved that $g(n) \ge (\log n)^{3/4}$. Very recently Tom have managed to reach the logarithmic barrier and to prove that

$g(n) \ge (\log n)/(\log \log n)^{5}.$

Quoting from his paper: “There are two main new ingredients in the present work: the first is a way of transforming sumsets introduced by Nets Katz and Paul Koester in 2008, and the second is a result on the $L_p$-invariance of convolutions due to Ernie Croot and Olof Sisask (2010).”

This is a truly remarkable result.

# János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem

Erdős and Pach celebrating another November day many years ago. The Wolf disguised as Little Red Riding Hood. Pach disguised as another Pach.

This post is authored by János Pach

### A Festive Day: November 19

Today is a festive day. It was on this day, November 19, 1863, that Abraham Lincoln presented his famous Gettysburg Address. Seventy nine years later, on the same day (on his own birthday!), Georgy Zhukov, Marshal of the Soviet Union, launched Operation Uranus, turning the tide of the battle of Stalingrad and of World War II. Now sixty eight years later, here we stand (or sit) and experience my very first attempt to contribute to a blog, as Gil has suggested so many times during the past couple of years. But above all, this is a festive day, because earlier today Larry Guth and Nets Hawk Katz posted on arXiv
(http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf) an almost complete solution of Erdös’s Distinct Distances Problem. The story started with Erdős’s 1946 paper published in the American Mathematical Monthly. In this paper, he posed two general questions about the distribution of distances determined by a finite set of points in a metric space.

1. Unit Distance Problem: At most how many times can the same distance (say, distance 1) occur among a set of n points?

2. Distinct Distances Problem: What is the minimum number of distinct distances determined by a set of n points?

Because of the many failed attempts to give reasonable bounds on these functions even in the plane, one had to realize that these questions are not merely “gems” in recreational mathematics. They have raised deep problems, some of which can be solved using graph theoretic and combinatorial ideas. In fact, the discovery of many important combinatorial techniques and results were motivated by their expected geometric consequences. (For more about the history of this problem, read my book with Pankaj Agarwal: Combinatorial Geometry, and for many related open problems, my book with Peter Brass and Willy Moser: Research Problems in Discrete Geometry.)

Erdős conjectured that in the plane the number of unit distances determined by n points is at most $n^{1+c/loglog n}$, for a positive constant c, but the best known upper bound, due to Spencer, Szemeredi, and Trotter is only $O(n^{4/3})$. As for the Distinct Distances Problem, the order of magnitude of the conjectured minimum is $n/\sqrt{log n}$, while the best lower bound was $n^{0.8641...}$, thanks to combined efforts by J. Solymosi – C.D. Toth (2001) and N.H. Katz – G. Tardos (2004).

This was the situation until today! The sensational new paper of Guth and Katz presents a proof of an almost tight lower bound of the order of n/log n. Let us celebrate this fantastic development! In this area of research, it is already considered a great achievement if by introducing an ingenious new idea one is able to improve a bound by a factor of $n^{\delta}$ for some positive δ. Continue reading

# Octonions to the Rescue

## Xavier Dahan and Jean-Pierre Tillich’s Octonion-based Ramanujan Graphs with High Girth.

Update (February 2012): Non associative computations can be trickier than we expect. Unfortunately, the paper by Dahan and Tillich turned out to be incorrect.

Update: There is more to be told about the background of the new exciting paper. In particular, I would like to tell you more about regular graphs with high girth. (I started below.) The Ramanujan graphs story is, of course, also fascinating so at the very least I should give good links.

Michael Atiyah‘s lecture at IAS physics last Friday was entertaining, educational and quite provocative.

The talk started with the following thesis: There are four fundamental forces of nature and there are four division rings over the reals. The real numbers, complex numbers, Quaternions and the Octonions. Atiyah expects that the Octonions will play a major role in physics and will allow a theory which accounts for gravitation. He described some specific steps in this direction and related ideas and connections. At the end of the talk,  Atiyah’s thesis looked more plausible than in the beginning. His concluding line was: “you can regard what I say as nonsense, or you can claim that you know it already, but you cannot make these two claims together.” In any case, it looks that the people in the audience were rather impressed by and sympathetic to the Octonionic ideas of this wise energetic scientific tycoon.

The same day I received an email from Nati Linial. The subject was: “a good topic for your blog” and the email contained just a single link.
http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.2642v1.pdf

Nati is my older academic brother and often I regard our relations as similar to typical relations between older and younger (biological) brothers. When he tells me what to do I often rebel, but usually at the end I do as he says and most of the times he is right.

So I waited a couple of hours before looking at the link. Indeed,  1011.2642v1.pdf is a great paper. It uses Octonions in place of Quaternions for the construction of Ramanujan graphs and describes a wonderful breakthrough in creating small graphs with large girth. Peter Sarnak’s initial reaction to the new paper was: “wow”.

Here is a link to a paper entitled “Octonions” by John Baez, that appeared in Bull. AMS.

### Some background:

Let $G$ be a $k$-regular graph with girth $g$ where $g$ is an odd integer. Continue reading

# The Simonovits-Sos Conjecture was Proved by Ellis, Filmus and Friedgut

Simonovits and Sos asked:

Let $\cal F$ be a family of graphs with N={1,2,…,n} as the set of vertices. Suppose that every two graphs in the family have a triangle in common. How large can $\cal F$ be?

(We talked about it in this post.)

One of the most beautiful conjectures in extremal set theory is the Simonovich-Sos Conjecture, the proposed answer to the question above:

Let $\cal F$ be a family of graphs with N as the set of vertices. Suppose that every two graphs in the family have a triangle in common. Than $|{\cal F}| \le 2^{{{n}\choose {2}}-3}$.

A few weeks ago David Ellis, Yuval Filmus, and Ehud Friedgut proved the conjecture. The paper is now written. The proof uses Discrete Fourier analysis/spectral methods and is quite involved. This is a wonderful achievement.

The example showing that this is tight are all graphs containing a fixed triangle.

Vera Sos’s, a great mathematical hero of mine, is ageless. Nevertheless, she had a birthday conference in early September.  The paper by Ellis, Filmus, and Friedgut is dedicated to Vera on the occasion of her birthday. What a nice birthday gift!

Let me add my own wishes: Happy birthday, Vera!

# Polymath3: Polynomial Hirsch Conjecture 4

So where are we? I guess we are trying all sorts of things, and perhaps we should try even more things. I find it very difficult to choose the more promising ideas, directions and comments as Tim Gowers and Terry Tao did so effectively in Polymath 1,4 and 5.  Maybe this part of the moderator duty can also be outsourced. If you want to point out an idea that you find promising, even if it is your own idea, please, please do.

This post has three parts. 1) Around Nicolai’s conjecture; 1) Improving the upper bounds based on the original method; 3) How to find super-polynomial constructions? Continue reading

# Polymath3 : Polynomial Hirsch Conjecture 3

Here is the third research thread for the polynomial Hirsch conjecture.  I hope that people will feel as comfortable as possible to offer ideas about the problem we discuss. Even more important, to think about the problem either in the directions suggested by others or on their own. Participants who follow the project and think about the issues without adding remarks are valuable.

The combinatorial problem is simple to state and also everything that we know about it is rather simple. At this stage joining the project should be easy.

Let me try to describe (without attemting to be complete) one main direction that we discuss. This direction started with the very first comment we had by Nicolai.

Please do not hesitate to repeat an idea raised by yourself or by other if you think it can be useful.

### Thinking about multisets (monomials).

Let $f^*(d,n)$ be the largest number of disjoint families $F_1, F_2, ..., F_t$ of degree d monomials in the variables $x_1,\dots,x_n$ such that

(*) for i < j < k, whenever $m_1 \in F_i$ and $m_2 \in F_k$, then there exists a monomial $u \in F_j$ such that $gcd(m_1, m_2) | u$.

### Nicolai’s conjecture:

$f^*(d,n)=d(n-1)+1$.

The example that supports this conjecture consists of families with a single monomial in every family.

The monomials are

$x_1^d,$

$x_1^{d-1}x_2$,

$\dots$,

$x_2^d$,

$x_2^{d-1}x_3$,

$\dots$,

$x_n^d$.

There are other examples that achieve the same bound. The bound can be achieved by families whose union include all monomials, and for such families the conjecture is correct.

### The case d=3.

An upper bound by EHRR (that can be extended to monomials) following works of Barnette and Larman on polytopes is $f^*(d,n) \le 2^{d-1}n$. For degree 3 monomials we have a gap

$3n-2\le f^*(3,n) \le 4n-1$.

It may be the case that understanding the situation for $d=3$ is the key for the whole problem.

There is another example achieving the lower bound that Terry found

$F_i := \{ \{a,b,c\}: a+b+c = i+2 \}$ $i=1,2,\dots 3n-2$

### Various approaches to the conjecture

Several approaches to the cojecture were proposed. Using clever reccurence relations, finding useful ordering, applying the method of compression, and algebraic methods. In a series of remarks Tim is trying to prove Nicolai’s conjecture. An encouraging sign is that both examples of Nicolai, Klas, and Terry come up naturally. One way to help the project at this stage would be to try to enter Tim’s mind and find ways to help him “push the car”. In any case, if Nicolai’s conjecture is correct I see no reason why it shouldn’t have a simple proof (of course we will be happy with long proofs as well).

### Constructions

Something that is also on the back of our minds is the idea to find examples that are inspired from the upper bound proofs. We do not know yet what direction is going to prevail so it is useful to remember that every proof of a weaker result and every difficulty in attempts to proof the hoped-for result can give some ideas for disproving what we are trying to prove.

Some preliminary attempts were made to examine what are the properties of examples for d=3 which will come close to the 4n bound. It may also be the case that counterexamples to Nicolai’s conjecture can be found for rather small values of n and d.

Two polls:

# Polymath 3: The Polynomial Hirsch Conjecture 2

Here we start the second research thread about the polynomial Hirsch conjecture.  I hope that people will feel as comfortable as possible to offer ideas about the problem. The combinatorial problem looks simple and also everything that we know about it is rather simple: At this stage joining the project should be very easy. If you have an idea (and certainly a question or a request,) please don’t feel necessary to read all earlier comments to see if it is already there.

In the first post we described the combinatorial problem: Finding the largest possible number f(n) of disjoint families of subsets from an n-element set which satisfy a certain simple property (*).We denote by f(d,n) the largest possible number of families satisfying (*) of d-subsets from {1,2,…,n}.

The two principle questions we ask are:

Can the upper bounds be improved?

and

Can the lower bounds be improved?

What are the places that the upper bound argument is wasteful and how can we improve it? Can randomness help for constructions? How does a family for which the upper bound argument is rather sharp will look like?

We are also interested in the situation for small values of n and for small values of d. In particular, what is f(3,n)? Extending the problem to multisets (or monomials) instead of sets may be fruitful since there is a proposed suggestion for an answer.