Here's an apparently elementary problem which has a rich history and has produced some really interesting combinatorial mathematics. Define FF(k) to be the largest integer t for which there exists an interval graph G and a linear order L on the vertices of G so that: (1) the maximum clique size of G is k, and (2) First Fit uses t colors on G when the vertices are processed in the order specified by L. In 1976, Woodall showed that FF(k) = O(k log k). In 1988, Kierstead showed that FF(k) <= 40k, i.e., FF(k) is linear in k. Kierstead and Qin improved this in 1995 to FF(k) <= 25.8k. From below, it follows from our work on on-line coloring of interval graphs that there exists an e > 0 so that FF(k) > (3 + e)k when k is large. In 1990, Chrobak and Slusarek proved that FF(k) > 4k - 10 when k > 6, and they later improved the lower bound to 4.4k.

In 2003, Pemmaraju, Raman and Varadarajan made a major breakthrough by showing that FF(k) <= 10k and commented that their upper bound might be improved but that the technique wouldn't yield a result better than 8k. Later in 2003, their predictions were confirmed, and their technique was refined by Brightwell, Kierstead and Trotter to obtain an upper bound of 8k. In 2004, Narayansamy and Babu found an even cleaner argument for this bound that actually yields the slightly stronger result: FF(k) <= 8k - 3.

Later in 2004, Kierstead and Trotter improved the lower bound by showing that for every e > 0, FF(k) > (5 - e)k when k is sufficiently large. Most recently, Kierstead and Trotter have shown that the tree-like structures used by various authors to obtain lower bounds cannot yield a better performance ratio than 5. So as k goes to infinity, the ratio FF(k)/k tends to a limit that is somewhere between 5 and 8, and I will bet that 5 is the right answer.

If P and Q are posets, then the dimension of the cartesian product P x Q s at most dim P + dim Q. Baker showed that equality holds if P and Q have (distinct) greatest and least elements. But what about the lower bound? Trivially, dim P x Q is at least the maximum of dim P and dim Q. In 1984, I showed that for every n, m t least 3, there exists an n-dimensional poset P and an m-dimensional poset Q so that dim P x Q = n + m - 2. These posets are taken from the so called "standard examples." But the question is whether these examples tell the whole story. It is conceivable that there is an n-dimensional poset P for which P x P is also n-dimensional. Why not?

Last modified: