28
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Union closed sets conjecture of Frankl. Gerhard "Master Of The Obvious, Apparently" Paseman, 2019.02.06. $\endgroup$ – Gerhard Paseman Feb 6 at 17:56
  • 3
    $\begingroup$ I have voted to close on the grounds the question is too broad. It seems any open problem related to sorting, searching, chains, antichains, cardinals, ordinals, surreal numbers, least fixed points, ... might be relevant. $\endgroup$ – Mark Wildon Feb 6 at 19:16
  • 5
    $\begingroup$ To be clear: The questions need to be questions about posets. For example, Frankl's union closed set conjecture is a great problem but it is outside the scope of the question as I see it. Gil, "if in doubt, make it a comment rather than an answer" Kalai. $\endgroup$ – Gil Kalai Feb 6 at 19:37
  • 5
    $\begingroup$ Here is the list from Ivan Rival that Gil Kalai mentioned: link.springer.com/content/pdf/10.1007%2FBF00334860.pdf. The last problem is interesting: I think it is saying "determine the Dedekind numbers (en.wikipedia.org/wiki/Dedekind_number)"; but it's too much to hope for an exact formula, right? $\endgroup$ – Sam Hopkins Feb 6 at 19:48
  • 7
    $\begingroup$ Frankl's conjecture can be reformulated in terms of posets. See Enumerative Combinatorics, vol. 1, 2nd ed., Exercise 3.102. Namely, let $L$ be a finite $n$-element lattice. Does there exist a join-irreducible $t$ of $L$ such that the principal dual order ideal $V_t:=\{ s\in L\colon s\geq t\}$ has at most $n/2$ elements? $\endgroup$ – Richard Stanley Feb 7 at 14:28

10 Answers 10

21
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ I don't think that the definition of a Gaussian poset is due to Proctor. $\endgroup$ – Richard Stanley Feb 6 at 18:59
  • 3
    $\begingroup$ @RichardStanley: apologies, Richard! $\endgroup$ – Sam Hopkins Feb 6 at 19:00
  • $\begingroup$ @SamHopkins : Reading between the lines, I wonder if you suspect that the conjecture may be false but the only counterexamples are "sporadic"? $\endgroup$ – Timothy Chow Feb 7 at 21:12
  • $\begingroup$ @TimothyChow: I think it could be false and in that case perhaps a large computer search could turn up a counterexample. If it’s true, it might just be true “by accident,” which would make it very hard to prove. $\endgroup$ – Sam Hopkins Feb 7 at 21:16
11
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Small correction: $M(8)$ is known, see OEIS sequence A000372 and Wiedemann, D.: A computation of the eighth Dedekind number (Order, March 1991, Vol. 8, Issue 1, pp 5-6). $\endgroup$ – nomadictype Feb 8 at 3:37
  • $\begingroup$ I have an English translation of Dr. Korshunov's hundred-page paper. (Even he does not have an English translation.) $\endgroup$ – Tri Feb 8 at 20:49
  • $\begingroup$ I believe it was Yamamoto proved that if n is even, then M(n) is even. What can we say about n odd? Using an idea I have long forgotten, I think Ciucu and Stembridge got some data for n up to 19, with one exception (ether n=11 or n=13). $\endgroup$ – Tri Feb 9 at 23:59
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What does connected mean here? The topology induced by the order? $\endgroup$ – Joel Adler Feb 13 at 7:52
  • $\begingroup$ @JoelAdler: connected in poset theory usually means "connected Hasse diagram" $\endgroup$ – Sam Hopkins Feb 13 at 15:43
  • $\begingroup$ "Connected" means that for all x and y in the poset, there exists a natural number n and elements z_1,...,z_n such that x <= z_1 >= z_2 <= z_3 >= ... <= z_n >= y. $\endgroup$ – Tri Feb 14 at 8:09
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.