Milan Haiman

Research

Here are a couple recent projects I have worked on.

Dimension Theory of Posets

The Dushnik-Miller dimension of a poset P, denoted \dim(P), is the least d such that P embeds into a product of d chains. This notion of dimension was introduced by Dushnik and Miller in 1941 and has been extensively studied.

An important example is the boolean hypercube \mathcal{Q}^n, viewed as the poset on subsets of [n], ordered by inclusion. It is easy to show that \dim(\mathcal{Q}^n)=n. A more interesting problem is to analyze the dimension of suborders of \mathcal{Q}^n. For I\subseteq [0,n], we let \mathcal{Q}^n_I be the suborder of \mathcal{Q}^n on subsets S of [n] for which |S|\in I. An elementary result in dimension theory implies that it suffices to consider only the case when I=\{k,\ell\} consists of just two layers of the hypercube. The dimension of \mathcal{Q}^n_{\{k,\ell\}} has been studied in detail. Several results are known but we don’t have exact asymptotic formulas in terms of k,\ell,n in most regimes. For a detailed survey on the known results, see this paper of Kierstead.

A notable open problem is the case of two consecutive layers of the hypercube. In particular, there is an exponential gap in the best known bounds for \dim(\mathcal{Q}^n_{n/2,n/2+1}).

In my paper from Duluth 2021, I introduced multiset analogs of the above posets, as well as a weighted multiset generalization to use techniques from known work to make progress on the dimension of divisibility orders. An interesting open problem here is to understand how the choice of weights for the elements 1 through n affect the dimension of the corresponding poset.

Irreducibility

Given a class of combinatorial objects with some notion of addition, we can define irreducible objects as those which cannot be written as a sum of other objects. A simple example is the set of nonnegative integer valued nondecreasing functions on a poset. Then the irreducible objects correspond to antichains in the poset. For a nice poset like the boolean hypercube, we know how to count the number of antichains asymptotically.

During SPUR 2022, I worked with Yuan Yao on understanding irreducible objects in more complicated classes of combinatorial objects. The main object we worked with was supermodular functions on the boolean hypercube. These functions are equivalent to generalized permutohedra, which were introduced by Postnikov. We have made progress on understanding the number of irreducible supermodular functions, but a precise asymptotic formula is not known.

A useful model problem for irreducibility is the following. Consider multisets whose elements are subsets of [N]. We say that such a multiset is balanced if each element of [N] appears in it the same number of times. The irreducible objects in this problem can be understood quite precisely using results in random matrix theory. Balanced multisets are a model problem for generalized permutohedra because the latter is a equivalent to a modification of the former, by restricting which multisets can be used and modifying the “balanced” condition.