GaTech Logo - Blue

Selected Research Problems

In the list below, I start with current problems that I am actively working on these days. Then I list some of my favorite problems that continue to retain my interest even though I have tried without success (at least to date) to solve them.

Recall that the dimension of a poset P, denoted dim(P), is the least d so that there is a family {L_1, ..., L_d} of linear extensions of P such that x <= y in P if and only if x <= y in L_i for all i = 1, ..., d. As an elementary example of a poset with a given dimension, for d >=2, the standard example S_d is the height 2 poset with Min(P) = {a_1, ..., a_d}, Max(P) = {b_1, ..., b_d} and a_i < b_j if and only if i is not equal to j. Trivially, dim(S_d) = d. For a poset P, define the standard example number of P, denoted se(P), to be 1 if P does not contain the standard example S_2; otherwise se(P) is the largest d such that P contains S_d. We then have the trivial inequality dim(P) >= se(P).

A Poset Analogue of Chi-Boundedness

Over the years, there has been considerable interest in finding classes of graphs where chromatic number is bounded in terms of clique number, independent of the number of vertices. The poset analogue is to find classes of posets where dimension is bounded in terms of standard example number, independent of the number of elements in the poset.

In 2022, Blake, Hodor, Micek, Seweryn and I succeeded in solving a problem that I have frequently referred to as the single most challenging problem I've every worked on. For many years, it sat untouched because no one, including me, had any idea how to begin an attack. The result is that the class of posets with planar cover graphs is dim-bounded, i.e., dimension is bounded in terms of standard example number. There were two important preliminary results. First, Blake, Micek and I proved the weaker result that the class of posets that have a zero and a planar cover graph is dim-bounded. Later, the five person group, with Seweryn play a lead role, proved that the class of planar posets is dim-bounded. The full general result is considerably more complicated. Two preliminary versions of the proof were written, and a polished version is now being prepared. The full proof runs more than 50 pages. The binding function is polynomial although we believe that the truth is linear. This is the case for planar posets. Watch this space for updates.

Boolean Dimension and planarity

The following concepts were introduced Nesetril and Pudlak in the 1980's. Let P be a poset and let B = {L_1, L_2,\dots,L_t} be a family of linear orders (not linear extensions) of the ground set of P. Then for each pair (x,y) of distinct elements of P, 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, denoted Bdim(P), is then the least t for which there is a Boolean realizer (B,f) with |B| = t. It is easy to see Bdim(P) <= dim(P) for every poset P. Also, Bdim(S_d) 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 asked whether the Boolean dimension is bounded for the class of planar posets. In fact, we believe this is true for the larger class of posets with planar cover graphs. In the same paper mentioned just above, Blake, Micek and I proved that the Boolean dimension of of a poset with a planar cover graph is at most 13 if the poset has a unique least element. Again, we believe we are making genuine progress on this vexing problem.

Dimension, Standard Examples and Size

For graphs in general, the absence of a clique of specified size limits chromatic number in terms of size. For example, the maximum chromatic number of a triangle-free graph is O(n/log n)^{1/2}).

Here is the poset analogue. For a fixed d >=2 and n tending to infinity, let f(d,n) denote the maximum value of the dimension of a poset on n points if se(P) < d. The class of posets with standard example number 1 is the class of interval orders, and the value of f(2,n) is known to within an additive error of 5. Roughly speaking f(2, n) is lg lg n + (1/2 +o(1))lg lg lg n. Biro, Hamburger and Por proved that for fixed d >= 3, f(d,n) = o(n), but this leaves open the possibility that f(d,n) is a slow growing function like f(2,n). However, Biro, Hamburger, Kierstead, Por, Wang and I have recently proved (2019) that there is a constant c_d < with 0 < c_d < 1 so that f(d,n) > n^{c_d}. It would be very interesting to determine if there is an upper bound on f(d,n) of the same form.

Stability Analysis

For a positive integer c, let sa(c) be the least integer such that if P is a poset on 2n+1 points, and dim(P) >= n - c, then se(P) > = n - f(c). Biro, Hamburger, Por and I proved (2019) that the function sa(c) is well defined and satisfies sa(c) = O(c^2). We also showed that (ignoring constant multiples) sa(c) >= c^{4/3}). Subsequently, we gave two different probabilistice proofs that improve the lower bound (ignoring poly-log terms) to c^{3/2}. I now believe the lower bound of 3/2 is the right answer.

Maximum Degree

For a poset P, and a point x in P, let U_P(x) count the number of elements of P that are larger than x. Also, let U_P(x) count the number of elements of P that are less than x. Then define Delta_P(x) = max{Delta_U(x), Delta_D(x)} and Delta(P) is the maximum value of Delta_P(x) taken over all x in P. For graphs, we have Brooks' Theorem that asserts that the chromatic number of a graph is at most 1 + Delta(G). When G is connected, equality holds only when G is a complete graph or an odd cycle. For posets, it is natural to ask whether dimension is bounded in terms of maximum degree, i.e., does there exist a function f so that if Delta(P) = k, then dim(P) <= f(k). The existence of such a function was established by Rodl and me, but our bound was only 2k^2+2. In 1986, Furedi and Kahn improved this (using the local lemma) to f(k) < 50 k log^2 k. In 1991, Erdos, Kierstead and I proved a lower bound of the form f(k) > c k log k. In 2018, Scott and Wood have improved the upper bound to f(k) < k log^{1+o(1)} k. Their proof features a very clever application of the local lemma. Perhaps the o(1) term in the exponent is necessary. Also, no one has yet been able to give an explict construction to show that f(k) > k+1.

Dimension and Height

In 2014, Streib and I proved that dimension is bounded in terms of height for posets with planar cover graphs. Joret, Micek and Wiechert (2017) have shown that the dimension of a poset P of height h is at most 192h + 96 when P has a planar diagram. Kozik, Micek and I have proved (2019+) that if P is a height h poset and the cover graph of P is planar, then dim(P) = O(h^6). In 2021, Gorsky and Seweryn improved this upper bound to O(h^3). However, their proof uses a key lemma from the KMT paper as a "black box". Blake and I have tweaked this proof to improve the bound to O(h^2). Most likely, the correct exponent is 1. A construction of Joret, Micek and Wiechert gives a lower bound of 2h - 2.

An Extremal Problem for Vectors

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. Felsner, Krawczyk and Micek 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. Lason, Micek, Streib, Walczak and I verified the conjecture when w = 3, and we gave a number of optimal constructions. These constructions 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.

The Monotone Hamiltonian Path Problem

Now that the notorious Middle Levels Conjecture has been settled in the affirmative by Torsten Muetze, perhaps researchers will take a fresh look at the following variation posed in 1995 by Felsner and me. We 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. 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. In 2019, 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 in the exponent has been lowered, 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)}. In 1984, I showed that dim(S_d X S_d) = 2d - 2. It is conceivable that for every $d >= 2, there is a poset P for which dim(P x P) = dim(P) = d. Why not?

Updated January 23, 2024.  Valid XHTML 1.0 Strict