Research Interests

My research interests are in combinatorics. Particularly, I am interested in the combinatorics of partially ordered sets, extremal combinatorics, and online algorithms for graphs and posets. My doctoral dissertation focused on three questions related to the linear discrepancy of partially ordered sets. I also conduct research on Stanley depth of monomial ideals, a topic on the boundary of the combinatorics of partially ordered sets and commutative algebra.

My research statement (PDF) discusses the research I've published or submitted as well as the problems on which I plan to work in the near future. Eventually, the information from this document will be broken up into subsections for the website, but at the moment some of the links in the menu at the left contain information about my research projects. If no information is available for a particular area, you may view my list of publications, which contains links to my papers.

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. As a graduate student, I was fortunate to develop collaborations with other early career mathematicians, and I am working to further develop those relationships while expanding my network of collaborators through my postdoctoral position. This overview gives a summary of my research interests for those who are not specialists in combinatorics. The subsequent sections provide 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.

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\lt y\) in \(L_1\) and \(y\lt 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 recently 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 a particular subclass of posets (semiorders) it remains best possible, although with a stronger performance guarantee. There have recently been several new results related to another online problem for posets, and it appears that these new ideas may lead to resolving a problem that has been open for more than 30 years.

Stanley depth: A connection to commutative algebra

Nearly 30 years ago, 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 recently, 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 in addition to progress on Stanley's conjecture. There are a number of questions yet to be resolved in this area through deeper collaboration between combinatorists and algebraists. To date, the algebraists and combinatorists working in this area have tended to work separately. In the coming years, I plan to continue collaborating with combinatorists interested in these problems and to develop new collaborations with the algebraists who are best positioned to identify the most important questions to answer.

\(\bigoplus uK[Z] \cong\mathcal{P} = \left\{[A,B]\colon A,B\in \mathcal{D}\right\}\)