Current Research Problems
Here's an apparently elementary problem which has a rich history and has produced some really interesting combinatorial mathematics. Let FF(k) be the largest integer for which First Fit can be forced to use t colors on an interval graph with maximum clique size k. In 1976, Woodall showed that FF(k) = O(k log k). In 1988, Kierstead showed that FF(k) <= 40k, and 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 - 9, when k >= 4, and they later improved the lower bound to 4.4k - C, where C is a large constant.
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. Howard has recently pointed out that one can actually show that FF(k) <= 8k-4.
Later in 2004, Kierstead and Trotter gave a computer proof that FF(k) >= 4.99k - C. This technique was subsequently refined to show that FF(k) >= 4.99999k - C. And in 2009, D. Smith showed that for every e > 0, FF(k) >(5 - e)k, when k is sufficiently large. It can also be 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. I will bet a nice bottle of wine that 5 is the right answer.
Some of the deepest and most important research on partially ordered sets involves correlation inequalities. In this setting, the family of all linear extensions of a poset is considered a probability space with each extension being an equally likely outcome. With this interpretation, we can then speak of the probabilty that x is greater than y and denote this quantity by Pr[x > y]. In 1980, Shepp proved the so-called XYZ theorem:
Pr[x > y] <= Pr[x > y| x > z]
His argument used the FKG inequality for distributive lattices. Then in 1984, Fishburn used the Ahlswede/Daykin four functions theorem to prove that the inequality is strict when x, y and z form a 3-element antichain.
Recently, Graham Brightwell and I have been able to provide combinatorial proofs of these theorem, i.e., we provide natural injections between sets of the appropriate cardinalities. These arguments provide additional insights into the structure of the poset and the enable us to say far more about the behavior of the error terms.
Now we want to tackle the log-concave results developed by Stanley using the Alexandrov/Fenchel inequalities for mixed volumes: For a fixed element x, the height sequence of x is log-concave. To date, we have only some partial success to report. Specifically, we have been able to prove the result when x is a fixed point and there are exactly two point incomparable with x. In this case, the height sequence of x contains only three non-zero terms and we are able to show that the product of the middle term is at least as large as the product of the other two terms. Quite recently, Csaba Biro and I have found a very clean proof of this special case, but even the challenge of extending it to the case where there are three points incomparable to x presents hurdles that we don't see how to get over.
Lately, I have been taking a fresh look at two old problems. The first one is the notorious middle two levels problem: Let n = 2k+1 be an odd integer and consider the subset lattice consisting of all subsets of {1, 2, ..., n}. The middle two levels consisting of the sets of size k and k+1 form a bipartite graph, and it is conjectured that this graph is hamiltonian. The conjecture is known to be true for n <= 15. The origins of this problem are not completely clear, but it was first posed to me by Ivan Havel in the summer of 1982. Havel in fact showed me an old reprint of his in which he had posed the problem long before it became well known here in the U.S.
The second problem is not as well known but seems similar in spirit. Felsner and I conjectured that for all n, there is a listing S_1, S_2, ..., S_t (where t = 2^n) of all subsets of {1, 2, ..., n} so that (1) the listing is a hamiltonian path, i.e., every subset is listed exactly once and for all i = 1, 2, ..., t-1, S_{i+1} differs from S_i by either adding or deleting a single element; (2) S_1 is the empty set; and (3) If 1 <= i< j <= t and S_j is a subset of S_i, then j = i+1.
Here are admissible paths when n = 3 and when n = 4 (with 0 denoting the empty set, and braces and commas suppressed):
0, 1, 12, 2, 23, 3, 13, 123
0, 1, 12, 2, 23, 3, 34, 4, 24, 124, 14, 134, 13, 123, 1234, 234
Unlike the middle two levels problem, the origin of this one is completely clear. It comes from efforts to determine the maximum chromatic number of the diagram of an interval order of given height. There are some interesting partial results on this problem, and one of their consequences is a construction which gives a cycle in the middle two levels which is a positive fraction of the maximum possible size. Also, Biro and Howard have a very nice proof of the existence of a suitable path that extends up through all the subsets of size 3. This is a neat problem.
In 1973, I conjectured that every finite partially ordered set with three or more points contains a pair whose removal decreases the dimension by at most one. Papers by Hiraguchi, Bogart, Reuter and me contain many examples of sufficient conditions which guarantee the existence of such a pair. In making the original conjecture, I made the stronger assertion that the removal of any critical pair decreased the dimension by at most 1. But Reuter constructed a 4-dimensional counterexample to this stronger conjecture on 10 points. Ironically, an incorrect diagram for Reuter's example appears in (at least) two different papers, and Reuter himself didn't provide a diagram, as he was motivated by the concept of what is called Ferrer's dimension. In any case, Reuter's counterexample is correct. Subsequently, Kierstead and I generalized his counterexample and constructed an infinite sequence of counterexamples for this stronger assertion for all dimensions starting with 4. Still it is reasonable to believe that (1) there is some critical pair whose removal decreases the dimension by at most 1; and (2) for every x, there is some other point y so that the removal of x and y decreases the dimension by at most 1.
This conjecture asserts that every finite partially ordered set that is not a chain contains an incomparable pair (x,y) so that
1/3 <= Prob[x < y] <= 2/3
Kahn and Saks proved that there is always a pair for which
3/11 <= Prob[x < y] <= 8/11
Brightwell, Felsner and I improved these bounds by showing that there exists a pair (x,y) with
(5-5^{.5})/10 <= Prob[x < y] <= (5+5^{.5})/10
In a certain sense, this result is best possible, since it is tight for a class of countably infinite posets for which the notion of Prob[x < y] makes sense. The BFT proof makes use of the Alexandrov/Fenchel inequalities and the machinery developed by Kahn and Saks. An interesting correlation inequality called the "Cross Product Inequality" is conjectured in BFT, and a special case is proven. This case is enough for the inequality on balancing pairs. In a recent popular lecture titled The Top Ten Theorems on Partially Ordered Sets, I listed this result at the very top and credited it to the comprehensive list: Ahlswede, Alexandrov, Brightwell, Felsner, Fenchel, Fishburn, Kahn, Saks, Stanley and Trotter.
In 1984, Fishburn and I asked whether every 3-dimensional poset is a circle order, i.e., can it be represented as the inclusion order of circles (disks) in the plane. Every 2-dimensional poset is a circle order; in fact, you can put all centers on a line. Not all 4-dimensional posets are circles orders. In particular, the 14-element poset consisting of all non-empty subsets of {1,2,3,4} is not a circle order. By the Alon-Scheinerman degrees of freedom argument, almost all 4-dimensional posets are not circle orders.
On the other hand, for each m >= 3, if P is a 3-dimensional poset, then P is the inclusion order of regular m-gons. So if m >>> |P|, don't m-gons look a lot like circles? However, Scheinerman and Weirman showed that Z X Z X Z is not a circle order, and Fon der Flass subsequently showed that 2 X 3 X N is not a circle order.
The issue was settled in 1998 when Fishburn, Felsner and I proved that if n is sufficiently large, the finite 3-dimensional partially ordered P_n which is the cartesian product of three chains, each of length n, is not a circle order. We actually proved a much stronger result. We showed that P_n is not a sphere order, i.e., there is no integer d for which P_n is the inclusion order of a family of spheres in d-dimensional euclidean space. Lately we have been looking at other geometric objects. Every 3-dimensional poset is an ellipse order, in fact we may require all the major axes to be co-linear. On the other hand, we conjecture that not all 4-dimensional posets are ellipse orders. In a similar vein, every n-dimensional poset has an inclusion representation using cubes (in general position) in euclidean 2n-space. This is best possible for n = 1 and n = 2, but already for n = 3, we don't know whether every 7 - dimensional poset has an inclusion representation using cubes in 3-space.
Paul Erdos posed many challenging problems in combinatorial geometry. Here are two of my favorites. Let n be a positive integer. Consider a set of n points in the euclidean plane, and let u(n) be the maximum number of pairs of points that are at unit distance apart. Also, let d(n) be minimum number of distinct distances determined by these points.
In the 1980's, Spencer, Szemeredi and I proved that u(n) < c n^{4/3}, while Chung, Szemeredi and I showed d(n) > n^{4/5}/log^c n. Szekely used crossing arguments to dramatically lower the constant in the bound for u(n) and to remove the log term from the denominator in the bound for d(n). Szekeley is also able to show that this many distances occur from a single point. Solymosi and Toth have improved the lower bound on d(n) to c n^{6/7}, but we are still far away from the answer conjectured by Erdos: u(n) = n^{1+c/log log n} and d(n) = n/{log n}^.5.
For many years, I have enjoyed a long standing and very productive research collaboration with my colleague Hal Kierstead. The next two problems represent topics on which we have worked together - and in fact he knows more about these subjects than I do. The first problems is estimate the function f(k,n), defined as the least number of colors required to color on-line a k-chromatic graph. Alon showed f(3,n) >= log^2 n, and Saks, Lovasz and I showed f(3,n) <= n/log log n. In a major breakthrough, Kierstead showed that f(3,n) = O(n ^2/3 / log^2/3 n). Kierstead's argument also gives a sublinear bound for f(k,n). Still, the lower bounds are considerably weaker.
Estimate the function f(n), defined as the least number of chains required to partition on-line any partially ordered set of width n. It is not trivial to show that f(n) exists. In 1981, Kierstead showed that f(n) <= (5^{n+1} - 1)/4. And in 2009, Bosek and Krawczyk improved this bound to f(n)=O(n^{16 log n}, which provides a subexponential upper bound. The real goal is to settle whether f(n) is polynomial. From below, the best lower bound is f(n) >= (1 -o(1))n^2.
If P and Q are posets, and P X Q is the cartesian product of P and Q, then dim(P x Q) <= 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) >= max{dim(P), dim(Q)}. For n >= 3, let S_n denote the poset consisting of the 1-element and n-1-element subsets of {1, 2, ...,n} ordered by inclusion. S_n is called the standard example of an n-dimensional poset. In 1984, I showed that dim(S_n X S_n) = 2n - 2. It is conceivable that for every $n >= 2, there is a poset P for which dim(P x P) = dim(P) = n. Why not?
Updated January 20, 2007.
