algorithmAlgorithm M. R. Emamy-K., Gustavo A. Meléndez Ríos 11institutetext:
Universidad de Puerto Rico, Recinto de Río Piedras, San Juan PR, USA,
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>

#  $ST$-distributive and $ST$-modular Lattices

M. R. Emamy-K. [0000-0002-5407-0392]
Gustavo A. Meléndez Ríos ✉ [0000-0001-5980-3666]

###### Abstract

For two subsets $S$ and $T$ of a given lattice $L,$ we define a relative
distributive (modular) property over $L,$ that underlies a large family
including the usual class of distributive (modular) lattices. Our proposed
class will be called $ST$-distributive ($ST$-modular) lattices. In this paper,
we find examples of maximal $S$ and $T$ to form $ST$-distributive lattices for
several non-distributive finite lattices of small order. In particular, we
characterize the maximal pairs of subsets $(S,T)$, subject to certain
constraints, that induce $ST$-distributivity in the lattice family
$\mathbf{M}_{n,n}$. Afterwards, we present an application of $ST$-modular to
convex sets and polytopes. This application is the original motivation for our
new definitions. The aforementioned definitions are closely related to
distributive elements and Stanley’s SS-lattices.

###### keywords:

Distributive lattices, Modular lattices, Convex polytopes

_2020 Mathematics Subject Classification_. Primary: 06D75, Secondary: 06C99,
52A99, 52B99 .

##  1 Introduction

We propose two new classes of lattices: $ST$-distributive lattices and
$ST$-modular lattices. The idea behind them is to define relative distributive
and modular properties that are fulfilled by certain pairs of subsets of a
lattice that is not necessarily distributive nor modular. Naturally, we desire
that these new classes include distributive and modular lattices respectively
(i.e. are a generalization of them). In a sense, this is analogous to relative
topologies in topological spaces.

This paper introduces one of the most basic questions regarding these new
classes: Given a lattice, which pairs of subsets satisfy these relative
distributive/modular properties? Of course, this question is non-trivial only
if the given lattice is non-distributive/non-modular. The main goal coming out
of this question is to identify families of lattices with particular
characterizations of the subsets that induce these relative properties.

Here, we define these new classes precisely and present some initial results
on $ST$-distributivity for a family of lattices called $\mathbf{M}_{n,n}$. We
also show connections between $ST$-distributive lattices and two established
concepts in lattice theory: distributive elements [5] and Stanley’s SS-
lattices [7]. In addition, we present a potential applications of $ST$-modular
lattices to convex sets.

This paper is organized as follows: Section 2 discusses $ST$-distributive
lattices including our results on $\mathbf{M}_{n,n}$. Afterwards, Sect. 3
introduces $ST$-modular lattices and applies them to convex sets. Finally,
Sect. 4 concludes with a summary and ideas for continuing this work. For more
details on how Sects. 2 and 3 are organized internally, see their respective
introductory paragraphs.

##  2 $ST$-distributive Lattices

In this section, we discuss $ST$-distributive lattices. Subsection 2.1
establishes the basic definitions regarding this new concept and provides some
illustrative examples. This is developed further with some basic properties of
these lattices in Subsect. 2.2. Subsection 2.3 then specifies our search
problem and presents the methodology we use to tackle it. Afterwards, the
family of lattices to which we apply this methodology, $\mathbf{M}_{n,n}$, is
described in Subsect. 2.4. This is followed by the results of this application
in Subsect. 2.5. Finally, Subsections 2.6 and 2.7 conclude this discussion by
connecting our $ST$-distributive lattices to distributive elements and
Stanley’s SS-lattices respectively.

###  2.1 Basic Definitions

We introduce $ST$-distributive lattices. A lattice $L$ is called
$ST$-distributive if it satisfies a relative distributive property with
respect to two subsets $S,T\subseteq L$. The idea is that all elements of $S$
can be distributed into any two elements of $T$ in both ways: meet into join
and join into meet. We now provide a formal definition.

######  Definition 2.1.

($ST$-distributive Lattice). Given a lattice $L$ with $S,T\subseteq L$, we
define:

  * •

$ST$-meet Distributive Lattice: $L$ is said to be $ST$-meet distributive if
for all $s\in S$ and $t_{1},t_{2}\in T$,

$s\land\left(t_{1}\lor t_{2}\right)=\left(s\land t_{1}\right)\lor\left(s\land
t_{2}\right)\;.$ (1)

  * •

$ST$-join Distributive Lattice: $L$ is said to be $ST$-join distributive if
for all $s\in S$ and $t_{1},t_{2}\in T$,

$s\lor\left(t_{1}\land t_{2}\right)=\left(s\lor t_{1}\right)\land\left(s\lor
t_{2}\right)\;.$ (2)

  * •

$ST$-distributive Lattice: $L$ is said to be $ST$-distributive if it is both
$ST$-meet distributive and $ST$-join distributive.

$1$ $u$ $v$ $w$ $0$ Figure 1: The pentagon $\mathbf{N}_{5}$

$1$ $a$ $b$ $c$ $0$ Figure 2: The diamond $\mathbf{M}_{3}$

$1$ $a$ $b$ $c$ $d$ $e$ $0$ Figure 3: Lattice $L$ of Example 2.3

A couple of remarks are in order. First, observe that this definition
generalizes distributive lattices which happen to be lattices that are
$ST$-distributive for $S=T=L$. Second, every lattice $L$ is vacuously
$ST$-distributive given $S=\emptyset$ or $T=\emptyset$. Third, we will
occasionally use the term relative distributive property to refer to the
$ST$-distributivity of a lattice. We now give an example of an
$ST$-distributive lattice.

######  Example 2.2.

(Example of $ST$-distributive Lattice). Consider the lattice $\mathbf{N}_{5}$
shown in Fig. 2. It is known to be non-distributive [2, 3, 5]. However, if
$S=\left\\{u,v\right\\}$ and $T=\left\\{w,0\right\\}$, then it is
$ST$-distributive. To verify this, we must check that it is both $ST$-meet
distributive and $ST$-join distributive. The necessary computations are
provided in Table 1 for the case $s=u$ in Equations (1) and (2). The
computations for $s=v$ are identical.

Table 1: Computations to show $\mathbf{N}_{5}$ is $ST$-distributive in Example 2.2 $ST$-meet |  |  $ST$-join
---|---|---
$u\land\left(w\lor 0\right)=0$ |  | $u\lor\left(w\land 0\right)=u$
$\left(u\land w\right)\lor\left(u\land 0\right)=0$ |  | $\left(u\lor w\right)\land\left(u\lor 0\right)=u$
$u\land\left(0\lor w\right)=0$ |  | $u\lor\left(0\land w\right)=u$
$\left(u\land 0\right)\lor\left(u\land w\right)=0$ |  | $\left(u\lor 0\right)\land\left(u\lor w\right)=u$
$u\land\left(0\lor 0\right)=0$ |  | $u\lor\left(0\land 0\right)=u$
$\left(u\land 0\right)\lor\left(u\land 0\right)=0$ |  | $\left(u\lor 0\right)\land\left(u\lor 0\right)=u$
$u\land\left(w\lor w\right)=0$ |  | $u\lor\left(w\land w\right)=1$
$\left(u\land w\right)\lor\left(u\land w\right)=0$ |  | $\left(u\lor w\right)\land\left(u\lor w\right)=1$

In practice, it will not be necessary to do all the computations done in
Example 2.2. We will show that the order structure of the lattice will
guarantee that certain triples $(s,t_{1},t_{2})$ will satisfy Equations (1)
and (2). See Property 2.2 in Subsect. 2.2 for details.

Next, we briefly discuss our new definition. We begin with a counter-example
to show that $ST$-meet distributive and $ST$-join distributive are not
equivalent in general.

######  Example 2.3.

($ST$-meet Distributive $\centernot\iff$ $ST$-join Distributive). Consider the
lattice $L=\left\\{0,a,b,c,d,e,1\right\\}$ shown in Fig. 3. Let
$S=\left\\{a\right\\}$ and $T=\left\\{b,c\right\\}$. Then $L$ is $ST$-meet
distributive but not $ST$-join distributive.

######  Proof 2.4.

$ST$-meet Distributive: There are four cases:

$a\land\left(b\lor c\right)\qquad a\land\left(c\lor b\right)\qquad
a\land\left(b\lor b\right)\qquad a\land\left(c\lor c\right).$ (3)

Note that the second follows from the first by commutativity of lattice
operations while the last two are immediate by idempotency. Hence, we need to
only verify the first:

$a\land\left(b\lor c\right)=a\land 1=a=d\lor e=\left(a\land
b\right)\lor\left(a\land c\right)\;.$ (4)

Not $ST$-join Distributive: Note that

$a\lor\left(b\land c\right)=a\lor 0=a\neq 1=1\land 1=\left(a\lor
b\right)\land\left(a\lor c\right)\;.$ (5)

∎

Another point to emphasize is that the subsets $S$ and $T$ in our definition
are not interchangeable in general, or equivalently, that the pair
$\left(S,T\right)$ is ordered. The following example illustrates this.

######  Example 2.5.

($ST$-distributive $\centernot\iff$ $TS$-distributive). Consider the lattice
$\mathbf{M}_{3}$ shown in Fig. 2. Let $S=\left\\{a,b\right\\}$ and
$T=\left\\{c\right\\}$. Then $\mathbf{M}_{3}$ is $ST$-distributive but not
$TS$-distributive.

######  Proof 2.6.

ST-distributive: This follows from idempotency of lattice operations because
$T$ only has one element. For instance,

$a\land\left(c\lor c\right)=a\land c=\left(a\land c\right)\lor\left(a\land
c\right)\;.$ (6)

Not TS-distributive: Observe that

$c\land\left(a\lor b\right)=c\land 1=c\neq 0=0\lor 0=\left(c\land
a\right)\lor\left(c\land b\right)\;.$ (7)

∎

We now introduce a special pair $\left(S,T\right)$ of proper subsets of a
lattice: those that make it $ST$-distributive but that cannot be expanded
further without either, breaking our relative distributive property or
becoming the whole lattice. We call them maximal $ST$-pairs.

######  Definition 2.7.

(Maximal $ST$-pair). Let $S$ and $T$ be proper subsets of $L$. A pair
$\left(S,T\right)$ is called a maximal $ST$-pair of $L$ if

  1. 1.

$L$ is $ST$-distributive.

  2. 2.

There is no proper $S^{{}^{\prime}}\supsetneq S$ such that $L$ is
$S^{{}^{\prime}}T$-distributive.

  3. 3.

There is no proper $T^{{}^{\prime}}\supsetneq T$ such that $L$ is
$ST^{{}^{\prime}}$-distributive.

######  Example 2.8.

(Maximal and Non-maximal $ST$-pairs). Consider the pair of (proper) subsets
$S=\left\\{u,v\right\\}$ and $T=\left\\{w,0\right\\}$ from Example 2.2.
Although, $\mathbf{N}_{5}$ is $ST$-distributive, this pair is not a maximal
$ST$-pair because if we let $S^{\prime}=\left\\{0,u,v,w\right\\}$ and
$T^{\prime}=\left\\{0,1,w\right\\}$, then $\mathbf{N}_{5}$ is
$S^{\prime}T^{\prime}$-distributive. Now, $\left(S^{\prime},T^{\prime}\right)$
is a maximal $ST$-pair of $\mathbf{N}_{5}$. Clearly, $S^{\prime}$ cannot be
expanded further without making it all $N_{5}$. On the other hand, trying to
add either $u$ or $v$ to $T$ breaks the relative distributive property because
$u\land\left(v\lor w\right)$ and $v\lor\left(u\land w\right)$ do not
distribute.

We conclude this subsection by remarking that $ST$-distributive lattices are
more general than what will be discussed in this paper. At present, we will
limit ourselves to finding $ST$-distributive lattices in non-distributive
lattices. However, Definition 2.1 does not require the initial lattice $L$ to
be non-distributive. In fact, we mentioned earlier that a lattice $L$ is
distributive if and only if it is $ST$-distributive for $S=T=L$. Therefore,
the study of $ST$-distributive lattices can encompass problems regarding
distributive lattices such as finding and describing their maximal proper
sublattices as done in [6]. In such a context, it is helpful to observe that
for a proper sublattice $S$ of $L$, the fact that $L$ is an $SS$-distributive
lattice is equivalent to $S$ being a distributive (proper) sublattice of $L$.
Furthermore, if $\left(S,S\right)$ is a maximal $\left(S,S\right)$-pair, this
implies that $S$ is a proper maximal distributive sublattice of $L$.

###  2.2 Basic Properties

With the definitions established, this subsection introduces some basic
properties of $ST$-distributive lattices. Two of them, the efficiency criteria
and the closure of $S$’s given fixed $T$, will facilitate our search of
subsets inducing $ST$-distributivity.

The efficiency criteria stated in Property 2.2 gives conditions on a triple of
elements $a$, $b$, and $c$ of a lattice that each guarantees that the first
element under meet (or join) will distributive into the join (or meet) of the
other two. The conditions all involve some form of order relation among the
elements of the triple. Their advantage is that for some triples, we can
determine distribution from simply comparing the elements rather than
computing meets and joins.

(Efficiency Criteria). Let $L$ be a lattice with $a,b,c\in L$ such that the
triple $(a,b,c)$ satisfies any of the following conditions:

  1. 1.

$b\leq c$ or $b\geq c$

  2. 2.

$a\geq b$ and $a\geq c$

  3. 3.

$a\leq b$ and $a\leq c$

Then the following hold:

$\displaystyle a\land\left(b\lor c\right)=\left(a\land
b\right)\lor\left(a\land c\right)\;\>$ (8) $\displaystyle a\lor\left(b\land
c\right)=\left(a\lor b\right)\land\left(a\lor c\right)\;.$ (9)

######  Proof 2.9.

We show only that each condition implies Equation (8). Duality gives Equation
(9) because condition 1 is self-dual and conditions 2 and 3 are each other’s
duals.

Condition 1: By commutativity, it is sufficient to show the result for only
one of the two inequalities of condition 1. Without loss of generality,
suppose that $b\leq c$. Then $a\land b\leq a\land c$. Applying the Connecting
Lemma [2, 3], we get

$a\land\left(b\lor c\right)=a\land c=\left(a\land b\right)\lor\left(a\land
c\right)\;.$ (10)

Condition 2: Suppose that $a\geq b$ and $a\geq c$. Then by definition of
$\lor$ as the supremum, $a\geq b\lor c$. This implies that

$a\land\left(b\lor c\right)=b\lor c\;.$ (11)

On the other hand, $a\geq b$ and $a\geq c$ also imply that $a\land b=b$ and
$a\land c=c$. Therefore,

$\left(a\land b\right)\lor\left(a\land c\right)=b\lor c$ (12)

and distribution follows from Equations (11) and (12).

Condition 3: This is similar to the proof for condition 2 except that we get

$a\land\left(b\lor c\right)=a=a\lor a=\left(a\land b\right)\lor\left(a\land
c\right)\;.$ (13)

∎

We make a few comments on Property 2.2. Considering conditions 2 and 3, it is
natural to ask what happens if $a$ is comparable to both $b$ and $c$ but in
different ways. Then we have either $b\leq a\leq c$ or $c\leq a\leq b$ and
hence, condition 1 by transitivity of $\leq$. Thus, it is not necessary to
list this as a separate condition. Also note that as a corollary of Property
2.2, we get that we can always add 0 and 1 to any $S$ or $T$ without affecting
the relative distributive property. If $a=0$ or $a=1$, condition 2 or 3 is
satisfied and if either $b$ or $c$ is 0 or 1, then condition 1 is satisfied.
In addition, we obtain the following useful fact.

######  Example 2.10.

(T-chain). Let $L$ be any lattice (finite or infinite), $S$ any subset of $L$,
and $T$ any chain of $L$. Then $L$ is $ST$-distributive by condition 1 of
Property 2.2.

The second property we establish says that if we fix the set $T$ of a pair
$\left(S,T\right)$ that we are considering in a lattice $L$, then the set of
possible subsets $S$ that make $L$ $ST$-distributive is closed under union.

(Closure of Union of $S$’s with Fixed $T$). Let $L$ be a lattice with
$S_{1},S_{2},T\subseteq L$. If $L$ is $S_{1}T$-distributive and
$S_{2}T$-distributive, then $L$ is $\left(S_{1}\cup
S_{2}\right)T$-distributive.

######  Proof 2.11.

Let $s\in S_{1}\cup S_{2}$. Then $s\in S_{1}$ or $s\in S_{2}$. If $s\in
S_{1}$, then for all $t_{1},t_{2}\in T$,

$\displaystyle s\land\left(t_{1}\lor t_{2}\right)$ $\displaystyle=\left(s\land
t_{1}\right)\lor\left(s\land t_{2}\right)$ (14) $\displaystyle
s\lor\left(t_{1}\land t_{2}\right)$ $\displaystyle=\left(s\lor
t_{1}\right)\land\left(s\lor t_{2}\right)$ (15)

because $L$ is $S_{1}T$-distributive. The case that $s\in S_{2}$ is done in
the same way. Therefore, $L$ is $\left(S_{1}\cup S_{2}\right)T$-distributive.
∎

An important consequence of Property 2.10 is that for a given $T$, we can form
a maximum $S$ such that $L$ is $ST$-distributive by checking all elements in
$L$, and picking the ones that distribute into any pair of elements of $T$.
This avoids checking each subset of $L$ and will play a crucial role in
computing $ST$-distributivity in the next subsection.

We now present an interesting algebraic extension of the result of Property
2.10.

######  Lemma 2.12.

(Complete Lattice of $S$’s with Fixed $T$). Let $L$ be any lattice. For a
fixed $T$, the collection of all subsets $S\subseteq L$ such that $L$ is
$ST$-distributive forms a complete distributive lattice of sets. The join and
meet operations are given by union and intersection respectively. We denote
this lattice $\mathcal{S}\left(L,T\right)$.

######  Proof 2.13.

Similar to Property 2.10. ∎

When $L$ is a finite lattice, the lattice $\mathcal{S}\left(L,T\right)$ is
also finite. In this case, the latter is a bounded lattice whose top element
is the set of all elements in $L$ that are meet and join distributive in $T$.
This is $L$ itself if $L$ is distributive. When $L$ is not distributive, it is
a subset of $L$ the contains the desired set of step 1 of Algorithm 2.15 (it
may be larger since the algorithm has additional restrictions from Problem
2.15). This subset may or may not be proper (e.g. it is all $L$ if $T$ is a
chain).

One last matter that we touch is how to construct new $ST$-distributive
lattices from known ones. It is known that the distributive property of
lattices is preserved by different lattice constructs: sublattices, products
of lattices, lattice homomorphisms, and dual lattices. The following
proposition generalizes this to $ST$-distributive lattices. The proofs come
straight from the definitions and are thus omitted.

######  Proposition 2.14.

(Preservation of $ST$-distributivity by Lattice Constructs). Let $L$ be a
lattice with subsets $S$ and $T$ such that $L$ is $ST$-distributive.

  1. 1.

If $K$ is a sublattice of $L$, then $K$ is $S_{1}T_{1}$-distributive for
$S_{1}=S\cap K$ and $T_{1}=T\cap K$.

  2. 2.

If $L^{\prime}$ is another lattice with subsets $S^{\prime}$ and $T^{\prime}$
such that $L^{\prime}$ is $S^{\prime}T^{\prime}$-distributive, then $L\times
L^{\prime}$ is $\left(S\times S^{\prime}\right)\left(T\times
T^{\prime}\right)$-distributive.

  3. 3.

If $\phi:L\rightarrow K$ is a lattice homomorphism that is onto, then $K$ is
$\phi\left(S\right)\phi\left(T\right)$-distributive.

  4. 4.

If $L^{\partial}$ represents the dual lattice of $L$ and $S$ and $T$ are
sublattices with duals $S^{\partial}$ and $T^{\partial}$, then $L^{\partial}$
is $S^{\partial}T^{\partial}$-distributive.

###  2.3 Search for $ST$-distributive Lattices

We want to study non-distributive lattices to find the subsets $S$ and $T$ for
which they are $ST$-distributive. The long-term goal is to identify families
of lattices with a particular characterization of the subsets inducing this.
As a result, we have the following initial problem, where $L^{*}$ denotes the
set of non-identity elements of a lattice $L$, i.e.
$L^{*}=L\setminus\left\\{0,1\right\\}$.

######  Problem 2.15.

($ST$-distributive Search). Given a non-distributive lattice $L$, we want to
find all of its maximal $ST$-pairs subject to the following conditions:

  1. 1.

$S\cap T=\emptyset$

  2. 2.

$S,T\subseteq L^{*}$

  3. 3.

$S\neq\emptyset$ and $T\neq\emptyset$

We explain the reasons for our conditions. The disjointness of $S$ and $T$ is
for narrowing the search space. Our disregard for 0 and 1 stems from the fact
that they can always be added to any $S$ or $T$ without affecting the relative
distributive property of the pair. This is a consequence of Property 2.2
mentioned earlier. Finally, the non-emptiness of both $S$ and $T$ is to focus
only on non-trivial pairs with actual distribution of elements.

We make a _very important clarification_ before moving forward. _From now on,
when we refer to a maximal $ST$-pair of a lattice $L$, we will mean a pair
$\left(S,T\right)$ that satisfies not only Definition 2.7 but also the
conditions of Problem 2.15_. In particular, we remark that the maximality of a
set of the pair will be altered by both the disjointness condition and the
disregard of proper subsets of $L$ not contained in $L^{*}$.

Having established the specifications of our search, we explain our method for
carrying in out. We write a SageMath program that does an “intelligent”
exhaustive search by applying Properties 2.2 and 2.10. An overview of how it
works is given in Algorithm 2.15. Property 2.10 allows us to construct a
maximum $S$ for each $T$ by iterating across all elements of $L^{*}\setminus
T$, putting those that distribute in one set. The resulting pair
$\left(S,T\right)$ is a maximal $ST$-pair unless there is a $T^{\prime}$
strictly containing $T$ that has the same maximum $S$. This motivates our
processing of the subsets $T$ by increasing size. Property 2.2 reduces the
computations done when determining who can be added to $S$. After running the
program, we manually verify the results for correctness and completeness. This
finishes our discussion of our search problem.

($ST$-program Algorithm).

  * •

Specifications:

    1. 1.

Input: lattice $L$

    2. 2.

Output: list of maximal $ST$-pairs of $L$ with Problem 2.15 conditions

  * •

Process Overview:

For each $T\subseteq L^{*}$ (by increasing size):

    1. 1.

Build largest possible set $S$ such that $L$ is $ST$-distributive.

      1. (a)

Add to candidate set $S$ all elements $s$ of $L^{*}\setminus T$ such that $s$
distributes into $T$.

    2. 2.

If returned $S$ is non-empty, add pair $\left(S,T\right)$ to list of pairs and
remove any pairs contained by $\left(S,T\right)$.

###  2.4 Family $\mathbf{M}_{n,n}$

Before we begin, we clarify some notation. For any natural number $n$,
$\mathbf{n}$ denotes the chain of $n$ elements and $\mathbf{\bar{n}}$ the
antichain of $n$ elements, respectively. In addition, for lattices $L$ and
$K$, $L\oplus K$ denotes their linear sum and $L\times K$ their product.

We now introduce the family of lattices with which we have begun our search of
$ST$-distributive lattices: $\mathbf{M}_{n,n}$. It consists of lattices
obtained by gluing two copies of
$\mathbf{M}_{n}=\mathbf{1}\oplus\mathbf{\bar{n}}\oplus\mathbf{1}$ in a
particular manner for each natural number $n\geq 3$. The pictorial idea is to
take the rightmost edge from the top element in the Hasse diagram of one of
the copies and make it equal to the leftmost edge from the bottom element of
the other copy’s diagram. Definition 2.16 formally describes the family and
presents relevant notation. Some members of the family are given in Example
2.17.

######  Definition 2.16.

(Lattice $\mathbf{M}_{n,n}$). For a natural number $n\geq 3$, the lattice
$\mathbf{M}_{n,n}$ has element set
$\left\\{0,1,a_{1},...,a_{n},b_{1},...,b_{n}\right\\}$ with $0$ and $1$ being
the bottom and top element respectively. $0$ is covered by all of the
$a_{i}$’s while $1$ covers all of the $b_{j}$’s. In addition $a_{n}$ is
covered by all the $b_{j}$’s and $b_{1}$ covers all of the $a_{i}$’s. No other
covering relations exist. This results in $\mathbf{M}_{n,n}$ having two
isomorphic copies of $\mathbf{M}_{n}$:
$\left\\{0,a_{1},a_{2},...,a_{n},b_{1}\right\\}$ and
$\left\\{a_{n},b_{1},b_{2},...,b_{n},1\right\\}$. Note that both of them share
$a_{n}$ and $b_{1}$ (the shared edge from the pictorial description above).

######  Example 2.17.

(Examples of $\mathbf{M}_{n,n}$). $\mathbf{M}_{3,3}$ and $\mathbf{M}_{4,4}$
are shown in Figs. 5 and 5 respectively. Note that

$\displaystyle\mathbf{M}_{3}\cong\left\\{0,a_{1},a_{2},a_{3},b_{1}\right\\}\cong\left\\{a_{3},b_{1},b_{2},b_{3},1\right\\}\quad\;\;\,$
(16)
$\displaystyle\mathbf{M}_{4}\cong\left\\{0,a_{1},a_{2},a_{3},a_{4},b_{1}\right\\}\cong\left\\{a_{4},b_{1},b_{2},b_{3},b_{4},1\right\\}.$
(17)

$1$ $b_{1}$ $b_{2}$ $b_{3}$ $a_{1}$ $a_{2}$ $a_{3}$ $0$ Figure 4: Lattice
$\mathbf{M}_{3,3}$

$1$ $b_{1}$ $b_{2}$ $b_{3}$ $b_{4}$ $a_{1}$ $a_{2}$ $a_{3}$ $a_{4}$ $0$ Figure
5: Lattice $\mathbf{M}_{4,4}$

We briefly discuss the family $\mathbf{M}_{n,n}$. First, we introduce some
terms we use to refer to particular subsets and elements of
$\mathbf{M}_{n,n}$. This vocabulary will facilitate the discussion of our
results in the next subsection.

######  Definition 2.18.

(Level). In $\mathbf{M}_{n,n}$, a level is a set of elements that constitutes
the antichain ($\mathbf{\bar{n}}$) of a copy of $\mathbf{M}_{n}$. In other
words, the sets $\left\\{a_{1},...,a_{n}\right\\}$ and
$\left\\{b_{1},...,b_{n}\right\\}$.

######  Definition 2.19.

(Link Element). In $\mathbf{M}_{n,n}$, a link element (or link) is one of the
two elements shared by both isomorphic copies of $\mathbf{M}_{n}$, that is,
$a_{n}$ and $b_{1}$.

We complete our introduction to the family $\mathbf{M}_{n,n}$ by remarking
that the lattice $\mathbf{M}_{n,n}$ is both modular and non-distributive for
$n\geq 3$. Both facts follow from applying the
$\mathbf{M}_{3}$-$\mathbf{N}_{5}$ Theorem [2, 3, 5]: $\mathbf{M}_{n,n}$ always
has two isomorphic copies of $\mathbf{M}_{n}$ as previously mentioned (and
hence of $\mathbf{M}_{3}$ since $n\geq 3$), but never an isomorphic copy of
$\mathbf{N}_{5}$. Thus, we have a family of modular and non-distributive
lattices. This is good because it allows us to study $ST$-distributivity non-
trivially in a relatively “controlled” environment. Finally, note that it is
possible to construct $\mathbf{M}_{2,2}$ and $\mathbf{M}_{1,1}$ following
Definition 2.16. However, the resulting lattices would be isomorphic to
$\mathbf{2}\times\mathbf{3}$ and $\mathbf{4}$ ($\mathbf{n}$ denotes the chain
of $n$ elements) and thus, distributive. This is what motivates our
specification that $n\geq 3$ when defining the family.

###  2.5 Results

Here, we present our results in the study of $ST$-distributivity in the family
$\mathbf{M}_{n,n}$. We start with some computational results and then present
theoretical results derived from them, concluding with a complete
characterization of the maximal $ST$-pairs of this lattice family. Throughout
the whole discussion, the reader should bear in mind the clarification we made
in Subsect. 2.3 about what we mean when we refer to a maximal $ST$-pair.

####  2.5.1 Computational Results.

Running the program discussed in Algorithm 2.15 with inputs $\mathbf{M}_{3,3}$
and $\mathbf{M}_{4,4}$ yields 27 and 42 maximal $ST$-pairs respectively. These
are listed in Tables 2 and 3. Manual verification then shows that these lists
are correct and complete. Further study of these pairs results in identifying
5 types into which all of them belong. These types are described with
constructions that select elements based on their role in the structure of
$\mathbf{M}_{n,n}$ (links and levels).

######  Remark 2.20.

(5 Types of Maximal $ST$-pairs). All of the maximal $ST$-pairs of
$\mathbf{M}_{3,3}$ and $\mathbf{M}_{4,4}$ are of one of the following 5 types.
The type of each pair indicated in Tables 2 and 3. An example of each type in
$\mathbf{M}_{4,4}$ is illustrated in Figures 10–10 ($S$ in cyan, $T$ in
black).

  1. 1.

_T-chain_ : $T$ is a chain. $S$ has all other elements.

  2. 2.

_S-link_ : $S$ has only one of the two links. $T$ has one more element in this
link’s level and all of the elements in the other level.

  3. 3.

_S-2-links_ : $S$ has both links. $T$ has one non-link element of each level

  4. 4.

_S-level_ : $S$ is one of the two levels. $T$ has two elements in the other
level, one of which must be its link.

  5. 5.

_S-level-minus-link_ : $S$ is one of the two levels minus its link. $T$ is
both links plus another element from the level that does not contain $S$.

Table 2: Maximal $ST$-pairs of $\mathbf{M}_{3,3}$ $S$ | $T$ | Type
---|---|---
1  $\left\\{a_{2},a_{3},b_{1},b_{2},b_{3}\right\\}$ | $\left\\{a_{1}\right\\}$ | 1
2  $\left\\{a_{1},a_{3},b_{1},b_{2},b_{3}\right\\}$ | $\left\\{a_{2}\right\\}$ | 1
3  $\left\\{a_{1},a_{2},b_{1},b_{2},b_{3}\right\\}$ | $\left\\{a_{3}\right\\}$ | 1
4  $\left\\{a_{1},a_{2},a_{3},b_{2},b_{3}\right\\}$ | $\left\\{b_{1}\right\\}$ | 1
5  $\left\\{a_{1},a_{2},a_{3},b_{1},b_{3}\right\\}$ | $\left\\{b_{2}\right\\}$ | 1
6  $\left\\{a_{1},a_{2},a_{3},b_{1},b_{2}\right\\}$ | $\left\\{b_{3}\right\\}$ | 1
7  $\left\\{a_{2},a_{3},b_{2},b_{3}\right\\}$ | $\left\\{a_{1},b_{1}\right\\}$ | 1
8  $\left\\{a_{1},a_{3},b_{2},b_{3}\right\\}$ | $\left\\{a_{2},b_{1}\right\\}$ | 1
9  $\left\\{a_{1},a_{2},b_{2},b_{3}\right\\}$ | $\left\\{a_{3},b_{1}\right\\}$ | 1
10  $\left\\{a_{1},a_{2},b_{1},b_{3}\right\\}$ | $\left\\{a_{3},b_{2}\right\\}$ | 1
11  $\left\\{a_{1},a_{2},b_{1},b_{2}\right\\}$ | $\left\\{a_{3},b_{3}\right\\}$ | 1
12  $\left\\{b_{1}\right\\}$ | $\left\\{a_{1},a_{2},a_{3},b_{2}\right\\}$ | 2
13  $\left\\{b_{1}\right\\}$ | $\left\\{a_{1},a_{2},a_{3},b_{3}\right\\}$ | 2
14  $\left\\{a_{3}\right\\}$ | $\left\\{a_{1},b_{1},b_{2},b_{3}\right\\}$ | 2
15  $\left\\{a_{3}\right\\}$ | $\left\\{a_{2},b_{1},b_{2},b_{3}\right\\}$ | 2
16  $\left\\{a_{3},b_{1}\right\\}$ | $\left\\{a_{1},b_{2}\right\\}$ | 3
17  $\left\\{a_{3},b_{1}\right\\}$ | $\left\\{a_{1},b_{3}\right\\}$ | 3
18  $\left\\{a_{3},b_{1}\right\\}$ | $\left\\{a_{2},b_{2}\right\\}$ | 3
19  $\left\\{a_{3},b_{1}\right\\}$ | $\left\\{a_{2},b_{3}\right\\}$ | 3
20  $\left\\{a_{1},a_{2},a_{3}\right\\}$ | $\left\\{b_{1},b_{2}\right\\}$ | 4
21  $\left\\{a_{1},a_{2},a_{3}\right\\}$ | $\left\\{b_{1},b_{3}\right\\}$ | 4
22  $\left\\{b_{1},b_{2},b_{3}\right\\}$ | $\left\\{a_{1},a_{3}\right\\}$ | 4
23  $\left\\{b_{1},b_{2},b_{3}\right\\}$ | $\left\\{a_{2},a_{3}\right\\}$ | 4
24  $\left\\{a_{1},a_{2}\right\\}$ | $\left\\{a_{3},b_{1},b_{2}\right\\}$ | 5
25  $\left\\{a_{1},a_{2}\right\\}$ | $\left\\{a_{3},b_{1},b_{3}\right\\}$ | 5
26  $\left\\{b_{2},b_{3}\right\\}$ | $\left\\{a_{1},a_{3},b_{1}\right\\}$ | 5
27  $\left\\{b_{2},b_{3}\right\\}$ | $\left\\{a_{2},a_{3},b_{1}\right\\}$ | 5
Table 3: Maximal $ST$-pairs of $\mathbf{M}_{4,4}$ $S$ | $T$ | Type
---|---|---
1  $\left\\{a_{2},a_{3},a_{4},b_{1},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{1}\right\\}$ | 1
2  $\left\\{a_{1},a_{3},a_{4},b_{1},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{2}\right\\}$ | 1
3  $\left\\{a_{1},a_{2},a_{4},b_{1},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{3}\right\\}$ | 1
4  $\left\\{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{4}\right\\}$ | 1
5  $\left\\{a_{1},a_{2},a_{3},a_{4},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{b_{1}\right\\}$ | 1
6  $\left\\{a_{1},a_{2},a_{3},a_{4},b_{1},b_{3},b_{4}\right\\}$ | $\left\\{b_{2}\right\\}$ | 1
7  $\left\\{a_{1},a_{2},a_{3},a_{4},b_{1},b_{2},b_{4}\right\\}$ | $\left\\{b_{3}\right\\}$ | 1
8  $\left\\{a_{1},a_{2},a_{3},a_{4},b_{1},b_{2},b_{3}\right\\}$ | $\left\\{b_{4}\right\\}$ | 1
9  $\left\\{a_{2},a_{3},a_{4},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{1},b_{1}\right\\}$ | 1
10  $\left\\{a_{1},a_{3},a_{4},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{2},b_{1}\right\\}$ | 1
11  $\left\\{a_{1},a_{2},a_{4},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{3},b_{1}\right\\}$ | 1
12  $\left\\{a_{1},a_{2},a_{3},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{4},b_{1}\right\\}$ | 1
13  $\left\\{a_{1},a_{2},a_{3},b_{1},b_{3},b_{4}\right\\}$ | $\left\\{a_{4},b_{2}\right\\}$ | 1
14  $\left\\{a_{1},a_{2},a_{3},b_{1},b_{2},b_{4}\right\\}$ | $\left\\{a_{4},b_{3}\right\\}$ | 1
15  $\left\\{a_{1},a_{2},a_{3},b_{1},b_{2},b_{3}\right\\}$ | $\left\\{a_{4},b_{4}\right\\}$ | 1
16  $\left\\{b_{1}\right\\}$ | $\left\\{a_{1},a_{2},a_{3},a_{4},b_{2}\right\\}$ | 2
17  $\left\\{b_{1}\right\\}$ | $\left\\{a_{1},a_{2},a_{3},a_{4},b_{3}\right\\}$ | 2
18  $\left\\{b_{1}\right\\}$ | $\left\\{a_{1},a_{2},a_{3},a_{4},b_{4}\right\\}$ | 2
19  $\left\\{a_{4}\right\\}$ | $\left\\{a_{1},b_{1},b_{2},b_{3},b_{4}\right\\}$ | 2
20  $\left\\{a_{4}\right\\}$ | $\left\\{a_{2},b_{1},b_{2},b_{3},b_{4}\right\\}$ | 2
21  $\left\\{a_{4}\right\\}$ | $\left\\{a_{3},b_{1},b_{2},b_{3},b_{4}\right\\}$ | 2
22  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{1},b_{2}\right\\}$ | 3
23  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{1},b_{3}\right\\}$ | 3
24  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{1},b_{4}\right\\}$ | 3
25  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{2},b_{2}\right\\}$ | 3
26  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{2},b_{3}\right\\}$ | 3
27  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{2},b_{4}\right\\}$ | 3
28  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{3},b_{2}\right\\}$ | 3
29  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{3},b_{3}\right\\}$ | 3
30  $\left\\{a_{4},b_{1}\right\\}$ | $\left\\{a_{3},b_{4}\right\\}$ | 3
31  $\left\\{a_{1},a_{2},a_{3},a_{4}\right\\}$ | $\left\\{b_{1},b_{2}\right\\}$ | 4
32  $\left\\{a_{1},a_{2},a_{3},a_{4}\right\\}$ | $\left\\{b_{1},b_{3}\right\\}$ | 4
33  $\left\\{a_{1},a_{2},a_{3},a_{4}\right\\}$ | $\left\\{b_{1},b_{4}\right\\}$ | 4
34  $\left\\{b_{1},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{1},a_{4}\right\\}$ | 4
35  $\left\\{b_{1},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{2},a_{4}\right\\}$ | 4
36  $\left\\{b_{1},b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{3},a_{4}\right\\}$ | 4
37  $\left\\{a_{1},a_{2},a_{3}\right\\}$ | $\left\\{a_{4},b_{1},b_{2}\right\\}$ | 5
38  $\left\\{a_{1},a_{2},a_{3}\right\\}$ | $\left\\{a_{4},b_{1},b_{3}\right\\}$ | 5
39  $\left\\{a_{1},a_{2},a_{3}\right\\}$ | $\left\\{a_{4},b_{1},b_{4}\right\\}$ | 5
40  $\left\\{b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{1},a_{4},b_{1}\right\\}$ | 5
41  $\left\\{b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{2},a_{4},b_{1}\right\\}$ | 5
42  $\left\\{b_{2},b_{3},b_{4}\right\\}$ | $\left\\{a_{3},a_{4},b_{1}\right\\}$ | 5

$1$ $b_{1}$ $b_{2}$ $b_{3}$ $b_{4}$ $a_{1}$ $a_{2}$ $a_{3}$ $a_{4}$ $0$ Figure
6: T-chain pair

$1$ $b_{1}$ $b_{2}$ $b_{3}$ $b_{4}$ $a_{1}$ $a_{2}$ $a_{3}$ $a_{4}$ $0$ Figure
7: S-link pair

$1$ $b_{1}$ $b_{2}$ $b_{3}$ $b_{4}$ $a_{1}$ $a_{2}$ $a_{3}$ $a_{4}$ $0$ Figure
8: S-2-links pair

$1$ $b_{1}$ $b_{2}$ $b_{3}$ $b_{4}$ $a_{1}$ $a_{2}$ $a_{3}$ $a_{4}$ $0$ Figure
9: S-level pair

$1$ $b_{1}$ $b_{2}$ $b_{3}$ $b_{4}$ $a_{1}$ $a_{2}$ $a_{3}$ $a_{4}$ $0$ Figure
10: S-level-minus-link pair

The natural questions arising from Remark 2.20 are if these constructions of
maximal $ST$-pairs work for all other $\mathbf{M}_{n,n}$ (recalling $n\geq 3$)
and whether larger $n$’s yield maximal $ST$-pairs of other forms. We already
know that type T-chain will always work by Example 2.10. We show that the
remaining constructions work for all lattices of the $\mathbf{M}_{n,n}$ family
and prove that these five constructions are the only ones possible in it.

####  2.5.2 Preliminary Theoretical Results.

To develop our main theoretical results, we require some preliminary results:
the modular comparability criteria for distributivity (MCCD) and Proposition
2.23. The MCCD gives a simple condition that guarantees distribution for any
triple of elements in a non-distributive but modular lattice.

######  Proposition 2.21.

(Modular Comparability Criteria for Distributivity — MCCD). Let $L$ be a
modular lattice with elements $a,b,c\in L$. If there is any comparability
between any 2 of the 3 elements, then

$\displaystyle a\land\left(b\lor c\right)$ $\displaystyle=\left(a\land
b\right)\lor\left(a\land c\right)$ (18) $\displaystyle a\lor\left(b\land
c\right)$ $\displaystyle=\left(a\lor b\right)\land\left(a\lor c\right).$ (19)

######  Proof 2.22.

By duality, we need only to show Eq. (18). There are three cases. First, If
$b\leq c$ or $b\geq c$, we are done by Property 2.2. Second, if $a\leq b$ or
$a\leq c$, then $a\leq b\lor c$. Thus, the Connecting Lemma [2, 3] and the
absorption property of lattices give

$a\land\left(b\lor c\right)=a=\left(a\land b\right)\lor\left(a\land
c\right)\;.$ (20)

Finally, we consider $a\geq b$ or $a\geq c$. Suppose that $a\geq c$, then by
modularity and the Connecting Lemma [2, 3],

$a\land\left(b\lor c\right)=\left(a\land b\right)\lor c=\left(a\land
b\right)\lor\left(a\land c\right)\;.$ (21)

The sub-case $a\geq b$ then follows from commutativity of $\lor$. Therefore,
Equation (18) is satisfied whenever $\left\\{a,b,c\right\\}$ is not an
antichain. ∎

The importance of the MCCD is that it implies that we need only to worry about
triples that are antichains when checking for relative distributivity. Note
that in general, the converse of MCCD is not true: a triple that is an
antichain may distribute (e.g. a triple of singleton sets in a power set
lattice). However, in $\mathbf{M}_{n,n}$, antichains never distribute.

######  Proposition 2.23.

(Antichains Not Distributive in $\mathbf{M}_{n,n}$). Suppose $n\geq 3$ and
$x,y,z\in\mathbf{M}_{n,n}$ are distinct elements. If $\left\\{x,y,z\right\\}$
is an antichain, then

$\displaystyle x\land\left(y\lor z\right)$ $\displaystyle\neq\left(x\land
y\right)\lor\left(x\land z\right)$ (22) $\displaystyle y\land\left(x\lor
z\right)$ $\displaystyle\neq\left(y\land x\right)\lor\left(y\land z\right)$
(23) $\displaystyle z\land\left(x\lor y\right)$ $\displaystyle\neq\left(z\land
x\right)\lor\left(z\land y\right).$ (24)

######  Proof 2.24.

There are two ways of choosing $x,y,z\in\mathbf{M}_{n,n}$ such that
$\left\\{x,y,z\right\\}$ is an antichain.

Case 1: $x,y,z$ are all elements of the same level of $\mathbf{M}_{n,n}$.
Without loss of generality, suppose that
$\left\\{x,y,z\right\\}=\left\\{a_{i},a_{j},a_{k}\right\\}$. Then we are done
by the fact that $a_{i},a_{j},a_{k}$ are three elements in the $\bf{\bar{n}}$
of an isomorphic copy of $\mathbf{M}_{n}$ in $\mathbf{M}_{n,n}$.

Case 2: $x,y,z$ consist of three non-link elements split among the two levels
of $\mathbf{M}_{n,n}$. Without loss of generality, suppose that
$\left\\{x,y,z\right\\}=\left\\{a_{i},a_{j},b_{k}\right\\}$ with $i,j\neq n$
and $k\neq 1$. Then

$\displaystyle a_{i}\land\left(a_{j}\lor b_{k}\right)=a_{i}\land 1=a_{i}\neq
0=0\lor 0=\left(a_{i}\land a_{j}\right)\lor\left(a_{i}\land b_{k}\right)$ (25)
$\displaystyle a_{j}\land\left(a_{i}\lor b_{k}\right)=a_{j}\land 1=a_{j}\neq
0=0\lor 0=\left(a_{j}\land a_{i}\right)\lor\left(a_{j}\land b_{k}\right)$ (26)
$\displaystyle b_{k}\land\left(a_{i}\lor a_{j}\right)=b_{k}\land
b_{1}=a_{n}\neq 0=0\lor 0=\left(b_{k}\land a_{i}\right)\lor\left(b_{k}\land
a_{j}\right).$ (27)

∎

The implication of Proposition 2.23 is that for a pair of subsets $S$ and $T$
of a lattice $L$ to be a maximal $ST$-pair, there can be no antichain of three
distinct elements in $L$ that has one element in $S$ and two in $T$. This
motivates the following definition.

######  Definition 2.25.

($ST$-breaking Antichain). Given $S,T\subseteq\mathbf{M}_{n,n}^{*}$, an
$ST$-breaking antichain is an ordered triple $(x,y,z)$ of elements of
$\mathbf{M}_{n,n}^{*}$ that form an antichain
$\left\\{x,y,z\right\\}\subseteq\mathbf{M}_{n,n}$ with $x\in S$ and $y,z\in
T$.

Observe that by commutativity of lattice operations, $(x,y,z)$ is an
$ST$-breaking antichain if and only if $(x,z,y)$ is.

####  2.5.3 Theoretical Results 1: Generalization of 5 Types.

We are now ready to prove that the constructions 2–5 in Remark 2.20 generalize
to all $\mathbf{M}_{n,n}$. Note the central role that the MCCD and
$ST$-breaking antichains play in the proofs and keep in mind our implicit
assumption that $n\geq 3$. To avoid tedious repetition, we begin with the
following remark that establishes some common ground for the subsequent
propositions.

######  Remark 2.26.

(Common arguments for Proposition 2.27-2.33) The following apply in
Propositions 2.27-2.33 and their proofs:

  1. 1.

$L_{1},L_{2}$ denote the two levels of $\mathbf{M}_{n,n}$.

  2. 2.

The $ST$-distributivity of the pair considered follows directly from the MCCD
via a case by case analysis of the ways of choosing $s$, $t_{1}$, and $t_{2}$
from it. The verification for this is purely computational and is thus
omitted.

  3. 3.

As a result of the previous item, the proof reduces to showing the maximality
of the $ST$-pair in question.

######  Proposition 2.27.

(S-link). Let $l,x\in L_{1}$ where $l$ is the link. If $S=\left\\{l\right\\}$
and $T=L_{2}\cup\left\\{x\right\\}$, then $\left(S,T\right)$ is a maximal
$ST$-pair of $\mathbf{M}_{n,n}$.

######  Proof 2.28.

Note that the only elements left in $\mathbf{M}_{n,n}^{*}$ are those in
$L_{1}\setminus\left\\{l,x\right\\}$. Let $y\in
L_{1}\setminus\left\\{l,x\right\\}$. If $y\in S$, then $\left(y,x,z\right)$ is
an $ST$-breaking antichain for any $z\in L_{2}$ except the link. Similarly, if
$y\in T$, then $\left(l,x,y\right)$ is an $ST$-breaking antichain. Hence,
neither $S$ nor $T$ can be expanded. ∎

######  Proposition 2.29.

(S-2-links). Let $l_{1}$ be $L_{1}$’s link and $l_{2}$ be $L_{2}$’s link.
Suppose $x\in L_{1}\setminus\left\\{l_{1}\right\\}$ and $y\in
L_{2}\setminus\left\\{l_{2}\right\\}$. If $S=\left\\{l_{1},l_{2}\right\\}$ and
$T=\left\\{x,y\right\\}$, then $\left(S,T\right)$ is a maximal $ST$-pair of
$\mathbf{M}_{n,n}$.

######  Proof 2.30.

Note that the only elements left in $\mathbf{M}_{n,n}^{*}$ are those in

$\left(L_{1}\setminus\left\\{l_{1},x\right\\}\right)\cup\left(L_{2}\setminus\left\\{l_{2},y\right\\}\right).$
(28)

Let $z$ be an element in this union. If $z\in S$, then $\left(z,x,y\right)$ is
an $ST$-breaking antichain. Now, suppose $z\in T$. Then either
$\left(l_{1},x,z\right)$ or $\left(l_{2},y,z\right)$ is an $ST$-breaking
antichain depending on whether $z\in L_{1}$ or $z\in L_{2}$. ∎

######  Proposition 2.31.

(S-level). Let $l,x\in L_{1}$ where $l$ is the link. If $S=L_{2}$ and
$T=\left\\{l,x\right\\}$, then $\left(S,T\right)$ is a maximal $ST$-pair of
$\mathbf{M}_{n,n}$.

######  Proof 2.32.

Note that the only elements left in $\mathbf{M}_{n,n}^{*}$ are those in
$L_{1}\setminus\left\\{l,x\right\\}$. Suppose $y\in
L_{1}\setminus\left\\{l,x\right\\}$. If $y\in S$, then $\left(y,x,l\right)$ is
an $ST$-breaking antichain. If $y\in T$, then $\left(z,x,y\right)$ is an
$ST$-breaking antichain for all $z\in S=L_{2}$ except the link. ∎

Observe that the only difference between $ST$-pairs of the type S-level-minus-
link and those of type S-level is that pairs of type S-level-minus-link take
the link element in the $S$ of a type S-level and add it to its $T$.

######  Proposition 2.33.

(S-level-minus-link). Let $l_{1},l_{2}$ be the respective links of
$L_{1},L_{2}$. Suppose $x\in L_{1}\setminus\left\\{l_{1}\right\\}$. If
$S=L_{2}\setminus\left\\{l_{2}\right\\}$ and
$T=\left\\{l_{1},l_{2},x\right\\}$, then $\left(S,T\right)$ is a maximal
$ST$-pair of $\mathbf{M}_{n,n}$. Dually, we can also suppose that
$S=L_{1}\setminus\left\\{l_{1}\right\\}$ and
$T=\left\\{l_{1},l_{2},y\right\\}$ for some $y\in
L_{2}\setminus\left\\{l_{2}\right\\}$ and the result will also hold. We omit
it from the proof because it uses the same argument.

######  Proof 2.34.

The same argument used in Proposition 2.31 can be applied with $l=l_{1}$,
adjusting only for the fact that $S$ no longer contains the link of $L_{2}$. ∎

####  2.5.4 Theoretical Results 2: No More Pairs.

Having established that all 5 types in Remark 2.20 generalize, we now show
that we have identified all ways of constructing a maximal $ST$-pair of
$\mathbf{M}_{n,n}$. The intuition behind this is that although the number of
elements of $\mathbf{M}_{n,n}$ increases as $n$ does, many of the new triples
are $ST$-breaking antichains since only the links, which are fixed at 2 for
all $n$, may be comparable with the new elements. We begin with the following
lemma, which greatly reduces the subsets of $\mathbf{M}_{n,n}^{*}$ to consider
when choosing $T$. Its proof uses $\mathbb{N}_{n}$ to denote the set of the
first $n$ natural numbers, $\\{1,2,...,n\\}$.

######  Lemma 2.35.

(Restriction on $T$) If $S,T\subseteq\mathbf{M}_{n,n}^{*}$ are disjoint
subsets such that $\mathbf{M}_{n,n}$ is $ST$-distributive, then $T$ cannot
contain four elements, two from each level of $\mathbf{M}_{n,n}$.

######  Proof 2.36.

We show this by contradiction. Suppose that
$T\supseteq\\{a_{i},a_{j},b_{k},b_{l}\\}$ for $i\neq j$ and $k\neq l$. If
$a_{m}\in S$ for any $m\in\mathbb{N}_{n}\setminus\\{i,j\\}$, then
$(a_{m},a_{i},a_{j})$ is an $ST$-breaking antichain, contradicting the
$ST$-distributivity of $\mathbf{M}_{n,n}$. A similar argument works for any
$b_{m}\in S$ distinct from $b_{k}$ and $b_{l}$. This implies that
$S=\emptyset$; contradiction. Therefore,
$T\not\supseteq\\{a_{i},a_{j},b_{k},b_{l}\\}$ for $i\neq j$ and $k\neq l$.

Without further delay, we complete the characterization of maximal $ST$-pairs
of $\mathbf{M}_{n,n}$ in Theorem 2.37. Table 4 provides a formal description
of the 5 types of maximal $ST$-pairs of $\mathbf{M}_{n,n}$ of Remark 2.20,
each with its possible variations. It will be a helpful reference when
following the different cases of the proof of Theorem 2.37.

Type 1 | T-chain
---|---
4 forms | $S$ | $T$ | index restrictions
$\\{a_{1},...,a_{i-1},a_{i+1},...,a_{n},b_{1},...,b_{n}\\}$ | $\\{a_{i}\\}$ | none
$\\{a_{1},...,a_{n},b_{1},...,b_{i-1},b_{i+1},...,b_{n}\\}$ | $\\{b_{i}\\}$ | none
$\\{a_{1},...,a_{i-1},a_{i+1},...,a_{n},b_{2},...,b_{n}\\}$ | $\\{a_{i},b_{1}\\}$ | none
$\\{a_{1},...,a_{n-1},b_{1},...,b_{i-1},b_{i+1},...,b_{n}\\}$ | $\\{a_{n},b_{i}\\}$ | none
Type 2 | S-link
2 forms | $S$ | $T$ | index restrictions
$\\{b_{1}\\}$ | $\\{a_{1},...,a_{n},b_{i}\\}$ | $i\neq 1$
$\\{a_{n}\\}$ | $\\{a_{i},b_{1},...,b_{n}\\}$ | $i\neq n$
Type 3 | S-2-links
1 form | $S$ | $T$ | index restrictions
$\\{a_{n},b_{1}\\}$ | $\\{a_{i},b_{j}\\}$ | $i\neq n,j\neq 1$
Type 4 | S-level
2 forms | $S$ | $T$ | index restrictions
$\\{b_{1},...,b_{n}\\}$ | $\\{a_{i},a_{n}\\}$ | $i\neq n$
$\\{a_{1},...,a_{n}\\}$ | $\\{b_{1},b_{i}\\}$ | $i\neq 1$
Type 5 | S-level-minus-link
2 forms | $S$ | $T$ | index restrictions
$\\{b_{2},...,b_{n}\\}$ | $\\{a_{i},a_{n},b_{1}\\}$ | $i\neq n$
$\\{a_{1},...,a_{n-1}\\}$ | $\\{a_{n},b_{1},b_{i}\\}$ | $i\neq 1$
Table 4: Formal descriptions of the 5 Types of Maximal $ST$-pairs of
$\mathbf{M}_{n,n}$

######  Theorem 2.37.

(Characterization of maximal $ST$-pairs of $\mathbf{M}_{n,n}$) For all
$n\in\mathbb{N}$ such that $n\geq 3$, the maximal $ST$-pairs of
$\mathbf{M}_{n,n}$ all fall into one of the 5 types listed in Remark 2.20 (or
Table 4).

######  Proof 2.38.

We show that if $(S,T)$ is a maximal $ST$-pair of $\mathbf{M}_{n,n}$, then
$(S,T)$ is of one of Types 1-5. Suppose that $(S,T)$ is a a maximal $ST$-pair
of $\mathbf{M}_{n,n}$. If $T$ is a chain, then $(S,T)$ is of Type 1 and we are
done. For the remainder of the proof, we assume that $T$ is not a chain. By
Lemma 2.35, $T$ cannot contain two elements of both levels of
$\mathbf{M}_{n,n}$ at the same time. Hence, there are two cases:

  1. 1.

$T$ is contained in one level: $T\subseteq\\{a_{1},...,a_{n}\\}$ or
$T\subseteq\\{b_{1},...,b_{n}\\}$.

  2. 2.

$T$ is contained in one level except for exactly one element:
$T\subseteq\\{a_{i},b_{1},...,b_{n}\\}$ with $a_{i}\in T$ or
$T\subseteq\\{a_{1},...,a_{n},b_{i}\\}$ with $b_{i}\in T$.

Case 1: $T$ is contained in one level. Consider the case
$T\subseteq\\{a_{1},...,a_{n}\\}$. The case $T\subseteq\\{b_{1},...,b_{n}\\}$
is done similarly. Since $T$ is not a chain, $|T|\geq 2$. That is $T$ contains
$a_{i}$ and $a_{j}$ with $i\neq j$. Then no other $a_{k}$ can be in $S$
because $(a_{k},a_{i},a_{j})$ would be an $ST$-breaking antichain. Thus,
$S\subseteq\\{b_{1},...,b_{n}\\}$. This reduces the problem to determining how
many $a_{i}$’s and $b_{j}$’s can be put in $T$ and $S$ respectively.

To begin, we have $b_{1}\in S$ by MCCD since $b_{1}\geq a_{i}$ for all $i$.
Now, observe that if $T$ contains two non-link and distinct $a_{i}$ and
$a_{j}$, then $S=\\{b_{1}\\}$ because $(b_{k},a_{i},a_{j})$ is an
$ST$-breaking antichain for any $k\neq 1$. This implies that
$T=\\{a_{1},...,a_{n}\\}$ given the maximality of our pair and our assumption
under Case 1. However, this pair is properly contained in a pair of Type 2
contradicting its maximality. Hence, $T$ cannot have two distinct non-link
elements under Case 1.

We are left with the possibility that $|T|=2$ with $a_{n}\in T$. In this case,
we must add all of the $b_{i}$’s to $S$ because $a_{n}\leq b_{i}$ for all $i$
(MCCD). Thus, $S=\\{b_{1},...,b_{n}\\}$ and $T=\\{a_{i},a_{n}\\}$ with $i\neq
n\implies(S,T)$ is a maximal $ST$-pair of Type 4.

Case 2: $T$ is contained in one level except for exactly one element. There
are two cases: (a) $|T|=2$ and (b) $|T|>2$.

_Sub-case 2a_ : If $|T|=2$, then $T=\\{a_{i},b_{j}\\}$. Since $T$ is not a
chain, we must have $i\neq n$ and $j\neq 1$. Hence, $T$ is an antichain of two
elements. This implies that for any non-link $a_{k}$ or $b_{k}$,
$(a_{k},a_{i},b_{j})$ and $(b_{k},a_{i},b_{j})$ is an $ST$-breaking antichain.
Thus, $S\subseteq\\{a_{n},b_{1}\\}$. Given that $a_{n}\leq b_{j}$ and
$b_{1}\geq a_{i}$, the MCCD allows us to add both links to $S$. Thus we have
$S=\\{a_{n},b_{1}\\}$ and $T=\\{a_{i},b_{j}\\}$ with $i\neq n$ and $j\neq
1\implies(S,T)$ is a maximal $ST$-pair of Type 3.

_Sub-case 2b_ : Suppose $|T|>2$. We work with the case that
$T\subseteq\\{a_{i},b_{1},...,b_{n}\\}$ with $a_{i}\in T$. The case
$T\subseteq\\{a_{1},...,a_{n},b_{i}\\}$ with $b_{i}\in T$ is done similarly.
We have that T contains $\\{a_{i},b_{j},b_{k}\\}$ for $j\neq k$ because
$|T|>2$. Then $S$ cannot contain any $b_{l}$’s because $(b_{l},b_{j},b_{k})$
is an $ST$-breaking antichain for any $b_{l}$ distinct from $b_{j}$ and
$b_{k}$. Thus,

$S\subseteq\\{a_{1},...,a_{i-1},a_{i+1},...,a_{n}\\}.$ (29)

Again, we have two cases: (i) $a_{i}$ is a link $(i=n)$ and (ii) $a_{i}$ is a
non-link $(i\neq n)$.

Sub-sub-case 2b-i: If $a_{i}$ is a link ($i=n$), then
$S\subseteq\\{a_{1},...,a_{n-1}\\}$ by (29). Note, however, that for any non-
link $a_{l}$ (i.e. $l\neq n$), $(a_{l},b_{j},b_{k})$ is an $ST$-breaking
antichain if both $b_{j}$ and $b_{k}$ are non-link elements. As a result, $T$
can have at most one non-link $b_{j}$ if we want $S$ to be non-empty. In
addition, $b_{1}$ can be added to $T$ because $b_{1}\geq a_{l}$ (MCCD). We can
also add one non-link $b_{k}$ without affecting the content of $S$ since
$a_{n}\leq b_{k}$ (MCCD). Thus, $T=\\{a_{n},b_{1},b_{k}\\}$ with $k\neq 1$.
Maximality then gives $S=\\{a_{1},...,a_{n-1}\\}$. Therefore, $(S,T)$ is a
maximal $ST$-pair of Type 5.

Sub-sub-case 2b-ii: If $a_{i}$ is a non-link ($i\neq n$), then we know for
sure that $T$ has two non-link elements because it will have at least one
$b_{j}$ with $j\neq 1$ (recall $|T|>2$) and $a_{i}$. Then for any non-link
$a_{l}$ we attempt to place in $S$, $(a_{l},a_{i},b_{j})$ is an $ST$-breaking
antichain. Given (29), the only possible element of $S$ is $a_{n}$. Since
$a_{n}\leq b_{k}$ for all $k$, MCCD implies that $S=\\{a_{n}\\}$. Maximality
forces $T=\\{a_{i},b_{1},...,b_{n}\\}$ with $i\neq n\implies(S,T)$ is a
maximal $ST$-pair of Type 2.

$\therefore(S,T)$ is of Type $m$ for some $m\in\\{1,2,3,4,5\\}$.

####  2.5.5 Combinatorial Corollary.

As a corollary of Theorem 2.37, we can count how many maximal $ST$-pairs
$\mathbf{M}_{n,n}$ has for each $n$. Observe that the 5 types of pairs are all
pairwise disjoint, e.g., it is not possible for a pair to be both a T-chain
pair and an S-link pair. Therefore, we just have to count how many of each
type there are using basic combinatorics and then add them up. We conclude
this section with the proof of this count.

######  Corollary 2.39.

(Count of maximal $ST$-pairs of $\mathbf{M}_{n,n}$) Let $n\geq 3$. Then
$\mathbf{M}_{n,n}$ has $n^{2}+8n-6$ maximal $ST$-pairs which are divided among
the 5 types as follows:

  1. 1.

T-chain: $4n-1$,

  2. 2.

S-link: $2n-2$,

  3. 3.

S-2-links: $n^{2}-2n+1$,

  4. 4.

S-level: $2n-2$,

  5. 5.

S-level-minus-link: $2n-2$.

######  Proof 2.40.

We count how many pairs there are of each type and then sum them up. We point
to Table 4 as a useful reference for following this proof.

T-chain: Since $S$ is completely determined by $T$
($S=\mathbf{M}_{n,n}^{*}\setminus T$), then there is exactly one T-chain pair
for each chain of $\mathbf{M}_{n,n}^{*}$. There are $2n$ size 1 chains, $2n-1$
size 2 chains, and no larger chains. The number of size 1 chains is the number
of elements of $\mathbf{M}_{n,n}^{*}$: $2n$. As for the size 2 chains, note
that they are all of the following two forms: $\\{a_{n},b_{i}\\}$ and
$\\{a_{i},b_{1}\\}$. Each of these forms has $n$ pairs, giving $2n$. However,
we must subtract one because $\\{a_{n},b_{1}\\}$ is counted twice. Adding
these up gives $4n-1$ pairs of type T-chain.

S-link: Note that $S$ consists of only $a_{n}$ or $b_{1}$. Given $S$, $T$
automatically has all of the elements of the level not containing $S$’s link,
but may differ by one non-link element of the level containing $S$’s link.
Hence,

$\displaystyle\\#pairs$ $\displaystyle=(\\#\text{link
choices})(\\#\text{choices of non-link in $T$})$ (30)
$\displaystyle=2\times(n-1)$ (31) $\displaystyle=2n-2.$ (32)

S-2-links: Observe that $S$ is fixed as $\\{a_{n},b_{1}\\}$. Thus, the number
of pairs of this type are determined by the number of ways of choosing $T$.
Since $T$ consists of one non-link $a_{i}$ and one non-link $b_{j}$, we have

$\displaystyle\\#pairs$ $\displaystyle=(\\#\text{non-link choices of
$a_{i}$})(\\#\text{non-link choices of $b_{j}$})$ (33)
$\displaystyle=(n-1)\times(n-1)$ (34) $\displaystyle=n^{2}-2n+1.$ (35)

S-level: Since $S$ is one of the two levels of $\mathbf{M}_{n,n}$, it has two
options. Given $S$, $T$ has two elements from the other level. One of these
must be the link while the other may be any of the non-links. As a result,

$\displaystyle\\#pairs$ $\displaystyle=(\\#\text{levels})(\\#\text{choices for
$T$'s non-link})$ (36) $\displaystyle=2\times(n-1)$ (37) $\displaystyle=2n-2.$
(38)

S-level-minus-link: Observe that each $ST$-pair of the type S-level-minus-link
is obtained from a type $S$-level pair by taking the link element in the $S$
of a type S-level and adding it to its $T$. Therefore, there is a 1-1
correspondence between these pairs and hence $2n-2$ pairs of type S-level-
minus-link.

Total: It remains to add up the totals of pairs of each type. It can be
verified that

$(4n-1)+(2n-2)+(n^{2}-2n+1)+(2n-2)+(2n-2)=n^{2}+8n-6,$ (39)

which is the total amount of pairs initially claimed.

###  2.6 Connection to Distributive Elements

Now that we are done with our main results regarding $ST$-distributive
lattices, we relate said lattices with distributive elements of lattices.
These have a history of changing in meaning. In Garret Birkhoff’s Lattice
Theory [2], they are defined as being synonymous to neutral elements (Chapter
III, Section 9). However, distributive and neutral elements are more recently
defined as two separate concepts, as can be seen in George Grätzer’s Lattice
Theory: Foundation [5] (Chapter III, Section 2). Nevertheless, we will define
a distributive element as in [2] for reasons that will be clarified shortly.
Thus, a distributive element is an element of a lattice with the property that
any three-element subset of the lattice containing it generates a distributive
sublattice.

######  Definition 2.41.

(distributive element) A distributive element of a lattice $L$ is an element
$a\in L$ such that for all $x,y\in L$, $[\\{a,x,y\\}]$ is distributive where
$[\\{a,x,y\\}]$ is the sublattice of $L$ generated by $\\{a,x,y\\}$. The set
of all distributive elements of $L$ is denoted $\mathrm{Distr}\>L$.

We now consider two weaker variations of distributive elements that we will
call meet distributive elements and join distributive elements. These really
are, respectively, dually distributive elements and distributive elements as
defined in [5] in disguise. We renamed them to make their connection to
$ST$-distributivity more apparent. This is also why we define distributive
elements as in [2].

######  Definition 2.42.

(meet distributive element) A meet distributive element of a lattice $L$ is an
element $a\in L$ such that

$a\land(x\lor y)=(a\land x)\lor(a\land y)$ (40)

for all $x,y\in L$. The set of all meet distributive elements of $L$ is
denoted $\mathrm{mDistr}\>L$.

######  Definition 2.43.

(join distributive element) A join distributive element of a lattice $L$ is an
element $a\in L$ such that

$a\lor(x\land y)=(a\lor x)\land(a\lor y)$ (41)

for all $x,y\in L$. The set of all join distributive elements of $L$ is
denoted $\mathrm{jDistr}\>L$.

Note that all elements of a distributive lattice are trivially distributive,
meet distributive, and join distributive. In addition, it is immediate from
Definitions 2.41-2.43 that all distributive elements are meet distributive and
join distributive. We use this fact to give the first non-trivial example of
these three types of elements.

######  Example 2.44.

(lattice identities) The identity elements $0$ and $1$ of any lattice $L$ are
distributive. This is because $[\\{0,x,y\\}]$ is either a chain,
$\mathbf{M}_{2}$, or $\mathbf{1}\oplus\mathbf{M}_{2}$ with dual reasoning for
$[\\{1,x,y\\}]$. This results in $0$ and $1$ both being meet and join
distributive as well.

Next, we make a few additional comments regarding the relationships between
these three types of lattice elements. It follows naturally from their
definitions that meet distributive elements and join distributive elements are
dual concepts. However, they are not equivalent. Furthermore, although all
distributive elements are both meet distributive and join distributive, it is
possible for an element to be both meet distributive and join distributive but
not distributive.

We now give three more examples, two of which will illustrate the relations
just discussed. They involve the lattices $\mathbf{M}_{3}$ and
$\mathbf{N}_{5}$, which we repeat in Figures 12 and 12 for ease of reference.
We omit the computations involved because they are elementary.

######  Example 2.45.

(meet distributive $\centernot\iff$ join distributive) An element that is meet
distributive but not join distributive is $v\in\mathbf{N}_{5}$. By Property
2.2 and idempotency of lattice operations, proving that $v$ is meet
distributive reduces to checking Equation (40) for the case $a=v$, $x=u$, and
$y=w$. On the other hand, to see that it is not join distributive, apply the
same variable assignments in Equation (41). It can be similarly shown that
$u\in\mathbf{N}_{5}$ is join distributive but not meet distributive.

######  Example 2.46.

(meet and join distributive but not distributive) The element $w$ of
$\mathbf{N}_{5}$ is both meet distributive and join distributive but not
distributive. To see that it is both meet and join distributive it suffices to
consider only the cases where $x$ and $y$ are both distinct from each other
and from $w$ in Equations (40) and (41). To see that it is not distributive
note that $[\\{w,u,v\\}]=\mathbf{N}_{5}$.

######  Example 2.47.

(complete non-example) The element $a\in\mathbf{M}_{3}$ is neither meet
distributive nor join distributive. To see this, it is enough to substitute
$a=a$, $x=b$, and $y=c$ in Equations (40) and (41). This also implies that $a$
is not distributive, which can also be verified by observing that
$[\\{a,b,c\\}]=\mathbf{M}_{3}$.

$1$ $a$ $b$ $c$ $0$ Figure 11: The diamond $\mathbf{M}_{3}$

$1$ $u$ $v$ $w$ $0$ Figure 12: The pentagon $\mathbf{N}_{5}$

Finally, we mention the connection between distributive elements and
$ST$-distributive lattices. This is that Definitions 2.41-2.43 provide choices
of $S\subseteq L$ that guarantee $ST$-distributivity for $T=L$. In particular,
we have that any lattice $L$ is

  1. 1.

$(\mathrm{mDistr}\>L)L$-meet distributive,

  2. 2.

$(\mathrm{jDistr}\>L)L$-join distributive,

  3. 3.

$(\mathrm{Distr}\>L)L$-distributive.

###  2.7 Connection to SS-lattices

Before moving on to $ST$-modular lattices, we place our $ST$-distributive
lattices in the context of Stanley’s SS-lattices (see [7]). Our main point is
that SS-lattices provide examples of $ST$-distributive lattices but
$ST$-distributive lattices are more general. First, we recall the definition
of an SS-lattice.

######  Definition 2.48.

(SS-lattice [7]). Consider a lattice $L$ with a maximal chain $\Delta$.
$\left(L,\Delta\right)$ is called a supersolvable lattice (SS-lattice) if for
all chains $K$ of $L$, $\left[\Delta,K\right]$ is distributive. Here,
$\left[\Delta,K\right]$ denotes the sublattice of $L$ generated by $\Delta\cup
K$.

From this definition, we can observe how we can obtain examples of
$ST$-distributive lattices from it: if $\left(L,\Delta\right)$ is an SS-
lattice, then $L$ is $\Delta K$-distributive and $K\Delta$-distributive for
all its chains $K$. On the other hand, $ST$-distributive lattices are a bigger
class because the conditions specified on Definition 2.1 are weaker than those
required for an SS-lattice. First, we let $S$ and $T$ be any subsets of the
initial lattice, not specifically chains. In addition, we only ask that $S$
distributes into $T$ rather than demanding that the generated sublattice
$\left[S,T\right]$ be distributive. This concludes our treatment of
$ST$-distributive lattices.

##  3 $ST$-modular Lattices

This section explores $ST$-modular lattices. As we shall see, these expand the
class of $ST$-distributive lattices. There are two parts to this section.
First, Subsect. 3.1 gives the basic definitions and some examples. Afterwards,
Subsect. 3.2 suggests a potential application to convex sets. In particular,
we will use $ST$-modularity to reprove some classical results on convex
polytopes. We remark that this connection to convexity is the original
motivation for defining $ST$-modular lattices, from which $ST$-distributive
lattices follow by analogy.

###  3.1 Basic Definitions

We now propose a generalization of modular lattices that is analogous to
$ST$-distributive lattices: $ST$-modular lattices. We first define them, then
explain how they relate to $ST$-distributive lattices, and conclude with some
illustrative examples. The reader should observe the parallels between this
subsection and Subsect. 2.1: the first being the similarity between Definition
2.1 and the following definition:

######  Definition 3.1.

($ST$-modular Lattice). Given a lattice $L$ with $S,T\subseteq L$, we define:

  * •

$ST$-meet Modular Lattice: $L$ is said to be $ST$-meet modular if for all
$s\in S$ and $t_{1},t_{2}\in T$,

$s\geq t_{2}\implies s\land\left(t_{1}\lor t_{2}\right)=\left(s\land
t_{1}\right)\lor t_{2}\;.$ (42)

  * •

$ST$-join Modular Lattice: $L$ is said to be $ST$-join modular if for all
$s\in S$ and $t_{1},t_{2}\in T$

$s\leq t_{2}\implies s\lor\left(t_{1}\land t_{2}\right)=\left(s\lor
t_{1}\right)\land t_{2}\;.$ (43)

  * •

$ST$-modular Lattice: $L$ is said to be $ST$-modular if it is both $ST$-meet
modular and $ST$-join modular.

$1$ $a$ $b$ $c$ $d$ $e$ $0$ Figure 13: Lattice $L$ of Examples 3.4, 3.6, and
3.8

We now briefly discuss $ST$-modular lattices. For starters, note how these
generalize modular lattices: $ST$-modular lattices for $S=T=L$. Next, before
giving some concrete examples, we examine the relationship between
$ST$-modular and $ST$-distributive lattices. We establish that
$ST$-distributive lattices are $ST$-modular. This follows directly from the
fact that distributive lattices are modular [2, 3, 5].

######  Proposition 3.2.

($ST$-distributive $\implies$ $ST$-modular). Let $L$ be a lattice with
$S,T\subseteq L$. If $L$ is $ST$-distributive, then $L$ is $ST$-modular

######  Proof 3.3.

Suppose $L$ is $ST$-distributive for $S,T\subseteq L$ with $s\in S$ and
$t_{1},t_{2}\in T$. If $s\geq t_{2}$, then the $ST$-distributivity of $L$ and
the Connecting Lemma [2, 3] imply

$s\land\left(t_{1}\lor t_{2}\right)=\left(s\land t_{1}\right)\lor\left(s\land
t_{2}\right)=\left(s\land t_{1}\right)\lor t_{2}\;.$ (44)

Similarly, if $s\leq t_{2}$,

$s\lor\left(t_{1}\land t_{2}\right)=\left(s\lor t_{1}\right)\land\left(s\lor
t_{2}\right)=\left(s\lor t_{1}\right)\land t_{2}\;.$ (45)

∎

Thus, we have that the $ST$-distributive lattice from Example 2.2 is also an
$ST$-modular lattice. Another $ST$-modular lattice is given in Example 3.4. It
is also a counter-example to the converse of Proposition 3.2. Hence, the class
of $ST$-modular lattices is greater than that of $ST$-distributive ones. This
is consistent with prior knowledge that not all modular lattices are
distributive [2, 3, 5].

######  Example 3.4.

($ST$-modular $\centernot\implies ST$-distributive). Recall the lattice $L$
from Fig. 3, repeated in Fig. 13 for convenience. Consider the subsets
$S=\left\\{b,d\right\\}$ and $T=\left\\{a,c\right\\}$. We claim the $L$ is
$ST$-modular but not $ST$-distributive.

######  Proof 3.5.

$ST$-modular: Note that there is no $s\in S$ and $t\in T$ such that $s\geq t$.
Hence, $L$ is vacuously $ST$-meet modular. To show that it is $ST$-join
modular, we only need to consider when $d\leq a$. This leads to 2 cases where
the necessary equalities hold. Note the use of absorption in the rightmost
equality of the first case.

$\displaystyle d\lor\left(a\land a\right)=d\lor a=a=\left(d\lor a\right)\land
a\qquad\>$ (46) $\displaystyle d\lor\left(c\land a\right)=d\lor e=a=1\land
a=\left(d\lor c\right)\land a\;.$ (47)

Not $ST$-distributive: Note that $b\in S$ and $a,c\in T$ yet,

$b\land\left(a\lor c\right)=b\land 1=b\neq d=d\lor 0=\left(b\land
a\right)\lor\left(b\land c\right)\;.$ (48)

∎

We finish this subsection with two more examples. These illustrate,
respectively, that $ST$-modular lattices behave like $ST$-distributive
lattices when it comes to (a) the distinction between their $ST$-meet and
$ST$-join sub-definitions and (b) the ordered nature of the pair of subsets
$\left(S,T\right)$.

######  Example 3.6.

($ST$-meet Modular $\centernot\iff$ $ST$-join Modular). Examine again the
lattice $L$ from Fig. 13. Consider the subsets $S=\left\\{0,b\right\\}$ and
$T=\left\\{c,d\right\\}$. We claim the $L$ is $ST$-join modular but not
$ST$-meet modular.

######  Proof 3.7.

$ST$-join Modular: Note that $0\leq c$ and $0\leq d$. This leads to 4 cases
that must be verified. It can be seen from Table 5 that all of them the
satisfy the modular law.

Table 5: Computations to show the $L$ is $ST$-join modular in Example 3.6 $0\lor\left(c\land c\right)=c$ |  | $0\lor\left(c\land d\right)=0$
---|---|---
$\left(0\lor c\right)\land c=c$ |  | $\left(0\lor c\right)\land d=0$
$0\lor\left(d\land c\right)=0$ |  | $0\lor\left(d\land d\right)=d$
$\left(0\lor d\right)\land c=0$ |  | $\left(0\lor d\right)\land d=d$

Not $ST$-meet Modular: Observe that although $b\in S$, $c,d\in T$ and $b\geq
d$, we have:

$b\land\left(c\lor d\right)=b\land 1=b\neq d=0\lor d=\left(b\land c\right)\lor
d\;.$ (49)

∎

######  Example 3.8.

($ST$-modular $\centernot\iff$ $TS$-modular). We use the lattice $L$ from Fig.
13 one more time. Consider the subsets $S=\left\\{b,c\right\\}$ and
$T=\left\\{a,d\right\\}$. We claim the $L$ is $ST$-modular but not
$TS$-modular.

######  Proof 3.9.

$ST$-modular: Note that there is no $s\in S$ and $t\in T$ such that $s\leq t$.
Hence, $L$ is vacuously $ST$-join modular. To show that it is $ST$-meet
modular, we only need to consider when $b\geq d$. This leads to 2 cases where
the necessary equalities hold. Note the use of absorption in the rightmost
equality of the first case.

$\displaystyle b\land\left(d\lor d\right)=b\land d=d=\left(b\land d\right)\lor
d\qquad\>$ (50) $\displaystyle b\land\left(a\lor d\right)=b\land a=d=d\lor
d=\left(b\land a\right)\lor d\;.$ (51)

Not $TS$-modular: To see this, note that although $d\in T$, $b,c\in S$, and
$d\leq b$, we have

$d\lor\left(c\land b\right)=d\lor 0=d\neq b=1\land b=\left(d\lor c\right)\land
b\;.$ (52)

∎

###  3.2 Application to Convex Sets

Having defined what is an $ST$-modular lattice, we will take a different route
from that taken with $ST$-distributive lattices. Rather than searching for
$ST$-modular lattices, we will propose an application of this relative modular
property to convex sets. This application is the original motivation for this
concept. For it we will need two ingredients: the lattice of convex sets and a
property of convex hulls in Proposition 3.11. In the following,
$\mathrm{conv}\left(A,B\right)$ denotes the convex hull of $A\cup B$ for two
sets $A$ and $B$.

######  Definition 3.10.

(Lattice of Convex Sets [1]). The lattice of convex sets of $\mathbb{R}^{d}$
is the lattice $\langle L,\lor,\land\rangle$ where $L$ is the set of all
convex sets of $\mathbb{R}^{d}$ with lattice operations

$A\land B=A\cap B\qquad A\lor B=\mathrm{conv}\left(A,B\right)\;.$ (53)

We mention two facts of this lattice: that it is ordered by inclusion
($\subseteq$) and that it can be shown to be non-modular. The latter will make
our proposed relative modularity non-trivial. Now, we present our second
ingredient: a statement regarding the intersection of an affine set with the
convex hull of two convex sets.

######  Proposition 3.11.

(Interesection of Affine Set and Convex Hull [4]). Suppose we have
$A,B,C\subseteq\mathbb{R}^{d}$ with $A$ affine, $B$ and $C$ convex, and
$A\supseteq C$. Then:

$A\cap\mathrm{conv}\left(B,C\right)=\mathrm{conv}\left(A\cap B,C\right)\;.$
(54)

######  Proof 3.12.

The inclusion $\supseteq$ is trivial because
$A\cap\mathrm{conv}\left(B,C\right)$ is convex and contains both $A\cap B$ and
$C=A\cap C$. For the other inclusion ($\subseteq$), let $x\in
A\cap\mathrm{conv}\left(B,C\right)$. Then $x\in\mathrm{conv}\left(B,C\right)$
and since $\mathrm{conv}\left(B,C\right)$ is the union of all line segments
connecting a point in $B$ with a point in $C$, there exist $b\in B$, $c\in C$
and $0\leq\alpha\leq 1$ such that

$x=\left(1-\alpha\right)b+\alpha c\;.$ (55)

If $\alpha=0$, then $x=b\in B$ and given that $x\in A$, $x\in A\cap B$ and we
are done. Similarly, if $\alpha=1$, then $x=c\in C$ and we are done.
Otherwise, solve Eq. (55) for $b$ to get

$b=\frac{1}{1-\alpha}x-\frac{\alpha}{1-\alpha}c\;.$ (56)

It follows that $b\in A$. This due to the fact that $x,c\in A$ (recall
$C\subseteq A$), the sum of their coefficients is 1, and $A$ is affine. This
means that the convex combination presentation in Eq. (55) is a convex
combination of a point in $A\cap B$ and a point in $C$. Therefore,
$x\in\mathrm{conv}\left(A\cap B,C\right)$.∎

We are ready to present our application of $ST$-modularity to convex sets. The
main idea is that we can use our relative modularity to describe certain
behaviors of convex sets. For instance, we can translate Proposition 3.11 into
the language of the lattice of convex sets to get $ST$-meet modularity in said
lattice.

######  Corollary 3.13.

($ST$-meet Modularity in the Lattice of Convex Sets). Let $L$ be the lattice
of convex sets of $\mathbb{R}^{d}$. If $S$ is the set of all affine sets of
$\mathbb{R}^{d}$ and $T=L$, then Proposition 3.11 simply says that $L$ is
$ST$-meet modular. This is because for $A\in S$, $B,C\in T$ with $A\geq C$, it
implies

$A\land\left(B\lor C\right)=\left(A\land B\right)\lor C\;.$ (57)

The relevance of this connection is that this $ST$-meet modularity can be used
to prove classical theorems on convex polytopes. We will provide two examples.
Before doing so, we clarify some definitions and notations that will be used
in the proofs. We define a _convex polytope_ as the convex hull of a finite
set of points in $\mathbb{R}^{d}$ and a _face_ of a convex polytope as the
intersection of the polytope with a supporting hyperplane (following [4]). A
_vertex_ is a 0-dimensional face. Given a hyperplane $H$ in $\mathbb{R}^{d}$,
$H^{+}$ denotes one of the closed halfspaces of $\mathbb{R}^{d}$ that it
defines and $int\left(H^{+}\right)$ its corresponding open halfspace. Finally,
for a finite set of points $\left\\{x_{1},...,x_{n}\right\\}$, we write
$\mathrm{conv}\left(x_{1},...,x_{n}\right)$ as short hand for
$\mathrm{conv}\left(\left\\{x_{1},...,x_{n}\right\\}\right)$.

######  Theorem 3.14.

(Faces of Convex Polytope [4]).

  1. 1.

A convex polytope has a finite number of faces.

  2. 2.

Each face is a convex polytope.

######  Proof 3.15.

We prove Statement 2 first and then derive Statement 1 from it.

Statement 2: Let $P=\mathrm{conv}\left(x_{1},...,x_{n}\right)$ be a convex
polytope and let $F$ be a face of $P$. Then there exists a supporting
hyperplane $H$ of $P$ such that $F=P\cap H$ with $x_{1},...,x_{j}\in F$ and
$x_{j+1},...,x_{n}\in int\left(H^{+}\right)$ for some
$j\in\left\\{1,...,n\right\\}$. Then

$\displaystyle F$ $\displaystyle=H\cap P$ (60)
$\displaystyle=H\cap\mathrm{conv}\left(x_{1},...,x_{n}\right)$
$\displaystyle=H\cap\mathrm{conv}\left(\mathrm{conv}\left(x_{j+1},...,x_{n}\right),\mathrm{conv}\left(x_{1},...,x_{j}\right)\right)\;.$

Since $H$ is affine, $\mathrm{conv}\left(x_{1},...,x_{j}\right)$ and
$\mathrm{conv}\left(x_{j+1},...x_{n}\right)$ are both convex, and
$H\supseteq\mathrm{conv}\left(x_{1},...,x_{j}\right)$, we can rewrite the
right-side expression using Proposition 3.11:

$\displaystyle F$
$\displaystyle=\mathrm{conv}\left(H\cap\mathrm{conv}\left(x_{j+1},...,x_{n}\right),\mathrm{conv}\left(x_{1},...,x_{j}\right)\right)$
(63)
$\displaystyle=\mathrm{conv}\left(\emptyset,\mathrm{conv}\left(x_{1},...,x_{j}\right)\right)$
$\displaystyle=\mathrm{conv}\left(x_{1},...,x_{j}\right)\;.$

Therefore, $F$ is a convex polytope.

Statement 1: Now, observe that we just showed that each face of $P$ is the
convex hull of a subset of $\left\\{x_{1},...,x_{n}\right\\}$, which is a
finite set. Thus, the number of faces of $P$ must be finite. ∎

######  Theorem 3.16.

(Vertices of Convex Polytope [4]). A convex polytope is the convex hull of its
vertices.

######  Proof 3.17.

Let $P=\mathrm{conv}\left(x_{1},...,x_{n}\right)$ be a convex polytope.
Suppose that this convex hull presentation of $P$ is minimal in the sense that

$P\neq\mathrm{conv}\left(x_{1},...,x_{i-1},x_{i+1},...,x_{n}\right)=S_{i}$
(64)

for all $i$ in $1,...,n$. We show that this implies that each $x_{i}$ is a
vertex and hence, $P$ is the convex hull of its vertices.

First, note that by supposition, $x_{i}\not\in S_{i}$. Second, we have that
$S_{i}$ is compact because it is the convex hull of a compact set:
$\left\\{x_{1},...,x_{i-1},x_{i+1},...,x_{n}\right\\}$ Putting these together
we get that $S_{i}$ is a convex and compact set not containing $x_{i}$. This
implies the existence of a hyperplane $H$ passing through $x_{i}$ such that
$S_{i}\subseteq int\left(H^{+}\right)$. We claim that $H$ is an appropriate
hyperplane to establish that $x_{i}$ is a vertex.

We must show that (a) $\left\\{x_{i}\right\\}=H\cap P$ and (b) $P\subseteq
H^{+}$. For the former, observe that

$H\cap P=H\cap\mathrm{conv}\left(S_{i},\left\\{x_{i}\right\\}\right)\;.$ (65)

Since $H$ is affine, $\left\\{x_{i}\right\\}$ and $S_{i}$ are both convex, and
$H\supseteq\left\\{x_{i}\right\\}$, we can rewrite the right-hand side with
Proposition 3.11 to obtain:

$\displaystyle H\cap P$ $\displaystyle=\mathrm{conv}\left(H\cap
S_{i},\left\\{x_{i}\right\\}\right)$ (68)
$\displaystyle=\mathrm{conv}\left(\emptyset,\left\\{x_{i}\right\\}\right)$
$\displaystyle=\left\\{x_{i}\right\\}\;.$

It remains to show that $P$ is contained in $H^{+}$. Note that
$\left\\{x_{i}\right\\}$ and $S_{i}$ are both subsets of $H^{+}$ and that
$P=\mathrm{conv}\left(\left\\{x_{i}\right\\},S_{i}\right)$. Then $P\subseteq
H^{+}$ because halfspaces are convex. Therefore, $x_{i}$ is a vertex of $P$. ∎

The main takeaway from all this is that $ST$-modularity may have applications
to the study of convex sets and polytopes.

##  4 Conclusion

This paper has introduced two new classes of lattices: $ST$-distributive
lattices and $ST$-modular lattices. They extend distributive and modular
lattices with corresponding relative properties satisfied by certain pairs of
subsets of a lattice.

Our main result is the full characterization of the maximal $ST$-pairs (of
disjoint and non-empty subsets that exclude the identity elements) of the
lattice family $\mathbf{M}_{n,n}$ for $n\geq 3$. To this end, we developed an
algorithm that finds all such pairs and applied it $\mathbf{M}_{3,3}$ and
$\mathbf{M}_{4,4}$. We found 27 and 42 maximal $ST$-pairs respectively. We
classified them into 5 types of pairs based on how they are constructed. We
then showed that these constructions generalize to all $\mathbf{M}_{n,n}$ for
$n\geq 3$ (one of them even for all lattices) and that these are the only
constructions possible in this family. Finally, we counted how many pairs of
each type $\mathbf{M}_{n,n}$ has as a function of $n$.

We also established some connection between our proposed classes of lattices
and existing concepts in mathematics. We mentioned how to get
$ST$-distributivity from distributive elements (as defined in [2]) and renamed
two subclasses of these meet and join distributive elements, respectively, to
fit our new definitions. We also discussed how our $ST$-distributive lattices
include and extend Stanley’s $SS$-lattices. Furthermore, we illustrated how
$ST$-modularity can be used to describe properties of convex sets which can
then be used to prove results on convex polytopes.

Needless to say, there is plenty to be done in this new and exciting area of
research. Naturally, we can continue our search for $ST$-distributive lattices
with other families of lattices and also search for $ST$-modular ones. Of
particular interest are cubical lattices (face lattices of hypercubes) and
lattices of cut-complexes of hypercubes. We can also consider restricting our
search to pairs of sublattices. All this can eventually lead to the
development of a general theory of $ST$-distributive and $ST$-modular lattices
with potential connections to other areas of mathematics (e.g. convex sets).
The possibilities are endless!

#### Acknowledgements.

We would like to thank the Math Department at Florida Atlantic University and
the organizers of SEICCGTC 2021 for all their effort in making the first
virtual SEICCGTC possible.

## References

  * [1] Bergman, G.: On lattices of convex sets in $\mathbb{R}^{n}$.  Algebra Universalis 53(2–3), 357–395 (2005).  https://doi.org/10.1007/s00012-005-1934-0
  * [2] Birkhoff, G.: Lattice Theory, 3rd edn.  American Mathematical Society, New York (1940)
  * [3] Davey, B., Priestley, H.: Introduction to Lattices and Order, 2nd edn.  Cambridge University Press., Cambridge, UK (2002)
  * [4] Emamy-K, M.R.: Elements of convex polytopes: An application of projective functionals (2000)
  * [5] Grätzer, G.: Lattice Theory: Foundation, 1st edn.  Springer, Basel (2011).  https://doi.org/10.1007/978-3-0348-0018-1
  * [6] Rival, I.: Maximal sublattices of finite distributive lattices.  Proc. Am. Math. Soc. 37(2), 417–420 (1973).  https://doi.org/10.1090/S0002-9939-1973-0311527-9
  * [7] Stanley, R.: Supersolvable lattices.  Algebra Universalis 2(1), 197–217 (1972).  https://doi.org/10.1007/BF02945028