34
$\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$
12
  • 4
    $\begingroup$ Union closed sets conjecture of Frankl. Gerhard "Master Of The Obvious, Apparently" Paseman, 2019.02.06. $\endgroup$ Feb 6, 2019 at 17:56
  • 4
    $\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$ Feb 6, 2019 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, 2019 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$ Feb 6, 2019 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$ Feb 7, 2019 at 14:28

11 Answers 11

24
$\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$
18
$\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$
4
  • 11
    $\begingroup$ I don't think that the definition of a Gaussian poset is due to Proctor. $\endgroup$ Feb 6, 2019 at 18:59
  • 5
    $\begingroup$ @RichardStanley: apologies, Richard! $\endgroup$ Feb 6, 2019 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$ Feb 7, 2019 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$ Feb 7, 2019 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$
1
6
$\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$
3
  • 2
    $\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$ Feb 8, 2019 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, 2019 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, 2019 at 23:59
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$
0
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$
1
5
$\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$
0
4
$\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$
4
$\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$
4
  • 1
    $\begingroup$ What does connected mean here? The topology induced by the order? $\endgroup$
    – Joel Adler
    Feb 13, 2019 at 7:52
  • 1
    $\begingroup$ @JoelAdler: connected in poset theory usually means "connected Hasse diagram" $\endgroup$ Feb 13, 2019 at 15:43
  • 1
    $\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, 2019 at 8:09
  • $\begingroup$ The equivalence relation generated by the partial order relation has one equivalence class. $\endgroup$
    – Todd Trimble
    Mar 16, 2019 at 17:12
3
$\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$
3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Where was this problem stated in the literature? $\endgroup$
    – Tri
    Jan 9, 2020 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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