GaTech Logo - Blue

Current Research Problems

Dimension and Tree-width

In the last couple of years, there have been a flurry of results linking combinatorics for posets with structural graph theory, especially in linking the dimension of a poset with graph theoretic properties of its cover graphs. The roots for this line of research go back almost 50 years, and along the way, things have taken a number of twists and turns. Repeatedly, it has been the case that we (especially me) should have recognized the significance of earlier results and spotted the relevant questions that they should have prompted. From the perspective of hindsight, it all makes sense. But at any moment in time, we had our noses to glued to the problems at hand and could not see the forest for the trees. The description to follow is lengthy, but I promise that if you are a newcomer to the area and you read through to the end, you will want to dive into the several dozen papers whose contents are discussed.

In 1971, in my very first exposure to combinatorics, Ken Bogart got me interested in dimension theory for finite posets. The summer of 1971 was a turning point in my life. I gave up my earlier dream of becoming a professional golfer (totally unrealistic) and began to work hard, really hard, at combinatorial mathematics. Thanks to Ken and Bob Norman, I was invited to spend the 1972--73 academic year at Dartmouth. During the 1971--72 year, preceding this visit, I squirreled away in my office and starting working on dimension theory. As a result, when I arrived at Dartmouth, I already had a bag full of results and I had lots and lots of examples.

During my year at Dartmouth, I learned of a graduate student Bob Kimble, workng with Curtis Greene. Kimble and I independently, and more or less concurrently, discovered a number of the elementary inequalities in dimension theory, and each of us had discovered a number of 3-irreducible posets on 6, 7 and 7 points. I had a couple that Kimble did not have an he had one on 8 points that I didn't know about. It would be another 10 years before the full list of 3-irreducible posets would be determined. This was done independently by Kelly and by me with my first Ph.D. student, John Moore, using quite different methods.

During the 1972--73 academic year, I visited MIT and Kimble and I had some exchanges of results and ideas. Later he wrote me a letter (I still have the original!) and in it, he wrote of his idea for "splitting a point x" in a poset. The idea is that x is removed and replaced by a min-max pair (x',x'') x' < x'', x' < u when x < u in P, and v < x'' when v < x in P. Kimble had proved that splitting a point cannot decrease the dimension but could increase it by 1. Later, I noticed that you could split one, some or even all the points of P. The dimension cannot decrease but could increase by at most 1, regardless of the number of points which are split.

In a number of papers in the literature, this result is attributed to Kimble and his Ph.D. thesis is cited. However, there is no mention of the concept of a split in his thesis, and instead, it is only via this personal communication that the idea was shared. Nevertheless, it is accurate to say that the original idea of a split is due to Kimble, and it is an idea that has continued to have value in very modern papers in this area.

But even in the 1970's I had enough foresight (it didn't take much) to ask what happens if you repeatedly split a poset. Can the dimension increase without bound. I knew that if you start with a trivial one point poset, and split it four times, you get a height 2 poset which has dimension 3 and it has a cover graph which is a tree.

Working with John Moore, I then proved that if P is poset of height 2 and the cover graph of P is a tree, then the dimension of P is at most 3. Subsequently we extended this results to posets of arbitrary height. But then something strange happened. We extended the result for trees by showing that if P is a poset with a planar order diagram and P has either a unique minimal element (traditional called a zero) or a unique maximal element (traditionally called a one), then the dimension of P is at most 3. Our previous result for trees follows from the relatively easy lemma that if the cover graph of P is a tree, then the poset P' obtained from P by adding a zero has a planar order diagram. The historical significance of this result stems from a 1972 theorem of Baker, Fishburn and Roberts: If P has a planar order diagram and has both a zero and a one, then the dimension of P is at most 2.

Using the result on trees, I was then able to show that repeated splitting of a poset can increase the dimension at most by 2, and the result for trees was really the heart of the argument. Regardless, the result on trees seemed to fade into the background, when actually it should have served as an early signal that we have two related but distinct classes of problems: (1) results which depend on the order diagram and (2) results that depend only on the cover graph. The Baker, Fishburn and Roberts theorem is the first category, as I noted in 1978 that there are posets which have arbitrarily large dimension, have a 0 and a 1 and have a planar cover graph. The result on trees is in the second category.

Throughout the 1970's, I was trying to prove that the dimension of a poset with a planar order diagram was bounded. We had the bound of 3 when P has either a zero or a one. Also, I knew that the standard example S_4 had a planar diagram, so I was hopeful of being able to show that a planar poset had dimension at most 4.

However, Kelly gave a construction in 1981 which showed that there are posets of arbitrarily large dimension which have planar order diagrams. And with my hopes for the opposite result dashed, I lost interest in questions of planarity for posets, and didn't return to the subject for a number of years.

The situation began to change with the following beautiful theorem of Schnyder: A graph G is planar if and only if the dimension of its incidence poset (vertices and edges ordered by inclusion) is at most 3. Schnyder published this result in 1989, but his result and his proof were already widely known by the time the paper came out. Also, Schnyder's proof gave an effective algorithm for embedding a planar graph on n vertices in a 2n-4 x 2n-4 grid (integer coordinates).

Schnyder noted in his paper him, that the poset consisting of the vertices, edges and faces of a planar triangulation, ordered by inclusion forms a poset of dimension 4. Furthermore, removing the exterior face lowers the dimension to 3. However, his proof does not extend to arbitrary planar graphs. Subsequently, Brightwell and I succeeded in this effort, and in 1993 we proved that the dimesion of such a poset is 4 when the graph is 3-connected. Furthermore, the dimension is lowered to 3 when any vertex or any face is removed. In 1996, we extended the proof to show that the dimension is at most 4 for any planar multigraph G, with loops and multiple edges allowed. In this more general setting, we lose the additional property that the dimension is lowered by the removal of a vertex or a face. Also, the dimension actually depends on the drawing and not just the graph.

The Brightwell-Trotter proofs are difficult and frankly unappealing. Subsequently Felsner found the "book" proofs and anyone interested in the topic should read his versions. The two proofs are quite different, but he succeeded in capturing the absolutely perfect approach. His papers appear 10 years apart.

For a graph G, the adjacency poset of G is a height 2 poset P with a minimal element x' and a maximal element x'' for every vertex x in G. The elements x' and x'' are incomparable in P. Also, x' < y'' in P if and only if xy is an edge in G. Trivially, the dimension of P is at least as large as the chromatic number of G.

Felsner and I noted that the dimension of the adjacency poset of a planar graph is at most 10 and made such a remark in a couple of papers. However, we didn't write the proof down, and after a period of some years, we forgot how we came up with this bound.

In 2008, I visited Berlin and the first goal, Felsner, Li and I tackled was actually coming up with a proof and writing it down. We actually did better, finding a clean and quite attractive proof of an upper bound of 8. The resulting paper appeared in 2010. Buried in this paper is the following result: If P is a poset of height 2 and the cover graph of P is planar, then the dimension of P is at most 4. The standard example shows that the result is best possible. The proof is a straightforward application of the Brightwell-Trotter theorem for planar maps, i.e., given a height 2 poset with a planar cover graph, we explain why P is a subposet of the poset of vertices, edges and faces of a planar multigraph. A detail here is that we need only the vertices and faces. We don't use the edges. Another detail is that without the Brightwell-Trotter theorem, there is no simple proof of any upper bound.

Felsner and I were quick to conjecture that for every h at least 3, there should be a constant c(h) so that if P is a poset of height h and the cover graph of P is planar, then the dimension of P is at most c(h). But we were unable to make any progress.

With my Ph.D. student 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. The resulting paper, which is condensed considerably with liberal use of phrases such as "it is easy to see" appeared in 2014. Our proof makes extensive use of Ramsey theory and only succeeds in showing the existence of c(h), without providing any useful information about how fast c(h) grows with h.

Subsequently, Felsner, Wiechert and I proved the following theorems: 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. This paper appeared in 2015 but preprints were being circulated by 2012. In this same paper, we proved that if the comparability graph of a poset P is planar, then dim(P) <= 4. This proof again uses Brightwell-Trotter but now, vertices, edges and faces all play essential roles. However, the proof of the result for outerplanar cover graphs is quite different and does not use Brightwell-Trotter. The fact that both results yield an upper bound of 4 is a coincidence.

Now on to discussions of connections with structural graph theory, so we will assume anyone reading this far has some understanding of the parameters for graphs known as tree-width and path-width. If not, take a break and brush up on these ideas.

Gwenael Joret, who had read all these papers (at least he knew all the results), made the following following observations (1) He noted my old theorem with Moore coult be restated: If P is a poset and the tree-width of the cover graph of P is 1, then the dimension of P is at most 3; (2) an outerplanar graph has tree-width at most 2; (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 diameter case.

The conjecture was settled in the affirmative by a team consisting of Gwenael Joret, Piotr Micek, Kevin Milans, Ruidong Wang, Bartosz Walczak and me, and our paper appeared in Combinatorica in 2016. Furthermore, the upper bound on d(t,h) is (roughly speaking) exponential in form. Subsequently, Biro, Keller and Young showed that if P is a poset whose cover graph has path-width 2, then the dimension of P is at most 15. The bound has just been lowered to 5 by Wiechert. Also, Joret, Micek, Wiechert, Wang and I showed that if P is a poset whose cover graph has tree-width 2, then the dimension of P is at most 1276.

As noted first by Joret, the cover graphs of the posets in Kelly's 1981 construction have path-width 3 and Joret, Micek and Wiechert have shown that d(3,h) must grow exponentially with h.

This work was extended to graph minors. First, Walczak (2017) used deep graph theoretic results to show that for every pair (n,h) of positive integers, there is a constant d(n,h) so that if P is a poset whose cover graph excludes a K_n minor and P has height at most h, then the dimension of P is at most d(n,h). Subsequently, Micek and Wiechert (2017+) gave an elegant combinatorial proof and their argument worked for toplogical minors.

Returning to the class of results that depend on the order diagram, after a seminar at MIT in 2014, Richard Stanley asked whether there was any bound on the dimension of a planar poset in terms of the number t of minimal elements. Of course, yes when t = 1. It is a beautiful question on the one hand, but it should have been asked and answered 40 years earlier. Wang and I proved that the dimension of a planar poset with t minimal elements is at most 2t+1. This bound is tight for t = 1 and t = 2. But for t at least 3, we can only show a lower bound of the form t + 3. The gap remains.

Joret, Micek and Wiechert (2017) have shown that the dimension of a planar posets of height h is at most 192h + 96. For posets with planar cover graphs, we have a polynomial upper bound, but no one has been able to settle whether or not the correct bound is linear in h.

The construction of Kelly raised another natural question. Suppose we have a planar poset which does not contain a subposet consisting of two disjoint chains of size k, each element of one chain incomparable with all elements of the other. Is the dimension of P bounded in terms of k, independent of the height of P? Howard, Streib, Trotter, Walcak and Wang answered this question in the affirmative and the reulting bound is polynomial in terms of k. This paper is now in press. However, the argument is very tightly tied to planarity and there does not seem, at least for now, to answer whether there are analogous results for tree-width and graph minors.

Underneath all this work is a very natural and apparently quite difficult question: Does a planar poset of large dimension contain a large standard example? Of course, the answer for posets in general as posets which exclude the standard example S_2 are just the interval orders and they can have arbitrarily large dimension. On the other hand, for posets in general, Biro, Hamburger, Por and I have the following theorem (published in 2016): For every c at least one, there is a pair (n_0, f(c)) so that if n is at least n_0, P is a poset on at most 2n+1 points, and the dimension of P is at least n - c, then P contains a standard example S_d with d at least n- f(c). Our proof provides a quadratic upper bound on the function f(c), and we provided a lower bound of the form f(c) >= c^{4/3}. Using the Lovasz Local Lemma, we now have a lower bound (ignoring log terms) of the form c^{3/2}.

Nevertheless, I feel it is very natural to conjecture that planar posets with large dimension must contain large standard examples. In fact, I think it is also true if the tree-width of the cover graphs is bounded. And in turn, it should be true if we exclude a K_n minor being present in the cover graph, even if we require that it be a topological minor.

Variations on the classic Dushnik-Miller concept of dimension.

In the past two years, there has been considerable interest in two variations of dimension, called Boolean dimension and local dimension, respectively. Most recently, a third variation, known as fractional local dimension has been introduced. In order to understand why these concepts have appeal, it is important to go back what happened to previous attempts in this direction. First, alternative forms of dimension that led to larger values, such as rank, greedy dimension and depth-first-search dimension, produced nice results but did not have lasting interest. Second, interval dimension (representing a poset as the intersection of interval orders) and fractional dimension (the natural linear programming relaxation of dimension) produced some very nice results. For example, both parameters satisfy the removable pair property, a question which remains unanswered for Dushnik-Miller dimension after 70 years. Also, the fractional dimension of an interval order is less than 4 (tight in the limit) and the fractional dimension of a poset P in which each point is comparable with at most k other points is at most k+1. In particular, the fractional dimension of the poset P(1,d;n) consisting of all 1-element and d-element subsets of {1,2, ..., n} ordered by inclusion is d+1, whie the interval dimension of P(1,d;n) is the same as the Dushnik-Miller dimension of P(1,d;n).

When S_n is the n-dimensional standard example, then the interval dimension and the fractional dimension of S_n is also n. It is for this very reason that there would be natural interest in variations of dimension where the parameter was small for standard examples. One such variation was introduced by Gambosi, Nesetril and Tamolo in the 1980's and is called Boolean dimension. To define this concept, consider a family B = {L_1, L_2,\dots,L_t} of linear orders (not linear extensions) of the ground set of P. Then for each pair (x,y) of distinct elements of P, we form a bit string q(x,y,B) of length t by setting coordinate i of this string to be 1 if and only if x < y in L_i$. Now let f be a function which maps bit strings of length t to {0, 1}. The pair (B,f) is called a Boolean realizer of P if for each pair (x,y) of distinct elements of P, x < y in P if and only if f maps q(x,y,B) to 1. The Boolean dimension of P is then the least t for which there is a Boolean realizer (B,f) with |B| = t$. It is easy to see that the Boolean dimension of the standard example S_n is at most 4.

Nesetril and Pudlak (1989) proved that the maximum Boolean dimension of a poset on n points is O(log n) and they conjectured that the Boolean dimension of planar poset is bounded. Recall that this conjecture comes soon after Kelly's construction of planar posets with arbitrarily large Dushnik-Miller dimension. After a couple of papers, the subject of Boolean dimension seemed to recede into the background.


In 2016, Torsten Ueckerdt, at a workshop in Poland, proposed a variation of Dushnik-Miller dimension he called local dimension. Here's how this parameter is defined. Let F = {L_1, L_2, ..., L_t} of linear extension of subposets of P (abbreviated ple's). The family F is called a local realizer of P if the following two conditions are satisfied: (1) if x <= y in P, there is some i with x <= y in L_i, and (2) if (x,y) is an incomparable pair, there is some i with x > y in L_i. The measure of such a local realizer is the maximum number of times any element of P appears, and the local dimension is then the minimum value of the measure taken over all local realizers. Now the local dimension of the standard example S_n is at most 3.

Ueckerdt's notion of local dimension resonated with researchers at the workshop and served to rekindle interest in Boolean dimension as well. This interest has been heightened by the growing list of connections with structural graph theory detailed in the preceding section. Here is a listing of some of the results which have been obtained. Some of these have elementary proofs while others are truly substantive results. The paper "Comparing Dushik-Miller dimension, Boolean dimension and local dimension", by Barrera-Cruz, Prag, Smith and me, abbreviated below as BPST which is Paper 149 on my list of publications, contains several of the proofs and is up-to-date with references to the relevant papers for the other results. This paper is currently under review.

  1. BPST shows that both Boolean dimension and local dimension are unbounded on the class of interval orders.
  2. Gambino, Nesetril and Tamolo show that the Boolean dimension of P(1, d;n) is at most 2d for all n > d. BPST show that equality holds when n is large. BPST also shows that the local dimension of P(1,d;n) tends to infinity with n for fixed d at least 2.
  3. The preceding result shows that local dimension is not bounded in terms of Boolean dimension. On the other hand, Walcak and I (2017+) proved that posets of local dimension 3 have Boolean dimension at most 8443. We also showed that there are posets with arbitrarily large Boolean dimension which have local dimension 4.
  4. BPST shows that the local dimension of a poset is bounded in terms of the path-width of its cover graph, independent of its height. However, BPST also shows that there are posets of arbitrarily large local dimension whose cover graphs have tree-width 3.
  5. Felsner, Meszaros and Micek (2017) show that the Boolean dimension of a poset is bounded in terms of the tree-width of its cover graph, independent of its height.
  6. Meszaros, Micek and I (2017+) show that if every block in a poset P has Boolean dimension at most d, then the Boolean dimension of P is O(2^d). They also show that this inequality is essentially best possible, up to a log factor
  7. Bosek, Grytczuk and I (2017+) show thtat there are posets with arbitrarily large local dimension in which every block in the cover graph has local dimension at most 3. They also show that there are planar posets with arbitrarily large local dimension. The corresponding question for Boolean dimension remains open.
  8. Kim, Martin, Masarik, Shull, Smith, Uzell and Wang (2017+) show that the maximum local dimension of a poset on n points is O(n/log n) and up to a multiplicative constant, this is tight.

Fractional local dimension is just the natural linear programming relaxation version of local dimension. Of course, for a poset P, the fractional local dimension of P is at most the minimum of the fractional dimension of P and the local dimension of P. In a paper, soon to be submitted, Barrera-Cruz, Prag, Smith and I investigate the fractional local dimension of the poset P(1,d;n) consisting of the 1-element and d-element subsets of {1,2,...,n} ordered by inclusion. For a fixed d at least 2, the fractional local dimension of P(1,d;n) increases from 3 and converges to a value f(d). We show that that in the limit, the ratio f(d) over log d/d tends to 1. We actually do much more and determine the value of f(d) to within an additive error of 1.

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.

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