Skip to Main Content

Was Gelfand Right? The Many Loves of Lattice Theory

Jonathan David Farley

Communicated by Notices Associate Editor Emilie Purvine

Article cover

Gian-Carlo Rota wrote in the Notices, “Never in the history of mathematics has a mathematical theory been the object of such vociferous vituperation as lattice theory.” In this article, we outline some of the exciting open problems in lattice theory and the theory of ordered sets.

I was surprised when I walked into the office of the person I hoped would be my doctoral advisor. The year before, I had bought the book coauthored by that person, a light blue paperback I still have in my possession: Introduction to Lattices and Order, by B. A. Davey and H. A. Priestley. Earlier that summer, there had been a conference in honor of Professor Garrett Birkhoff, who had been my undergraduate thesis advisor. At the conference, Professor Birkhoff told Dr. Priestley to expect me in the fall at the University of Oxford, where Dr. Priestley taught.

Dr. Priestley had sent me a handwritten note telling me we should meet at a particular office at the Mathematical Institute. The door was open and I walked in and that was the first time I realized that no one had actually used the pronoun “he” or “him,” because sitting in a chair wearing a dress was the woman who would become my doctoral advisor, H. A. Priestley.

I had been confounded by the British practice of using initials, like J. R. R. Tolkien, C. S. Lewis, and H. R. Highness!

Like me, some mathematicians may have false preconceived notions, even prejudices, about lattice theorists, lattice theory, or the theory of ordered sets. I hope that what you find in these pages will instead surprise—and delight—and excite—you. Maybe you’ll even find something you’ll love.

1. The Fixed-Point Property

In the first conversation Dr. Priestley and I had, she described this problem:

Is the fixed-point property for posets preserved by products?

A partially ordered set—a.k.a. poset—is a pair , where is a set and is a relation that is reflexive ( for all ), transitive ( and imply for all ), and antisymmetric ( and imply ). “Let be a poset” means we are considering for some set and relation on with those three properties.

Let and be posets. A function is order-preserving if implies . It is an order-embedding if also the converse holds. We denote the set of order-preserving maps from to by . A poset has the fixed-point property if for every there is a such that .

We can define a partial ordering on the direct product of posets as follows: if and only if and . For example, if is the -element totally ordered set, then is order-isomorphic to the power set of a three-element set.

Question 1.

If and have the fixed-point property, does ?

This problem was in circulation before it appeared in the first volume of the journal Order in 1984.

Roddy came up with the spectacular answer “Yes!”—for finite posets—in 1994. Roddy sent me a letter saying that the key idea had been in Roddy’s mind for a year, but Roddy couldn’t figure out how to make it work until seeing an article of mine on “the uniqueness of the core.” (To this day, I don’t see the connection.) Roddy’s paper is one of the greatest in the theory of ordered sets 16.

Later, Roddy, Schröder, and Rutkowski proved that the answer is “Yes” even if just one of and is finite, a far-reaching extension, but the general problem is still open. Maybe you will solve it?

Duffus explored fixed points of automorphisms of direct products of posets when the posets were directly indecomposable. (An automorphism is an order-isomorphism from a poset to itself. A poset with is directly indecomposable if, whenever for posets and , then or .)

An interesting problem is to generalize Duffus’s results. In particular,

Question 2.

Let and be connected posets such that every automorphism of or has a fixed point. Does every automorphism of have a fixed point?

(See §2 for the definition of “connected.” We focus on connected posets because of a beautiful theorem that we will see in §2.)

Bonus question.

Does a truncated non-complemented lattice of finite height have the fixed-point property?

I have a dream…that one day I will be able to give a talk about lattices to a general audience without having to define “lattice.” A lattice is a non-empty poset such that every pair of elements has a least upper bound, denoted , and a greatest lower bound, . A poset with a least element and a greatest element is called bounded. A bounded lattice is complemented if for every element , there is an element such that and . (These lattices have high self-esteem.) Examples include the power set of a set ordered by inclusion and the lattice of subspaces of a finite-dimensional vector space.

The complemented lattice has the fixed-point property. If is order-preserving, either or or equals (say) and hence . But if you remove the least and greatest elements, you get a poset without the fixed-point property, because the function switching and is order-preserving.

This doesn’t happen with finite non-complemented lattices. Baclawski and Björner proved the following theorem.

Theorem 3.

Let be a finite, non-complemented lattice. Then the truncated lattice has the fixed-point property.

Björner, a Pólya Prize winner, conjectured in 1981 that the theorem remains true even if is infinite, as long as there is a finite bound on the size of ’s totally ordered subsets, called chains. (This is what it means for to have finite height.) This conjecture has been open since 1981. See 10.

2. The Arithmetic of Ordered Sets

Let and be posets. The set can be partially ordered, where, for , if for all .

Figure 1.

, where is the 4-element cycle with and is the 2-element chain ; denotes the function such that and .

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.85]

\draw(-5,-0.25) node {$a$};
\draw(-4,-0.25) node {$b$};
\draw(-5,1.25) node {$c$};
\draw(-4,1.25) node {$d$};
\draw(-3.25,1) node {$0$};
\draw(-3.25,2) node {$1$};

\draw(-1,-0.25) node {$aa$};
\draw(-1.3,1) node {$ac$};
\draw(-1,2.25) node {$cc$};
\draw(0,0.75) node {$ad$};

\draw(1,0.75) node {$bc$};

\draw(2,-0.25) node {$bb$};
\draw(2.3,1) node {$bd$};
\draw(2,2.25) node {$dd$};

\draw[fill] (-5,0) circle (.05cm);
\draw(-5,0) -- (-5,1);
\draw[fill] (-5,1) circle (.05cm);
\draw(-5,0) -- (-4,1);
\draw[fill] (-4,1) circle (.05cm);

\draw[fill] (-4,0) circle (.05cm);
\draw(-4,0) -- (-4,1);
\draw[fill] (-4,1) circle (.05cm);
\draw(-4,0) -- (-5,1);

\draw[fill] (-3.5,1) circle (.05cm);
\draw(-3.5,1) -- (-3.5,2);
\draw[fill] (-3.5,2) circle (.05cm);

\draw(-2,1) node {\large$\cong$};

\draw[fill] (-1,0) circle (.05cm);
\draw(-1,0) -- (-1,1);
\draw[fill] (-1,1) circle (.05cm);
\draw(-1,1) -- (-1,2);
\draw[fill] (-1,2) circle (.05cm);
\draw(-1,0) -- (0,1);
\draw[fill] (0,1) circle (.05cm);

\draw[fill] (2,0) circle (.05cm);
\draw(2,0) -- (2,1);
\draw[fill] (2,1) circle (.05cm);
\draw(2,1) -- (2,2);
\draw[fill] (2,2) circle (.05cm);
\draw(2,0) -- (1,1);
\draw[fill] (1,1) circle (.05cm);

\draw(0,1) -- (2,2);
\draw(1,1) -- (-1,2);
\end{tikzpicture}

If and are disjoint, define the disjoint sum of and to be the poset defined on such that in if and only if and or and . A non-empty poset that is not the disjoint sum of non-empty posets is connected.

In the 1979 Proceedings of the American Mathematical Society, Duffus and Wille proved that implies if and are both finite, non-empty, and connected 5, Theorem, p. 14.

Duffus—editor-in-chief of the journal Order from 2007 to 2015 and chair of the Mathematics Department at Emory University from 1991 to 2005—said in 1984, “It is still an open problem to show connectedness can be dropped.” He notes in his 1978 thesis, “It is not obvious that is connected and imply that is connected.”

I proved that, indeed, if and are finite, non-empty posets such that and is connected, then is connected 8.

In other words, I resolved the issue from Duffus’s 1978 thesis in that I have “half-dropped” the connectedness hypothesis used in the 1979 Proceedings of the American Mathematical Society paper, whereas the 1984 problem asked if it could be dropped entirely. That problem is still open for you to solve.

One of the most beautiful results in the theory of ordered sets is Hashimoto’s Refinement Theorem: if is a connected, non-empty poset (finite or infinite!), any two ways of writing as a direct product (of a finite or infinite family of posets) have a common refinement. For example, if , then there exist posets such that , , , and .

We can consider similar issues with respect to the exponentiation operator. If , , , and are posets, then

What if we have posets , , , and such that ? Can we find “refining” posets , , , and such that the isomorphism is naturally explained (by , where

In 1982, Jónsson (an invited speaker at the 1974 International Congress of Mathematicians) and McKenzie, a professor at the University of California at Berkeley, posed the following problem. We only quote part of it 12.

“PROBLEM 12.1. Find counter examples (or prove that none exist) to the refinement of under any of the following conditions:…

(ii) , , and are finite and connected.

(iii) is a directly indecomposable lattice.”

I solved Problem 12.1(ii) 9, but (iii) is still open. (I solved a problem of Jónsson and McKenzie related to (iii) in 6; in that problem, Jónsson and McKenzie allowed one to assume the exponent was finite.)

Hashimoto’s Refinement Theorem enables you to prove results like: if , , and are finite, non-empty posets and , then . What if we merely have an order-embedding? This is a conjecture Birkhoff lists as a suggestion in a 1942 article.

Question 4.

If , , and are finite, non-empty posets and is isomorphic to a subposet of , is isomorphic to a subposet of ?

It is unclear if Lovász’s clever ideas in 13 would be applicable here.

3. Free Distributive Lattices

A lattice is distributive if for all , , , . Distributive lattices are beautiful and wonderful. We will say that is a free bounded distributive lattice generated by the finite poset —we will denote the bounded distributive lattice by —if is order-preserving and, for any order-preserving map from to a bounded distributive lattice , there is a unique lattice-homomorphism preserving and such that . It turns out that is order-isomorphic to 19, p. 369.

Several famous problems in combinatorics can be rephrased in terms of free distributive lattices. For instance, the lattice appears a lot in combinatorics: it is the poset and it is order-isomorphic to . A still-open problem is to find a combinatorial proof that the polynomial is unimodal (this means that the coefficients form a unimodal sequence: they weakly increase, then weakly decrease); Stanley explained to me that this is tantamount to showing that a certain distributive lattice is unimodal (where the lattice is unimodal if the number of elements of each “height” yields a unimodal sequence of numbers). If one can prove combinatorially that is unimodal, one will have solved this open problem.

If you look at a paper on “lozenge tilings of hexagons,” you may see MacMahon’s famous formula for counting “plane partitions in a box.” This is the cardinality of :

I recall emailing Stanley circa 1992 to ask if there was a formula for the cardinality of (), and my memory is that he replied that it was a well-known open problem. It is still open 19, Chapter 3, Exercise 170(h). Stanley wrote in 1972, “Nothing significant seems to be known in general about” .

Dedekind himself found that has 168 elements, and the oldest problem in lattice theory is Dedekind’s: find the cardinality of where there are ’s,” also known as the free distributive lattice with generators. This cardinality is known only for . Yamamoto proved that this cardinality is even if is even. What if is odd?

4. Inequalities for -vectors

Let belong to the symmetric group . A descent (an ascent) is an index such that (resp., ). A natural labeling of an -element poset (also known as a natural labelling 7) is an order-preserving bijection from to the chain . Figure 2(a) shows a natural labeling of the fence is the -element poset in which —but Figure 2(b) does not.

Figure 2. (a) A natural labeling. (b) An unnatural labeling.

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.85]
\draw[fill] (-5,0) circle (.05cm);
\draw[fill] (-5,1) circle (.05cm);
\draw[fill] (-4,0) circle (.05cm);
\draw[fill] (-4,1) circle (.05cm);

\draw(-5.25,-0.25) node {$1$};
\draw(-5.25,1) node {$3$};
\draw(-3.75,-0.25) node {$2$};
\draw(-3.75,1) node {$4$};

\draw(-5,0) -- (-5,1);
\draw(-4,0) -- (-5,1);
\draw(-4,0) -- (-4,1);

\draw[fill] (0,0) circle (.05cm);
\draw[fill] (0,1) circle (.05cm);
\draw[fill] (1,0) circle (.05cm);
\draw[fill] (1,1) circle (.05cm);

\draw(-0.25,-0.25) node {$1$};
\draw(-0.25,1) node {$2$};
\draw(1.25,-0.25) node {$3$};
\draw(1.25,1) node {$4$};

\draw(0,0) -- (0,1);
\draw(1,0) -- (1,1);
\draw(1,0) -- (0,1);
\end{tikzpicture}

If we fix a natural labeling, the linear extensions of —listings of the elements of where appears to the left of if in —are permutations. Every listing of the members of an -element set is a permutation if one lists all the elements without repetition. Let be the set of linear extensions of with exactly descents, and let (). When the poset is understood, we will simply write and .” One can have tremendous fun calculating . See Figure 3, where we partially order the linear extensions by saying that for an ascent and using transitivity. Note that .

Figure 3(a).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.8]

\draw[fill] (-5,0) circle (.05cm);
\draw[fill] (-4,0) circle (.05cm);
\draw[fill] (-3,0) circle (.05cm);

\draw(-5,0.5) node {$1$};
\draw(-4,0.5) node {$2$};
\draw(-3,0.5) node {$3$};
\draw(-4,-0.5) node {$P$};

\draw[fill] (0,0) circle (.05cm);
\draw[fill] (-1,1) circle (.05cm);
\draw[fill] (1,1) circle (.05cm);
\draw[fill] (-1,2) circle (.05cm);
\draw[fill] (1,2) circle (.05cm);
\draw[fill] (0,3) circle (.05cm);

\draw(0,-0.25) node {$123$};
\draw(-1.5,1) node {$213$};
\draw(1.5,1) node {$132$};
\draw(-1.5,2) node {$231$};
\draw(1.5,2) node {$312$};
\draw(0,3.25) node {$321$};

\draw(0,0) -- (-1,1);
\draw(0,0) -- (1,1);
\draw(-1,1) -- (-1,2);
\draw(1,1) -- (1,2);
\draw(-1,2) -- (0,3);
\draw(1,2) -- (0,3);

\draw(-2,-2) node {$\h_0=1\quad\h_1=4\quad\h_2=1\quad\h_3=0$};

\end{tikzpicture}

Figure 3(b).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.8]

\draw(-5.5,0) node {$1$};
\draw(-5.5,1) node {$2$};
\draw(-5.5,2) node {$3$};
\draw(-5,-0.5) node {$P$};

\draw[fill] (0,0) circle (.05cm);
\draw[fill] (-5,0) circle (.05cm);
\draw[fill] (-5,1) circle (.05cm);
\draw[fill] (-5,2) circle (.05cm);

\draw(0,-0.5) node {$123$};

\draw(-5,0) -- (-5,1);
\draw(-5,1) -- (-5,2);

\draw(-2,-2) node {$\h_0=1\quad\h_1=0\quad\h_2=0\quad\h_3=0$};

\end{tikzpicture}

Figure 3(c).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.8]

\draw(-5,-0.3) node {$1$};
\draw(-4,1.3) node {$3$};
\draw(-3,-0.3) node {$2$};
\draw(-4,-0.8) node {$P$};

\draw[fill] (0,0) circle (.05cm);
\draw[fill] (0,1) circle (.05cm);

\draw[fill] (-5,0) circle (.05cm);
\draw[fill] (-4,1) circle (.05cm);
\draw[fill] (-3,0) circle (.05cm);

\draw(0,-0.5) node {$123$};
\draw(0,1.5) node {$213$};

\draw(0,0) -- (0,1);

\draw(-5,0) -- (-4,1);
\draw(-3,0) -- (-4,1);

\draw(-2,-2) node {$\h_0=1\quad\h_1=1\quad\h_2=0\quad\h_3=0$};
\end{tikzpicture}

Figure 3(d).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.8]

\draw[fill] (0,0) circle (.05cm);
\draw[fill] (0,1) circle (.05cm);
\draw[fill] (0,2) circle (.05cm);
\draw(0,0) -- (0,1);
\draw(0,1) -- (0,2);

\draw(0,-0.5) node {$123$};
\draw(0.8,1) node {$132$};
\draw(0,2.5) node {$312$};

\draw[fill] (-5,0) circle (.05cm);
\draw[fill] (-5,1) circle (.05cm);
\draw[fill] (-4,0.5) circle (.05cm);
\draw(-5,0) -- (-5,1);

\draw(-5,-0.5) node {$1$};
\draw(-4,1.3) node {$3$};
\draw(-5,1.5) node {$2$};
\draw(-4.5,-1.5) node {$P$};

\draw(-2,-2) node {$\h_0=1\quad\h_1=2\quad\h_2=0\quad\h_3=0$};
\end{tikzpicture}
Table 1.

What makes working with -vectors—the -tuples —so delightful is when there are two families of posets differing in structure that mysteriously have the same -vectors. See Figures 4, 5, and 6.

It is known that the -vector of is the sequence of Narayana numbers (see 19, Example 3.5.5). In Table 1, we show the -vectors for the smallest posets of the form and . What properties do the “generalized Narayana” numbers have? (See the work of Robert Sulanke.)

Figure 4(a).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.75]
\draw[fill] (0,0) circle (.05cm);
\draw(0,-0.25) node {$1$};
\draw(0,0) -- (-1,1);
\draw(0,0) -- (1,1);

\draw[fill] (-1,1) circle (.05cm);
\draw(-1.25,1) node {$2$};
\draw[fill] (1,1) circle (.05cm);
\draw(1.25,1) node {$3$};
\draw(-1,1) -- (-2,2);
\draw(-1,1) -- (0,2);
\draw(1,1) -- (2,2);
\draw(1,1) -- (0,2);

\draw[fill] (-2,2) circle (.05cm);
\draw(-2.25,2) node {$5$};
\draw[fill] (0,2) circle (.05cm);
\draw(0.25,2) node {$4$};
\draw[fill] (2,2) circle (.05cm);
\draw(2.25,2) node {$6$};
\draw(-2,2) -- (-1,3);
\draw(0,2) -- (-1,3);
\draw(0,2) -- (1,3);
\draw(2,2) -- (1,3);

\draw[fill] (-1,3) circle (.05cm);
\draw(-1.25,3) node {$7$};
\draw[fill] (1,3) circle (.05cm);
\draw(1.25,3) node {$8$};
\draw(-1,3) -- (0,4);
\draw(1,3) -- (0,4);

\draw[fill] (0,4) circle (.05cm);
\draw(0,4.25) node {$9$};

\draw(-4,-2) node {$\h_0=1\quad\h_1=10\quad\h_2=20\quad\h_3=10\quad\h_4=1$};

\end{tikzpicture}

Figure 4(b).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.75]

\draw[fill] (0,0) circle (.05cm);
\draw(0,-0.25) node {$1$};
\draw(0,0) -- (1,1);
\draw[fill] (2,0) circle (.05cm);
\draw(2,-0.25) node {$2$};
\draw(2,0) -- (1,1);
\draw(2,0) -- (3,1);
\draw[fill] (4,0) circle (.05cm);
\draw(4,-0.25) node {$5$};
\draw(4,0) -- (3,1);

\draw[fill] (1,1) circle (.05cm);
\draw(0.75,1) node {$3$};
\draw(1,1) -- (0,2);
\draw(1,1) -- (2,2);
\draw[fill] (3,1) circle (.05cm);
\draw(3.25,1) node {$6$};
\draw(3,1) -- (2,2);

\draw[fill] (0,2) circle (.05cm);
\draw(-0.25,2) node {$4$};
\draw(0,2) -- (1,3);
\draw[fill] (2,2) circle (.05cm);
\draw(2.25,2) node {$7$};
\draw(2,2) -- (1,3);

\draw[fill] (1,3) circle (.05cm);
\draw(1.25,3) node {$8$};
\draw(1,3) -- (0,4);

\draw[fill] (0,4) circle (.05cm);
\draw(0,4.25) node {$9$};

\draw(-2,-2) node {$\h_0=1\quad\h_1=10\quad\h_2=20\quad\h_3=10\quad\h_4=1$};


\end{tikzpicture}

An answer should help resolve what Proctor calls “a complete mystery” 15, p. 555.

Readers will immediately formulate their own conjecture about -vectors of two families of posets from Figures 5 and 6; MacMahon’s formula, shown earlier, would yield it, but a bijective proof is lacking.

Figure 5(a).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.85]

\draw[fill] (0,0) circle (.05cm);
\draw(0,-0.25) node {$1$};
\draw(0,0) -- (-1,1);
\draw(0,0) -- (1,1);

\draw[fill] (-1,1) circle (.05cm);
\draw(-1.25,1) node {$2$};
\draw[fill] (1,1) circle (.05cm);
\draw(1.25,1) node {$4$};
\draw(-1,1) -- (-2,2);
\draw(-1,1) -- (0,2);
\draw(1,1) -- (0,2);

\draw[fill] (-2,2) circle (.05cm);
\draw(-2.25,2) node {$3$};
\draw[fill] (0,2) circle (.05cm);
\draw(0.25,2) node {$5$};
\draw(-2,2) -- (-1,3);
\draw(0,2) -- (-1,3);

\draw[fill] (-1,3) circle (.05cm);
\draw(-1,3.25) node {$6$};

\draw[fill] (2,1.5) circle (.05cm);
\draw(2.25,1.5) node {$7$};

\draw(-2,-2) node {$\h_0=1\quad\h_1=12\quad\h_2=18\quad\h_3=4$};


\end{tikzpicture}

Figure 5(b).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.85]

\draw[fill] (0,0) circle (.05cm);
\draw(0,-0.25) node {$1$};
\draw(0,0) -- (0,1);
\draw[fill] (1,0) circle (.05cm);
\draw(1,-0.25) node {$4$};
\draw(1,0) -- (1,1);

\draw[fill] (0,1) circle (.05cm);
\draw(-0.25,1) node {$2$};
\draw(0,1) -- (0,2);
\draw[fill] (1,1) circle (.05cm);
\draw(1.25,1) node {$5$};
\draw(1,1) -- (1,2);

\draw[fill] (0,2) circle (.05cm);
\draw(-0.25,2) node {$3$};
\draw[fill] (1,2) circle (.05cm);
\draw(1.25,2) node {$6$};
\draw(1,2) -- (1,3);

\draw[fill] (1,3) circle (.05cm);
\draw(1.25,3) node {$7$};

\draw(1,-2) node {$\h_0=1\quad\h_1=12\quad\h_2=18\quad\h_3=4$};

\end{tikzpicture}

Figure 6(a).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.85]

\draw[fill] (0,0) circle (.05cm);
\draw(0,-0.25) node {$1$};
\draw(0,0) -- (-1,1);
\draw(0,0) -- (1,1);

\draw[fill] (-1,1) circle (.05cm);
\draw(-1.25,1) node {$2$};
\draw[fill] (1,1) circle (.05cm);
\draw(1.25,1) node {$4$};
\draw(-1,1) -- (-2,2);
\draw(-1,1) -- (0,2);
\draw(1,1) -- (0,2);

\draw[fill] (-2,2) circle (.05cm);
\draw(-2.25,2) node {$3$};
\draw[fill] (0,2) circle (.05cm);
\draw(0.25,2) node {$5$};
\draw(-2,2) -- (-1,3);
\draw(0,2) -- (-1,3);

\draw[fill] (-1,3) circle (.05cm);
\draw(-1,3.25) node {$6$};

\draw[fill] (2,1.5) circle (.05cm);
\draw(2.25,1.5) node {$7$};
\draw(2,1.5) -- (2,2.5);
\draw[fill] (2,2.5) circle (.05cm);
\draw(2.25,2.5) node {$8$};

\draw(-2,-2) node {$\h_0=1\quad\h_1=21\quad\h_2=66\quad\h_3=46\quad\h_4=6$};

\end{tikzpicture}

Figure 6(b).

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.85]

\draw[fill] (0,0) circle (.05cm);
\draw(0,-0.25) node {$1$};
\draw(0,0) -- (-1,1);
\draw(0,0) -- (1,1);

\draw[fill] (-1,1) circle (.05cm);
\draw(-1.25,1) node {$2$};
\draw[fill] (1,1) circle (.05cm);
\draw(1.25,1) node {$3$};
\draw(-1,1) -- (0,2);
\draw(1,1) -- (0,2);
\draw(0,2.25) node {$4$};
\draw[fill] (0,2) circle (.05cm);

\draw[fill] (2,-0.5) circle (.05cm);
\draw(2.25,-0.5) node {$5$};
\draw(2,-0.5) -- (2,0.5);
\draw[fill] (2,0.5) circle (.05cm);
\draw(2.25,0.5) node {$6$};
\draw(2,0.5) -- (2,1.5);
\draw[fill] (2,1.5) circle (.05cm);
\draw(2.25,1.5) node {$7$};
\draw(2,1.5) -- (2,2.5);
\draw[fill] (2,2.5) circle (.05cm);
\draw(2.25,2.5) node {$8$};

\draw(-2,-2) node {$\h_0=1\quad\h_1=21\quad\h_2=66\quad\h_3=46\quad\h_4=6$};

\end{tikzpicture}

Can we combinatorially (i.e., with an explicit bijection or algorithm—in particular, without using the MacMahon formula) prove, for , , …, , that

1

The reader should be wondering if this is a typo or if the author is offering a cash prize for a solution to this problem.

(Professor Vaughan Pratt suggested this symmetric formulation in a discussion that started on the Universal Algebra Listserv.)

For and , we are comparing

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.85]

\draw[fill] (0,0) circle (.05cm);
\draw(0,0) -- (-1,1);
\draw(0,0) -- (1,1);

\draw[fill] (-1,1) circle (.05cm);
\draw[fill] (1,1) circle (.05cm);
\draw(-1,1) -- (-2,2);
\draw(-1,1) -- (0,2);
\draw(1,1) -- (2,2);
\draw(1,1) -- (0,2);

\draw[fill] (-2,2) circle (.05cm);
\draw[fill] (0,2) circle (.05cm);
\draw[fill] (2,2) circle (.05cm);
\draw(-2,2) -- (-1,3);
\draw(0,2) -- (-1,3);
\draw(0,2) -- (1,3);
\draw(2,2) -- (1,3);

\draw[fill] (-1,3) circle (.05cm);
\draw[fill] (1,3) circle (.05cm);
\draw(-1,3) -- (0,4);
\draw(1,3) -- (0,4);

\draw[fill] (0,4) circle (.05cm);

\draw[fill] (3,1.5) circle (.05cm);
\draw[fill] (3,2.5) circle (.05cm);
\draw(3,1.5) -- (3,2.5);

\end{tikzpicture}

and

\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=.85]

\draw[fill] (0,0) circle (.05cm);
\draw(0,0) -- (-1,1);
\draw(0,0) -- (1,1);

\draw[fill] (-1,1) circle (.05cm);
\draw[fill] (1,1) circle (.05cm);
\draw(-1,1) -- (-2,2);
\draw(-1,1) -- (0,2);
\draw(-2,2) -- (-3,3);
\draw(1,1) -- (0,2);

\draw[fill] (-2,2) circle (.05cm);
\draw[fill] (0,2) circle (.05cm);
\draw(-2,2) -- (-1,3);
\draw(0,2) -- (-1,3);

\draw[fill] (-1,3) circle (.05cm);
\draw(-1,3) -- (-2,4);

\draw[fill] (-3,3) circle (.05cm);
\draw(-3,3) -- (-2,4);

\draw[fill] (-2,4) circle (.05cm);

\draw[fill] (3,1.5) circle (.05cm);
\draw[fill] (3,2.5) circle (.05cm);
\draw(3,1.5) -- (3,2.5);
\draw[fill] (3,3.5) circle (.05cm);
\draw(3,2.5) -- (3,3.5);

\end{tikzpicture}

Going back to arbitrary -element posets, I conjectured that, for , . In 1997, Björner was able to prove the inequality using the -Theorem on polytopes, but, he wrote in a letter to me dated March 2, 1997, “This seems unnecessarily complicated. There should be a combinatorial proof! Namely, an injection from the set of linear extensions of with [] descents to [the set of linear extensions of with] descents. It seems nontrivial however. Can you do it?”

I did it (unpublished), but there are other interesting inequalities between the entries of the -vector that remain to be proved.

At the 1981 Banff Conference on Ordered Sets, Stanley said, “About ten years ago I proved” the following result.

Theorem 5 (Stanley).

Let be a finite naturally labeled poset. Let be the set of linear extensions of , and, for every , let be the number of descents of . Let be . Then the following are equivalent:

(i)

for .

(ii)

Every maximal chain of has the same length.

He went on to pose the following problem:

“Find a combinatorial proof of this theorem. More precisely, when (ii) holds describe explicitly a bijection such that for all .”

Stanley added, “It would even be interesting to do this for the case .

Stanley reported in his 2012 book 19, p. 454, “A combinatorial proof using a complicated recursion argument was given by J. D. Farley” 7. A more direct proof might help us prove that for , part of a conjecture of Hibi, a winner of the Algebra Prize of the Mathematical Society of Japan.

5. The Structure of the Perfect Terrorist Cell

In 2008, policeman Kevin Blake, the former director of Jamaica’s National Intelligence Bureau, part of Jamaica’s Ministry of National Security, told the Jamaica Observer newspaper, “Ordered sets theory allows you to organise networks, a criminal network or a terrorist cell, and mathematically calculate the chances of successfully disrupting the cell upon capturing a number of those individuals.” The newspaper went on to say, “Blake’s work has already contributed to the disruption of one criminal gang.”

Whatever you might think of this work, maybe it played a role in a former deputy director of the CIA’s calling me up and having coffee with me. It’s easy to get a big head when a US Air Force officer (now a colonel) says that your “thinking has influenced real world decisions of highest operational importance to the Department of Defense” or when the Wiener Zeitung does a two-page profile of you or when Seed Magazine names you one of “15 people who have shaped the global conversation about science in 2005” (alongside people like Harvard University physics professor Lisa Randall). Fortunately, I have remained modest.

Figure 7.

Zeinab Bandpey.

Graphic for Figure 7.  without alt text

Zeinab Bandpey (shown in Figure 7) found the structure of the “perfect” terrorist cell with a single leader, according to certain specific criteria. Mathematically, she proved a conjecture about minimizing the number of cutsets—subsets that intersect all maximal chains—in a finite poset with a top element such that no element has more than lower covers 1.

Before Bandpey’s breakthrough, Chvátal and three colleagues at McGill University had previously proven a special case of the conjecture for trees (the chairman of Stanford University’s Computer Science Department at one time called Chvátal “one of the two best young combinatorialists in the world”) and I had proven the case.

What if has two maximal elements (or more)?

6. “Trying to Reestablish the Cosmic Order by Riding on a Buffalo”

While I don’t necessarily agree with “Professor Gelfand’s oft-repeated prediction that lattice theory will play a leading role in the mathematics of the twenty-first century” (as Rota said in the Notices 17, p. 1445), lattice theory and the theory of ordered sets arise in a variety of applications, from robotics 4 to imaging to chemistry to linguistics to economics 20 (see Roth’s Nobel Prize acceptance speech) to sociology to epidemiology 2 to physics 3 to national security (the work of Cliff Joslyn at Los Alamos National Laboratory predates mine) to computer science 14.⁠Footnote2 But I will leave you with a list of 12 problems in pure mathematics:

2

See the list of talks in the AMS Special Sessions on The Many Lives of Lattice Theory and the Theory of Ordered Sets for 2002, 2003, and 2004, as well as the DIMACS Workshop on Applications of Lattices and Ordered Sets to Computer Science and the DIMACS Workshop on Applications of Order Theory to Homeland Defense and Computer Security.

(0)

If and are posets with the fixed-point property, does have the fixed-point property? If every automorphism of the connected poset (resp., ) has a fixed point, does every automorphism of have a fixed point?

(1)

Let and be finite, non-empty posets. If , is ?

(2)

Let , , and be finite, non-empty posets. If embeds in , does embed in ?

(3)

Let be an exponentially and directly indecomposable lattice, and let be a connected, non-empty poset. Is the automorphism group of isomorphic to the product of the automorphism group of and the automorphism group of ? (A poset is exponentially indecomposable if, whenever for posets and , then .)

(4)

Find a formula for the cardinality of the free distributive lattice generated by a disjoint sum of four finite chains.

(5)

If is odd, when is the cardinality of the free distributive lattice with generators odd?

(6)

Without using the MacMahon formula (and preferably with a bijection), prove that, for , ($137). (Remember, this is a prelude to explaining combinatorially why the -vectors of posets in the classes containing the posets of Figures 4(a) and (b) are the same.)

(7)

Generalize all the results we know about Narayana numbers to .

(8)

Let be a finite poset and let be the largest integer such that . Is if ?

(9)

In the class of finite posets with maximal elements such that no element has more than lower covers, find the poset or posets with the fewest cutsets.

And to show that there is more than we could discuss in this article:

(10)

Are and the only directly indecomposable differential lattices? 18, Problem 2

(11)

Is every finite lattice the lattice of congruences of a finite algebra? 11

I hope you solve them.

Fin

Acknowledgments

The author thanks Professor Asamoah Nkwanta, Professor Bernd Schröder, the referees, and the editor for critiquing a draft of this article. Notices policy forced me to restrict the number of references to 20. The author is thankful for the opportunity to contribute to the Notices but objects to one editorial decision.

References

[1]
Zeinab Bandpey, Jonathan Farley’s mathematical terror theory: the structure of perfect terrorist cells with a single leader, Congr. Numer. 228 (2017), 345–352. MR3751850Show rawAMSref\bib{BanAG}{article}{ author={Bandpey, Zeinab}, title={Jonathan Farley's mathematical terror theory: the structure of perfect terrorist cells with a single leader}, journal={Congr. Numer.}, volume={228}, date={2017}, pages={345--352}, issn={0384-9864}, review={\MR {3751850}}, } Close amsref.
[2]
Niko Beerenwinkel, Nicholas Eriksson, and Bernd Sturmfels, Evolution on distributive lattices, J. Theoret. Biol. 242 (2006), no. 2, 409–420, DOI 10.1016/j.jtbi.2006.03.013. MR2272562Show rawAMSref\bib{BeeEriStuJF}{article}{ author={Beerenwinkel, Niko}, author={Eriksson, Nicholas}, author={Sturmfels, Bernd}, title={Evolution on distributive lattices}, journal={J. Theoret. Biol.}, volume={242}, date={2006}, number={2}, pages={409--420}, issn={0022-5193}, review={\MR {2272562}}, doi={10.1016/j.jtbi.2006.03.013}, } Close amsref.
[3]
Garrett Birkhoff and John von Neumann, The logic of quantum mechanics, Ann. of Math. (2) 37 (1936), no. 4, 823–843, DOI 10.2307/1968621. MR1503312Show rawAMSref\bib{BirvonCF}{article}{ author={Birkhoff, Garrett}, author={von Neumann, John}, title={The logic of quantum mechanics}, journal={Ann. of Math. (2)}, volume={37}, date={1936}, number={4}, pages={823--843}, issn={0003-486X}, review={\MR {1503312}}, doi={10.2307/1968621}, } Close amsref.
[4]
Domitilla Del Vecchio and Richard M. Murray, Existence of cascade discrete-continuous state estimators for systems on a partial order, Hybrid Systems: Computation and Control, Lecture Notes in Computer Science, vol. 3414, Springer, Berlin, 2005, pp. 226–241.
[5]
Dwight Duffus and Rudolf Wille, A theorem on partially ordered sets of order-preserving mappings, Proc. Amer. Math. Soc. 76 (1979), no. 1, 14–16, DOI 10.2307/2042907. MR534380Show rawAMSref\bib{DufWilGI}{article}{ author={Duffus, Dwight}, author={Wille, Rudolf}, title={A theorem on partially ordered sets of order-preserving mappings}, journal={Proc. Amer. Math. Soc.}, volume={76}, date={1979}, number={1}, pages={14--16}, issn={0002-9939}, review={\MR {534380}}, doi={10.2307/2042907}, } Close amsref.
[6]
J. D. Farley, The automorphism group of a function lattice: a problem of Jónsson and McKenzie, Algebra Universalis 36 (1996), no. 1, 8–45, DOI 10.1007/BF01192707. MR1397566Show rawAMSref\bib{FarIF}{article}{ author={Farley, J. D.}, title={The automorphism group of a function lattice: a problem of J\'{o}nsson and McKenzie}, journal={Algebra Universalis}, volume={36}, date={1996}, number={1}, pages={8--45}, issn={0002-5240}, review={\MR {1397566}}, doi={10.1007/BF01192707}, } Close amsref.
[7]
Jonathan David Farley, Linear extensions of ranked posets, enumerated by descents. A problem of Stanley from the 1981 Banff conference on ordered sets, Adv. in Appl. Math. 34 (2005), no. 2, 295–312, DOI 10.1016/j.aam.2004.05.007. MR2110553Show rawAMSref\bib{FarJE}{article}{ author={Farley, Jonathan David}, title={Linear extensions of ranked posets, enumerated by descents. A problem of Stanley from the 1981 Banff conference on ordered sets}, journal={Adv. in Appl. Math.}, volume={34}, date={2005}, number={2}, pages={295--312}, issn={0196-8858}, review={\MR {2110553}}, doi={10.1016/j.aam.2004.05.007}, } Close amsref.
[8]
Jonathan David Farley, An issue raised in 1978 by a then-future editor-in-chief of the journal Order: Does the endomorphism poset of a finite connected poset tell us that the poset is connected?, arXiv:2005.03255, 2020.
[9]
Jonathan David Farley, Another problem of Jónsson and McKenzie from 1982: refinement properties for connected powers of posets, Algebra Universalis 82 (2021), no. 3, Paper No. 48, 6, DOI 10.1007/s00012-020-00698-y. MR4289456Show rawAMSref\bib{FarBJd}{article}{ author={Farley, Jonathan David}, title={Another problem of J\'{o}nsson and McKenzie from 1982: refinement properties for connected powers of posets}, journal={Algebra Universalis}, volume={82}, date={2021}, number={3}, pages={Paper No. 48, 6}, issn={0002-5240}, review={\MR {4289456}}, doi={10.1007/s00012-020-00698-y}, } Close amsref.
[10]
Jonathan David Farley, A conjecture of Kozlov from the 1998 Proceedings of the American Mathematical Society: Non-evasive order complexes and generalizations of non-complemented lattices, manuscript, 2020.
[11]
Walter Feit, An interval in the subgroup lattice of a finite group which is isomorphic to , Algebra Universalis 17 (1983), no. 2, 220–221, DOI 10.1007/BF01194532. MR726276Show rawAMSref\bib{FeiHC}{article}{ author={Feit, Walter}, title={An interval in the subgroup lattice of a finite group which is isomorphic to $M_{7}$}, journal={Algebra Universalis}, volume={17}, date={1983}, number={2}, pages={220--221}, issn={0002-5240}, review={\MR {726276}}, doi={10.1007/BF01194532}, } Close amsref.
[12]
Bjarni Jónsson and Ralph McKenzie, Powers of partially ordered sets: cancellation and refinement properties, Math. Scand. 51 (1982), no. 1, 87–120, DOI 10.7146/math.scand.a-11966. MR681261Show rawAMSref\bib{JonMcKHB}{article}{ author={J\'{o}nsson, Bjarni}, author={McKenzie, Ralph}, title={Powers of partially ordered sets: cancellation and refinement properties}, journal={Math. Scand.}, volume={51}, date={1982}, number={1}, pages={87--120}, issn={0025-5521}, review={\MR {681261}}, doi={10.7146/math.scand.a-11966}, } Close amsref.
[13]
L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967), 321–328, DOI 10.1007/BF02280291. MR214529Show rawAMSref\bib{LovFG}{article}{ author={Lov\'{a}sz, L.}, title={Operations with structures}, journal={Acta Math. Acad. Sci. Hungar.}, volume={18}, date={1967}, pages={321--328}, issn={0001-5954}, review={\MR {214529}}, doi={10.1007/BF02280291}, } Close amsref.
[14]
G. Markowsky and B. K. Rosen, Bases for chain-complete posets, IBM J. Res. Develop. 20 (1976), no. 2, 138–147, DOI 10.1147/rd.202.0138. MR392706Show rawAMSref\bib{MarRosGF}{article}{ author={Markowsky, G.}, author={Rosen, B. K.}, title={Bases for chain-complete posets}, journal={IBM J. Res. Develop.}, volume={20}, date={1976}, number={2}, pages={138--147}, issn={0018-8646}, review={\MR {392706}}, doi={10.1147/rd.202.0138}, } Close amsref.
[15]
Robert A. Proctor, Shifted plane partitions of trapezoidal shape, Proc. Amer. Math. Soc. 89 (1983), no. 3, 553–559, DOI 10.2307/2045516. MR715886Show rawAMSref\bib{ProHC}{article}{ author={Proctor, Robert A.}, title={Shifted plane partitions of trapezoidal shape}, journal={Proc. Amer. Math. Soc.}, volume={89}, date={1983}, number={3}, pages={553--559}, issn={0002-9939}, review={\MR {715886}}, doi={10.2307/2045516}, } Close amsref.
[16]
Michael S. Roddy, Fixed points and products, Order 11 (1994), no. 1, 11–14, DOI 10.1007/BF01462225. MR1296230Show rawAMSref\bib{RodID}{article}{ author={Roddy, Michael S.}, title={Fixed points and products}, journal={Order}, volume={11}, date={1994}, number={1}, pages={11--14}, issn={0167-8094}, review={\MR {1296230}}, doi={10.1007/BF01462225}, } Close amsref.
[17]
Gian-Carlo Rota, The many lives of lattice theory, Notices Amer. Math. Soc. 44 (1997), no. 11, 1440–1445. MR1488572Show rawAMSref\bib{RotIG}{article}{ author={Rota, Gian-Carlo}, title={The many lives of lattice theory}, journal={Notices Amer. Math. Soc.}, volume={44}, date={1997}, number={11}, pages={1440--1445}, issn={0002-9920}, review={\MR {1488572}}, } Close amsref.
[18]
Richard P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), no. 4, 919–961, DOI 10.2307/1990995. MR941434Show rawAMSref\bib{StaHH}{article}{ author={Stanley, Richard P.}, title={Differential posets}, journal={J. Amer. Math. Soc.}, volume={1}, date={1988}, number={4}, pages={919--961}, issn={0894-0347}, review={\MR {941434}}, doi={10.2307/1990995}, } Close amsref.
[19]
Richard P. Stanley, Enumerative combinatorics. Volume 1, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR2868112Show rawAMSref\bib{StaAB}{book}{ author={Stanley, Richard P.}, title={Enumerative combinatorics. Volume 1}, series={Cambridge Studies in Advanced Mathematics}, volume={49}, edition={2}, publisher={Cambridge University Press, Cambridge}, date={2012}, pages={xiv+626}, isbn={978-1-107-60262-5}, review={\MR {2868112}}, } Close amsref.
[20]
Qingyun Wu and Alvin E. Roth, The lattice of envy-free matchings, Games Econom. Behav. 109 (2018), 201–211, DOI 10.1016/j.geb.2017.12.016. MR3802588Show rawAMSref\bib{WuRotAH}{article}{ author={Wu, Qingyun}, author={Roth, Alvin E.}, title={The lattice of envy-free matchings}, journal={Games Econom. Behav.}, volume={109}, date={2018}, pages={201--211}, issn={0899-8256}, review={\MR {3802588}}, doi={10.1016/j.geb.2017.12.016}, } Close amsref.

Credits

Opening image is courtesy of Marlena Hewitt.

Figures 1–6 and Table 1 are courtesy of Jonathan David Farley.

Figure 7 is courtesy of Elyad Farajnia.

Photo of Jonathan David Farley is courtesy of Peter Kiar.