Open questions about posets

Question

Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They are also related to sorting and to other questions in the theory of computing. I am asking for a list of open questions and conjectures about posets.

Answer 1

The 1/3-2/3 conjecture is probably considered one of the most significant open problems about finite posets; see the Wikipedia page: https://en.wikipedia.org/wiki/1/3%E2%80%932/3_conjecture.

Answer 2

Here's a problem that I believe has little chance of being resolved, and it's also not so clear to me what the motivation behind the problem is, but it involves some very pretty algebraic combinatorics.

Stanley (in his PhD thesis) defined a poset $P$ to be Gaussian if for every $m\geq 0$ we have $$ \sum_{I \in J(P\times [m])} q^{\#I} = \frac{\prod_{i=1}^{r}(1-q^{h_i+m})}{\prod_{i=1}^{r}(1-q^{h_i})}$$ where $r$ and $h_1,\ldots,h_r$ are constants independent of $m$. (Here $J(P \times [m])$ is the distributive lattice of order ideals of the Cartesian product of $P$ and the chain poset $[m]=\{1,2,\ldots,m\}$.)

Using results from Standard Monomial Theory, in "Bruhat Lattices, Plane Partition Generating Functions, and Minuscule Representations", Proctor proved that if $P$ is a minuscule poset, then $P$ is Gaussian. Here a minuscule poset is a certain finite poset coming from a minuscule representation of a semisimple Lie algebra; these have been classified- see Proctor's paper for the list. Furthermore, Proctor conjectured that the minuscule posets are the only Gaussian posets.

I think a few things are known (due to some mixture of Proctor and Stanley) about this conjecture: that a Gaussian poset $P$ is a disjoint union of connected Gaussian posets; that a connected Gaussian poset has to be graded; that $r$ has to be the number of elements of $P$; that the $h_i$ have to be the ranks of the elements $p\in P$; maybe some more things too. But like I said I think the full conjecture is pretty hopeless.

Answer 3

Here's another classic from algebraic combinatorics.

In his PhD thesis "Ordered Structures and Partitions", Stanley introduces the $(P,\omega)$-partition generating function of a labeled poset $(P,\omega)$. This is defined to be $K(P,\omega) := \sum_{\sigma \in A^r(P,\omega)} x^{\sigma}$, where $A^r(P,\omega)$ is the set of all reverse $(P,\omega)$-partitions (i.e., fillings of the poset $P$ with entries in $\mathbb{N}$ obeying certain inequalities depending on $\omega$ and the order structure of $P$), and where we use the notation $x^f := \prod_{i \geq 1} x_i^{\#f^{-1}(i)}$. Stanley shows that $K(P,\omega)$ is always a quasisymmetric function. When $P$ is the poset of a skew Young diagram and $\omega$ is a compatible ``Schur labelling'' then $K_{(P,\omega)}$ is in fact a symmetric function (namely, a skew Schur funciton). Stanley's conjecture is that $K_{(P,\omega)}$ is a symmetric function if and only if $(P,\omega)$ is isomorphic to $(P_{\lambda/\mu},w)$, where $\lambda/\mu$ is a skew-shape and $w$ is a Schur labelling of $P_{\lambda/\mu}$. There has been some progress on this conjecture due to Malvenuto; I don't know the exact status of what has been proved.

Answer 4

Let $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2$ be a boolean function. Ordering $\mathbb{F}_2$ so that $0<1$, we say that $f$ is monotone if $f(x_1,\ldots,x_n) \le f(y_1, \ldots, y_n)$ whenever $x_1 \le y_1, \ldots, x_n \le y_n$. The Dedekind number $M(n)$ is the number of monotone Boolean functions of $n$ variables, up to logical equivalence.

Equivalently, $M(n)$ is the number of Boolean functions (up to logical equivalence) that can be expressed without negation, or the number of access structures on $n$ people. For example,

$$(x_1 \wedge x_2) \vee (x_1 \wedge x_3) \vee (x_2 \wedge x_3)$$

is counted by $M(3)$, and corresponds to the access structure where any pair of people, or all three people, form an authorized set. In general the minimal authorized sets form an antichain in the poset of subsets of $\{1,\ldots, n\}$, so $M(n)$ is the number the number of antichains in $\mathcal{P}(\{1,\ldots,n\})$. Since the maximal subsets in an abstract simplicial complex form an antichain, $M(n)$ is also the number of abstract simplicial complexes on $\{1,\ldots, n\}$.

The antichain interpretation makes it plausible that

$$\log M(n) \sim \binom{n}{\frac{n}{2}} \sim \sqrt{\frac{2}{\pi}} \frac{2^n}{\sqrt{n}} $$

and this was proved by Kleitman.

An important open problem (mentioned in the comments above) is to give a more precise asymptotic estimate for $M(n)$, and to determine the value of $M(n)$ for small $n$. At the moment, $M(n)$ is known precisely only for $n \le 7$. The linked paper has the best known asymptotic formula, due to Korshunov.

Answer 5

What about the Stanley–Stembridge conjecture on (3+1)-free posets? Given a poset $P$ with vertex set $V = \{1,2,\ldots,n\}$, define the symmetric function $X_P$ in countably many indeterminates $x_1, x_2, \ldots$ by $$X_P := \sum_{\kappa:V\to\mathbb{N}} x_{\kappa(1)}x_{\kappa(2)}\cdots x_{\kappa(n)}$$ where the sum is over all maps $\kappa:V \to\mathbb{N}$ such that the pre-image $\kappa^{-1}(i)$ of every $i\in\mathbb{N}$ is a totally ordered subset of $P$. Then the conjecture is that if $P$ is (3+1)-free (i.e., that $P$ contains no induced subposet isomorphic to the disjoint union of a 3-element chain and a 1-element chain) then the expansion of $X_P$ in terms of elementary symmetric functions has nonnegative coefficients.

This conjecture grew out of certain positivity conjectures about immanants. Guay-Paquet has reduced the conjecture to the case of unit interval orders (i.e., posets that are both (3+1)-free and (2+2)-free), and the unit interval order case has a graded generalization (due to Shareshian and Wachs), which has close connections with representation theory and Hessenberg varieties.

Answer 6

Let $P$ be a (not necessarily finite) poset such that each element covers and is covered by a finite number of elements. Then we can define the operators $U,D\colon \mathbb{Q}P\to\mathbb{Q}P$ on the vector space of formal linear combinations of elements of $P$ by $U(p) = \sum_{p\lessdot q} q$ and $D(p) = \sum_{q\lessdot p}q$. Such a poset $P$ is called $r$-differential if it is locally finite, graded, with a unique minimal element, and these up and down operators satisfy $DU-UD=rI$ (where $I$ is the identity map). See https://en.wikipedia.org/wiki/Differential_poset.

The two prominent examples of $1$-differential posets are Young's lattice and the Young-Fibonacci lattice. It is known that these are the only $1$-differential lattices, although this was only proved relatively recently by Byrnes (https://conservancy.umn.edu/handle/11299/142992). The open problem is: are all $r$-differential lattices products of Young's lattice and the Young-Fibonacci lattice?

Answer 7

The fish-scale conjecture: In every poset not containing an infinite antichain there exist a chain $C$ and a decomposition of the vertex set into antichains $A_i$, such that $C\cap A_i \neq \emptyset$ for all $i\in I$. See Conjecture 10.1 in this article by Ron Aharoni and Eli Berger.

Interestingly, this conjecture is implied by the following covering problem in hypergraphs: Let $H=(V,E)$ be a hypergraph with the following properties:

1. $\bigcup E = V$,
2. Any subset of $e\in E$ is a member of $E$, and
3. whenever $S\subseteq V$ and every $2$-element subset of $S$ belongs to $E$, then $S\in E$.

Then there is $J\subseteq E$ such that whenever $K\subseteq E$ has the property that $\bigcup K = V$ then $|J\setminus K| \leq |K\setminus J|$. (In that case $J$ is said to be a "strongly minimal cover" because it covers $V$ "more efficiently" in some sense, than any other cover.)

This covering problem is mentioned in Conjecture 10.3.(2) of the same paper.

Answer 8

Find a nice expression for the number of down-sets (order ideals) of a product of four finite chains (totally ordered sets), $|\bf2^{(\bf k\times \bf m\times \bf n\times \bf r)}|$, where $k,m,n,r$ are positive integers and "$\bf k$" denotes the $k$-element chain, $\{0,1,\dots,k-1\}$.

Richard P. Stanley writes (on page 83 of Ordered Structures and Partitions), "Nothing significant seems to be known in general about" this quantity.

http://www-math.mit.edu/~rstan/pubs/pubfiles/9.pdf#page=87

The MacMahon formula for $|\bf2^{(\bf k\times \bf m\times \bf n)}|$ is $\prod_{h=0}^{k-1}\prod_{i=0}^{m-1}\prod_{j=0}^{n-1}\frac{h+i+j+2}{h+i+j+1}$.

I'd be willing to accept a nested summation.

See page 2 of James Propp, "Generating Random Elements of Finite Distributive Lattices," Electronic Journal of Combinatorics 4 (1997), R15. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i2r15/pdf#page=2

See Theorem 3.3 on page 114 of Joel Berman and Peter Koehler, "Cardinalities of Finite Distributive Lattices," Mitteilungen aus dem Mathem. Seminar Giessen 121 (1976), 103-124. http://homepages.math.uic.edu/~berman/freedist.pdf#page=7

Answer 9

Let $P,Q$ be posets. Let $Q^P$ denote the poset of order-preserving maps from $P$ to $Q$, where $f\le g$ if $f(p)\le g(p)$ for all $p\in P$.

A poset has the fixed point property if for all $f\in P^P$, there exists $p\in P$ such that $f(p)=p$.

If $P$ and $Q$ have the fixed point property, does $P\times Q$?

Roddy, Rutkowski, and Schroeder proved the answer is "yes" if $P$ is finite.

If $P,Q$ are finite and non-empty, does $P^P\cong Q^Q$ imply $P\cong Q$? Duffus and Wille proved that the answer is "yes" if $P$ and $Q$ are connected.

Dwight Duffus and Rudolf Wille, "A theorem on partially ordered sets of order-preserving mappings," Proceedings of the American Mathematical Society 76 (1979), 14-16

Conjecture. One of these questions is important. The other may not be of interest to anyone but myself.

Answer 10

A ranked poset is called a symmetric chain order, or SCO, if it can partitioned into rank symmetric, saturated chains. Such posets are particularly nice, as they are rank-symmetric, unimodal, and have the strong Sperner property. If $P$ and $Q$ are SCO's, then so is $P\times Q$. In particular, the Boolean poset ${\bf 2}^n$ of subsets of $\{1,2,\dots,n\}$, which is the product of $n$ copies of a two-element chain, is an SCO.

Let $G$ be a subgroup embedded in the symmetric group $S_n$. This induces an action on ${\bf 2}^n$ where $gS=\{g(s):s\in S\}$. Define the quotient poset ${\bf 2}^n/G$ on the orbits of this action, with $[S]\le [T]$ if some $S'\subseteq T'$ for $S'\in[S]$ and $T'\in [T]$.

Several familiar posets are realized as quotients of ${\bf 2}^n$.

• $L(m,k)$, the sub-poset of Young's lattice consisting of partitions which fit in an $m\times k$ box. Here, $n=mk$, and the subgroup is the wreath product $S_m\wr S_k$.

• the poset of isomorphism classes finite simple graphs on $n$ vertices with the subgraph relation.

Conjecture: For all $n\ge 0$ and all $G\le S_n$, ${\bf 2}^n/G$ is an SCO.

Partial results:

• $L(4,n)$ is an SCO.

• Letting $G=\langle (1\,2\,\dots\,n)\rangle$, then the necklace poset ${\bf 2}^n/G$ is an SCO.

Answer 11

So in mathematics, one can iterate operation of mapping a group to its automorphism group transfinitely to obtain the automorphism tower of a group. And the automorphism tower always terminates. The next natural follow up question to this result is to ask about the congruence lattice tower where one begins with a lattice.

Now, if $L$ is a lattice, then the mapping $e:L\rightarrow\mathrm{Con}(L)$ defined by letting $(x,y)\in e(a)$ if and only if $x\vee a=y\vee a$ is a lattice homomorphism precisely when the lattice $L$ is distributive. Since we want $L$ to embed in $\mathrm{Con}(L)$, we want to restrict our attention to distributive lattices. Furthermore, if $L$ is a lattice, then $\mathrm{Con}(L)$ is always a distributive lattice, so we have no choice but to only consider distributive lattices in the congruence lattice tower problem. It is a not too difficult exercise to show that the mapping $e:L\rightarrow\mathrm{Con}(L)$ is a lattice isomorphism if and only if $L$ is a finite Boolean algebra. Therefore, the congruence tower problem is quite easy and boring for the variety of all distributive lattices. The congruence tower problem for frames instead of distributive lattices is a difficult open question of mathematical significance.

A frame is a complete lattice $L$ that satisfies the infinite distributivity law $x\wedge\bigvee R=\bigvee_{r\in R}(x\wedge r)$. The frames $L$ are precisely the complete lattices which happen to be complete Heyting algebras. If $L$ is a frame, then an equivalence relation $\simeq$ on $L$ is said to be a frame congruence if $\bigvee_{i\in I}x_{i}\simeq\bigvee_{i\in I}y_{i}$ whenever $x_{i}\simeq y_{i}$ for $i\in I$ and $r\wedge s\simeq t\wedge u$ whenever $r\simeq t,s\simeq u$.

If $L$ is a frame, then let $\mathfrak{C}(L)$ denote the collection of all congruences of the frame $L$. Then $\mathfrak{C}(L)$ is itself a frame, and there is a mapping $e:L\rightarrow\mathfrak{C}(L)$ where $(x,y)\in e(a)$ if and only if $x\vee a=y\vee a$ which happens to be a frame homomorphism.

One can define $\mathfrak{C}^{\alpha}(L)$ for all ordinals $\alpha$ by letting $\mathfrak{C}^{\alpha+1}(L)=\mathfrak{C}(\mathfrak{C}^{\alpha}(L))$ for all $\alpha$ and where for limit ordinals $\gamma$, we have $\mathfrak{C}^{\gamma}(L)=\varinjlim_{\alpha<\gamma}\mathfrak{C}^{\alpha}(L)$ (direct limits are taken in the category of frames).

If $e:L\rightarrow\mathfrak{C}^{\alpha}(L)$ is the canonical mapping, then for each complete Boolean algebra $B$, the mapping $\mathrm{Hom}(\mathfrak{C}^{\alpha}(L),B)\rightarrow\mathrm{Hom}(L,B)$ in the category of frames where $\phi\mapsto\phi\circ e$ is a bijection (this result should convince you that $\mathfrak{C}^{\alpha}(L)$ is important).

So there are frames $L$ where the tower $(\mathfrak{C}^{\alpha}(L))_{\alpha}$ never stops growing. If $B$ is a complete Boolean algebra, then the canonical mapping $e:B\rightarrow\mathfrak{C}(B)$ is an isomorphism, and if the tower $(\mathfrak{C}^{\alpha}(L))_{\alpha}$ stops growing, then $\mathfrak{C}^{\alpha}(L)$ is a complete Boolean algebra for large enough $\alpha$.

Now, in all known examples, either $(\mathfrak{C}^{\alpha}(L))_{\alpha}$ never stops growing or the tower $(\mathfrak{C}^{\alpha}(L))_{\alpha}$ stops growing at or before around the 4th step. Suppose that $\alpha$ is an ordinal. Then is there a frame $L$ where $\alpha$ is the least ordinal with $\mathfrak{C}^{\alpha}(L)=\mathfrak{C}^{\beta}(L)$ for $\beta\geq\alpha$ in the sense that the canonical frame homomorphism between these frames is an isomorphism?

Answer 12

A finite, non-empty poset $P$ has dimension $k\in\mathbb N_0$ if $k$ is the smallest number of chains (totally ordered sets) into a product of which one can order-embed $P$.

$S_3$ is the standard example; it has dimension $3$.

See W. T. Trotter, "The dimension of the cartesian product of partial orders," Discrete Math. 53 (1985), 255-263.

https://trotter.math.gatech.edu/papers/49.pdf

Also see George Bergman, "Some frustrating questions on dimensions of products of posets" (2024), preprint.

https://math.berkeley.edu/~gbergman/papers/poset_dim.pdf