List of combinatorial problems

I have a list of problems that I am currently thinking about. It’s quite difficult to judge which one is easy or whether a conjecture is true. But all of them seems to be important enough, in the sense of the possibility to initiate a whole new branch of combinatorics. I also mark their importance (in my opinion) by stars. Certainly there are many other important open problems, here is just a very small collection of them, those I spent at least a couple of hours on.

A. Graph coloring:

1. Erdos-Faber-Lovasz conjecture  ✭✭✭✭
2. Hedetniemi conjecture ✭✭✭✭
3. Chromatic number of Cayley graph ✭✭✭✭
4. Doubly critical graph conjecture ✭✭

Common points: Chromatic number is NP-hard, but for graphs with nice algebraic structures, maybe we can characterize it. It’s also possible to find some other also-NP-hard equivalent description of chromatic number, which is easier to study for specific problems.

B. Traditional Graph Theory:

1. Seymour’s second neighborhood conjecture ✭✭✭✭

C. Correlation Inequality:

1. Bunkbed conjecture ✭✭✭✭

D. Extremal Combinatorics:

1. Generalization of Sperner Lemma ✭✭✭

E. Combinatorial Geometry:

1. Unit distance problem ✭✭✭✭
2. Kusner conjecture (l1 distance) ✭✭✭✭

April 17, 2010. Uncategorized. Leave a comment.


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.

A digraph whose longest directed path<=k is k-colorable

To prove this theorem, we have the following steps: (first I will assume the graph G is weakly connected)

(i) Find a maximal subgraph H of G which contains no directed cycles.
(ii) Prove that this subgraph H can be k-colored such that if v->u, then the color number c(v) is strictly less than c(u).
(iii) If we add any directed edges into H, it must result a cycle. Use (ii) to show the two end vertices of this edge has different colors.

The main difficulty lies in step (ii). Let’s also divide it into several small steps: (remember that now our graph contains no directed cycles.)

(ii.1) Find a longest directed path (its length is k), choose its starting vertex v. Then for every vertex u which can be reached from v, give it the color c(u)= maximal length of directed path from v to u.
(ii.2) Prove that for every u1, u2 s.t. c(u1)=c(u2), there is no edge between them. Therefore, so far our coloring is proper.
(ii.3) From the remaining vertices, find a vertex w such that it maximize the following thing:
the maximal length of paths from w which doesn’t touch any colored vertices except the last one – the color number of the last vertex.
Then for any uncolored x, let c(x)=maximal length of paths from w to x which doesn’t touch any colored vertices. Like in step (ii.1) and (ii.2), we can also prove that so far the coloring is proper.
(ii.4) Continue this process, since G is weakly connected. We will finally get a proper coloring of all the vertices.

April 25, 2008. Uncategorized. Leave a comment.