GaTech Logo - Blue

Current Research Problems

An Extremal Problem for Vectors

We consider a problem posed by Tomasz Krawczyk: Let w be a positive integer and consider vectors of length w with integer coordinate values. Such vectors can be partially ordered by setting A <= B when A[i] <= B[i] for each i = 1,2,...,w. For a positive integer k, two vectors A and B are said to be k-crossing when there exist distinct coordinates i and j so that A[i] >= k + B[i] and B[j] >= k + A[j]. So incomparable vectors are 1-crossing. Let f(k,w) denote the largest integer t for which there is a family of t vectors so that: (a) all vectors in the family are pairwise incomparable, i.e., the family is an antichain; and (b) there are no k-crossing pairs. Krawczyk conjectured that f(k) = k^{w-1}. This conjecture holds trivially if either k = 1 or w = 1. Also, it is easy to see that it holds when w = 2, so the first non-trivial case is w = 3 with k > 1. For example, the family (0,1,2), (1,2,0),(2,0,1),(1,1,1) shows that f(2,3) >= 4 = 2^2. In joint work with M. Lason, P. Micek, N. Streib and B. Walczak, we have verified the conjecture when w = 3. The resulting paper is Number 130 in my list of publications. We have also developed a number of optimal constructions, which help to explain why the conjecture seems challenging in general.

Dimension and Tree-width

In the last couple of years, there have been a flurry of results connecting the dimension of a poset with geometric/topological properties of its cover graph. Felsner, Wiechert and I showed that if the cover graph of a poset P is outerplanar, then dim(P) <= 4; this inequality is tight. We also showed that when the height of P is 2, this can be lowered to dim(P) <= 3, which is also tight. The proofs of the upper bounds are elegant, and the tightness of the general upper bound seems to require a nice example. Note that outerplanar graphs have tree-width at most 2. A construction of Kelly shows that for every d >=2, there is a poset P_d so that (a) the cover graph of P_d is planar and the dimension of P_d is d. Kelly's elegant construction takes the standard example S_d of a d-dimensional poset, which has height 2 and embeds it as a subposet of P_d. The height of P_d grows linearly with d. Here we note that the cover graphs of the posets constructed by Kelly have path-width 3. With Felsner and Li, I showed that if P has height 2 and the cover graph of P is planar, then dim(P) <= 4. This proof appears in paper Number 123 on my home page. You may note that the proof is an easy corollary to the work I did with Brightwell on the dimension of the poset of vertices, edges and faces of a planar multigraph - with loops and multiple edges allowed. Sans this machinery, we know of no simple proof of any upper bound. You may also note that this inequality is a minor result of Number 123, with the major results of this paper focusing on adjacency posets of planar graphs. In this paper, we made the following conjecture: For every integer h, there exists a constant c_h so that if P is a poset of height h and the cover graph of P is planar, then dim(P) <= c_h. So the theorem with Felsner and Li shows that c_2 exists and is 4. But the proof techniques do not extend to cover the case h > 2. With Noah Streib, we worked for two years on this conjecture, first settling the case h = 3 and with another year's work, extended our proof for general h and settling the conjecture in its entirety. This is paper Number 129 on my home page. Subsequently, Gwenael Joret - who had read this paper - made the following following observations (1) He noted my old paper with J. Moore in which we proved that the dimension of a poset whose cover graph is a tree is at most three; (2) He knew of the results with Felsner and Wiechert on outerplanar graphs; and (3) Although planar graphs can have large tree-width in general, the proof Streib and I gave showing that the dimension of a poset with a planar graph is bounded in terms of its height used a reduction to the case where the diameter is bounded in terms of the height. He knew that the tree-width of a planar graph with bounded diameter is bounded. Based on this evidence, Joret made the following striking conjecture: For every pair (t,h) of positive integers, there is a constant d = d(t,h) so that if P is a poset of height h and the tree-width of the cover graph of P is at most t, then the dimension of P is at most d. It is easy to show that this conjecture, if true, yields the theorem with Streib as a corollary, of course via the same reduction to the bounded diamter case. (2012) The conjecture has just been settled in the affirmative! Gwenael Joret, Piotr Micek, Kevin Milans, Ruidong Wang, Bartosz Walczak and I have just polished off the conjecture. The argument (forgive me for saying so) is beautiful! 2014 update: Joret, Micek, Wang, Wiechert and I have shown that if P is a poset whose cover graph has tree-width at most 2, then the dimension of P is at most 2554. Previously, Biro, Keller and Young had proved a parallel result for path-width. Most recently, Walczak has proven the master theorem: For every pair h, C, where h is a positive integer and C is a proper minor closed class of graphs, there is a constant d = d(t,C) so that if P is a poset, the height of P is at most h and the cover graph of P belongs to C, then the dimension of P is at most d. Walczak's result is stronger than all the other results, except that it doesn't say that d is independent of h when C is either the class of graphs of tree-width at most 1 or the class of graphs of tree-width at most 2. An amazing result indeed!

First Fit Coloring of Interval Graphs

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 FF(k)/k <= 8, when k is large. Later in 2003, their predictions were confirmed, and their technique was refined by Brightwell, Kierstead and Trotter to obtain an upper bound of 8k on FF(k). 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 paper Number 135 on my list, Smith, Kierstead and I show 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.

Correlation Inequalities

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. In paper Number 126 on my list, 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.

Hamiltonian Path and Cycle Problems

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.

2014 Update: The middle two levels problem has just been solved by Torsten Mutze. Congratulations to Torsten!

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. Two relevant papers are Number 96 on my list (joint with Felsner) where the original problem is posed and the connections with other problems are detailed. One additional detail is buried in the survey paper, Number 103 on my list.

There are some interesting partial results on this problem. For example, 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.

The Removable Pair Conjecture

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.

The "1/3 - 2/3" Conjecture

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.

Geometric Inclusion Orders

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. This past summer, I found a slick proof of the following result. If P is a poset and the cover graph of P is a tree, then P is a circle order. Had this result been known 15 years ago, it would have been cited as evidence that every 3-dimensional poset should be a circle order, something that we now know is not true. It would still be of considerable interest to determine whether every poset of width 3 is a circle order.

On-Line Graph Coloring

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.

On-Line Chain Partitioning

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. Since then, the constant 16 has been lowered to 14, but 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.

The Dimension of Cartesian Products

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 August 16, 2014.  Valid XHTML 1.0 Strict