Research Interests

Broadly, my research interests are in combinatorial mathematics. My research has focused on the combinatorics of partially ordered sets and online algorithms, but I am also interested in extremal problems in other areas of combinatorics, and computational work using SageMath and Python is playing an increasingly large part of my research program. As a graduate student, I was fortunate to develop collaborations with other early career mathematicians, and my postdoctoral positions expanded my network of collaborators. My closest collaborator, Stephen J. Young, is now at Pacific Northwest National Lab, and I have visited the lab multiple times. This connection has the potential to lead to interesting new applied research directions for me (and students) and the possibility of external funding in conjunction with PNNL. In this overview, I give a summary of my research interests for those who are not specialists in combinatorics. My full research statement (PDF) includes this overview and then provides more detailed information about my research, including problems on which I intend to work in the near future.

Combinatorics of Partially Ordered Sets

Partially ordered sets (or posets) provide combinatorial models for comparison relationships. One example of a poset is the lattice of subsets of a finite set, where the partial order is given by subset inclusion. Many questions about posets, including the two discussed in this statement, involve properties of their linear extensions. A linear extension of a partial order \(P\) is a total order \(L\) on the same ground set that respects \(P\), i.e., if \(x\leq y\) in \(P\), then \(x\leq y\) in \(L\).

One poset parameter on which I have worked is linear discrepancy. The problem of linear discrepancy arises naturally when considering linear extensions of a partial order. If incomparable elements are placed far apart, users in applied settings may create an implicit comparison between them. This comparison unfairly biases against the element that is placed lower, suggesting that it is smaller in the original partial order. Linear discrepancy attempts to quantify this unfairness by measuring the largest distance between incomparable elements in a linear extension and minimizing that distance over all linear extensions.

Part of my linear discrepancy research involved completing the characterization of the posets with linear discrepancy \(2\). We provided a complete list of the forbidden subposets for such posets. My research has also provided upper bounds on a poset's linear discrepancy in terms of the maximum number of elements of the ground set to which any element is incomparable. This work partially addresses one of the original questions asked about linear discrepancy by providing tight bounds for two classes of posets—disconnected posets and interval orders.

An interval order is a poset having the property that we can associate to each point of the poset a closed, bounded interval of \(\mathbb{R}\) in such a way that \(x < y\) in the poset if and only if the interval of \(x\) lies completely to the left of that of \(y\). A semiorder is an interval order with the additional property that all of the associated intervals have the same length. Interval orders arise in many areas of my research and have a great number of uses in applications. Recently, I have completed work that involves enumeration of certain classes of unlabeled semiorders. The tools developed in this process have the potential to be applied to address a number of other problems related to interval orders and semiorders.

The linear extension diameter of a poset measures how different two linear extensions can be. Specifically, the distance between linear extensions \(L_1\) and \(L_2\) is the number of pairs of incomparable elements \(x,y\) for which \(x<y\) in \(L_1\) and \(y<x\) in \(L_2\). We say such an incomparable pair is reversed by \(L_1\) and \(L_2\). The linear extension diameter of a poset is the maximum distance between two of its linear extensions. Some posets have linear extension diameter equal to the number of incomparable pairs, but in general this is not the case. In fact, we have shown that it is not always possible to find a pair of linear extensions that reverse a constant fraction of the total number of incomparable pairs. We have also begun investigating the relationship between linear extension diameter and long-studied poset parameters such as width and dimension.

Online algorithms

Another of my research interests is online algorithms. The traditional framework for algorithms applied to discrete structures provides the algorithm with complete information about the structure throughout execution. In contrast, an online algorithm receives information about a structure one piece at a time and makes an irrevocable decision at each stage. For some applications, the online algorithm framework more accurately represents how a problem must be solved, since it is impossible to supply complete information at the outset. The performance of an online algorithm is generally compared to that of an optimal, perhaps inefficient, algorithm in the traditional framework.

My research has included investigation of online algorithms for linear discrepancy. We have obtained a best possible online algorithm for linear discrepancy on arbitrary posets and shown that when restricted to semiorders it remains best possible, although with a stronger performance guarantee. With an honors thesis student at Washington & Lee University, I have explored online algorithms for linear discrepancy in the context of up-growing orders, which requires that the points of the poset be presented to the algorithm in such a way that each new point is not less than any previously-presented point. I am currently working on preparing a version of the thesis work that is suitable for journal publication.

Stanley depth: A connection to commutative algebra

In 1982, R.P. Stanley made a conjecture involving two parameters of modules over a polynomial ring over a field. Little progress had been made on Stanley's conjecture until about eight years ago, when a team of researchers identified a way to approach some cases of the problem through a partitioning problem on certain posets. This discovery has led to interesting combinatorics, and the increase in activity may be partially responsible for the recent counterexample of Duval et al. Even though Stanley's original conjecture is false, there are still a number of interesting questions open in this area. In Summer 2015, I worked with a W&L undergraduate student on a project involved in resolving a conjecture some coauthors and I had made a few years prior. Although we did not prove the conjecture, computational investigations did lead to a more precise conjecture in the first case to investigate, and the revised conjecture suggests a proof method.