My mathematical diseases

Richard Lipton has an article on mathematical disease. My own definition of mathematical disease is quite similar: it must be simple in form, easily explainable to a non-specialist in a few minutes. Moreover, there should be more than one person exclaiming “how can such a problem be open?”. Here I also list some problems I consider as my favourite “diseases”.

1. Erdos-Faber-Lovasz Conjecture

The main difficulty of this conjecture is, how to bound the chromatic number from above effectively? There are some lower bounds for chromatic number, like using eigenvalues of adjacency matrix, or topological bounds developed by Lovasz in proof of Kneser Conjecture. However for upper bound, we knew very little except giving an explicit coloring. Although an asymptotic version of this conjecture has been proven by J.Kahn, I believe the exact version, if indeed correct, requires more understanding about chromatic number.

2. Hedetniemi Conjecture

A reformulation of this conjecture can reduce it to proving the chromatic number of some graphs can be bounded from above. So maybe it has some connection with the previous problem.

3. Bunkbed Conjecture

There is no article on this conjecture in wikipedia on mathworld. But it is very easy in appearance, and once proved, it can be written as a theorem in any textbook of probability in graduate level. The most general form is as follows, given a graph G, consider its Cartesian product with complete graph of two vertices K_2. Now consider the model such that every edge in this graph appears independetly in some probability. The only restriction is the probability of any edge uv in G and that of its corresponding edge u'v' are equal. The conjectures says the probability that there is a path connecting u and v is greater than or equal to the probability that there is a path connecting u and v'.

4. Unit distance problem

More precisely, I am talking about the problem of counting the maximum number of pairs of unit distances for n points in \mathbb{R}^2. The other, perhaps more famous, problem of computing chromatic number of unit distance graph of \mathbb{R}^2 seems much more difficult.

5. Kusner Conjecture

I also don’t find a survey paper on this conjecture. It’s so natural and beautiful that every middle school student can have some thought on it. The conjecture is: consider the l^1 metric (sum of absolute values)┬áin the d-dimensional real space \mathbb{R}^d, there can be at most 2d points whose pairwise distances are exactly 1. This bound can be reached by looking at the octahedron with vertcies (\frac{1}{2},0,0), (-\frac{1}{2},0,0), (0,\frac{1}{2},0), (0,-\frac{1}{2},0), (0,0,\frac{1}{2}), (0,0,-\frac{1}{2}).

March 3, 2010. Tags: . Uncategorized. Leave a comment.