CURRENT  RESEARCH  PROBLEMS

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.

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.

In the last year, 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.

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.  Known to be true for  n  at most  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 a reprint in which the problem was posed.

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)  S_2  is not a subset of  S_1, and (2) for all  i  with 1 <  t-1, S_{i+1  is not a subset of the union of  S_i  and  S_{i-1}.  Unlike the first 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.  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 on  10 points. Subsequently, Kierstead and I generalized this 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.

Every finite partially ordered set which 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 countably infinite posets. 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.

Felsner, Fishburn and I showed that exists a finite 3-dimensional partially ordered set which cannot be represented as the inclusion order of a family of spheres in d-dimensional Euclidean space, regardless of how large  d  is. This proof solves a long standing problem first posed by Fishburn and me (for circles) in 1984 at the Banff Conference on Ordered Sets.  Lately we have been looking at other geometric objects.  Although 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 the problem of determining (or estimating) the functions  u(n)  and  d(n)  so that a set of  n  points (a) has at most  u(n)  pairs at unit distance, and (b) determines at least  d(n)  distinct distances. 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. In the last year, Szekely has 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.  But we are still far away from the answer conjectured by Erdos:  n  points determine at most  n^{1+c/log log n}  unit distances and at least  n/log^.5 n  distinct distances.

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)  is at least  log^2 n, and Saks, Lovasz and I showed  f(3,n) is at most  n/log log n. In a major breakthrough in the last year, Kierstead has shown that  f(3,n) = O(n ^2/3 / log^2/3 n). Kierstead's argument gives a sublinear bound for  f(k,n). Still, the lower bounds are considerably weaker.

Estimate the function  (n), defined as the least number of chains required to partition on-line any partially ordered set of width  n.  Kierstead showed that  (n) <= (5^{n+1} - 1)/4,  and Szemeredi showed that  f(n) >= n(n+1)/2. In particular settle, whether  f(n)  is polynomial in  n.  Recently, Felsner settled the  n = 2  case, by showing that a poset of width  2  can be partitioned into  5  chains.  This is already a complicated result, and no progress has been made on the general problem for the last  15  years.

The Dimension of Cartesian Products

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?