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.