Category Archives: Open problems

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

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. 

Now, what about backgammon?  Continue reading

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.

Continue reading

Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier

Click here for the most recent polymath3 research thread.

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.

Continue reading

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

Click here for the most recent polymath3 research thread.

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!