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}).

Advertisements

March 3, 2010. Tags: . Uncategorized.

Leave a Comment

Be the first to comment!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback URI

%d bloggers like this: