I guess now I know how to prove generalized bunkbed conjecture when there are two vertical edges. This is the first nontrivial case since when there is only one vertical edge, the statement follows directly from FKG inequality about increasing events.

I will not uncover more details until I found a way to solve the general case (when there are more than two vertical edges), or I decide to give up on this conjecture and submit a junk paper.

Anyway, I feel quite happy since I am finally able to prove something, rather than giving counterexamples…


March 14, 2010. Uncategorized. Leave a comment.

Ahlswede-Daykin Inequality

Is there any good generalization of Ahlswede-Daykin inequality?

There is a paper by R. Aharoni. But I believe A-D inequality (or FKG) definitely have many different versions of generalizations. One of them can possibly lead to the proof of Bunkbed Conjecture.

March 9, 2010. Uncategorized. Leave a comment.

How to give a good talk

Actually I am only a third-year graduate student now and have very little experience to give a public talk. So here I basically only collect what other people said and wish that I can learn something from them.

1. Presentation

If you are  happened to talk in SIAM or other place, this will be very useful:
How to give a good 20-minute math talk

2. Preparing for the slides

The Latex beamer class page
Norm Matloff’s tutorial on beamer package

March 6, 2010. Uncategorized. Leave a comment.

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.