A list of my favorite open problems in combinatorics


Content disclaimer: It's really hard for me to judge the difficulty of these problems. They all have an easy-to-understand appearance but may be very difficult indeed, and it's very easy to become addicted to them. So try them at your own risk!


1. Erdős–Faber–Lovász conjecture

The edge disjoint union of  k cliques of size k has chromatic number k.


2. Hedetniemi conjecture 

Given two graphs G and H, define the graph tensor product G*H so that the adjacency matrix of the product graph is equal to the tensor product of two adjacencies matrices. The conjecture is: the chromatic number of  G*H  is equal to the minimum of the two chromatic numbers.


3. Kusner conjecture 

There are at most 2n points in ℝn, such that the pairwise L1 distances between any two points are equal to 1.


4. Revolving door conjecture (Havel)

All the k-subsets and (k+1)-subsets of [2k+1] can be listed on a cycle by alternately adding or deleting one element.


5. Bunkbed conjecture (Kasteleyn)

Given a graph G, make another copy of it and connect all the corresponding vertices (say u and u', v and v' and etc.)  by "vertical edges" (think about setting up a bunkbed). Now take every edge independently in some probability such that the probability of taking uv is same as that of u'v'. Then the probability that there exists a path from u to v is no less than the probability that there exists a path from u to v'.


6. Unit distance problem (Erdős)

Among n points on the plane, how many pairs of points can be at unit distance from each other?