Jtdylktuy

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.

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 $mgeq 0$ we have
$$ sum_{I in J(Ptimes [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 $pin P$; maybe some more things too. But like I said I think the full conjecture is pretty hopeless.

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.

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:Vtomathbb{N}} x_{kappa(1)}x_{kappa(2)}cdots x_{kappa(n)}$$
where the sum is over all maps $kappa:V tomathbb{N}$ such that the pre-image $kappa^{-1}(i)$ of every $iinmathbb{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.

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,Dcolon mathbb{Q}Ptomathbb{Q}P$ on the vector space of formal linear combinations of elements of $P$ by $U(p) = sum_{plessdot q} q$ and $D(p) = sum_{qlessdot 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?

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.

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 $Ccap A_i neq emptyset$ for all $iin 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 $ein E$ is a member of $E$, and


3. whenever $Ssubseteq V$ and every $2$-element subset of $S$ belongs to $E$, then $Sin E$.

Then there is $Jsubseteq E$ such that whenever $Ksubseteq E$ has the property that $bigcup K = V$ then $|Jsetminus K| leq |Ksetminus 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.

Find a nice expression for the number of down-sets (order ideals) of a product of four finite chains (totally ordered sets), $|bf2^{(bf ktimes bf mtimes bf ntimes 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 ktimes bf mtimes 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

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

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

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

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

If $P,Q$ are finite and non-empty, does $P^Pcong Q^Q$ imply $Pcong 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.

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 $Ptimes 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):sin 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 $mtimes k$ box. Here, $n=mk$, and the subgroup is the wreath product $S_mwr S_k$.




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

Conjecture: For all $nge 0$ and all $Gle 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.