# Two flags in a semimodular lattice
generate an antimatroid

Koyo Hayashi111Department of Information and System Engineering, Chuo
University, Tokyo 112-8551, Japan<EMAIL_ADDRESS>Hiroshi Hirai222
Department of Mathematical Informatics, Graduate School of Information Science
and Technology, The University of Tokyo, Tokyo, 113-8656, Japan.
<EMAIL_ADDRESS>
###### Abstract

A basic property in a modular lattice is that any two flags generate a
distributive sublattice. It is shown (Abels 1991, Herscovic 1998) that two
flags in a semimodular lattice no longer generate such a good sublattice,
whereas shortest galleries connecting them form a relatively good join-
sublattice. In this note, we sharpen this investigation to establish an
analogue of the two-flag generation theorem for a semimodular lattice. We
consider the notion of a modular convex subset, which is a subset closed under
the join and meet only for modular pairs, and show that the modular convex
hull of two flags in a semimodular lattice of rank $n$ is isomorphic to a
union-closed family on $[n]$. This family uniquely determines an antimatroid,
which coincides with the join-sublattice of shortest galleries of the two
flags.

Keywords: semimodular lattice, antimatroid, Jordan-Hölder permutation, modular
pair

##  1 Introduction

One of the basic and classical results in lattice theory is that any two
maximal chains (flags) in a modular lattice generates a distributive
sublattice:

######  Theorem 1.1 ([4]).

Let $L$ be a modular lattice with a finite rank, and let $C,D$ be flags of
$L$. Then the sublattice generated by $C\cup D$ is a distributive lattice.

The present note addresses an extension of this theorem for a semimodular
lattice. The distributive sublattice in the above theorem can be interpreted
in terms of the graph of all flags, which is obtained by joining two flags
differing on exactly one element. A path in this graph is usually referred to
as a gallery. Abels [1, 2] studied the gallery-distance of two flags in a
semimodular lattice, and showed that for the case of a modular lattice, the
union of all shortest galleries between two flags coincides with the
distributive sublattice generated by them. He also showed that in a
semimodular lattice, the elements in shortest galleries between two flags form
a join-closed subset of the original lattice. This direction was further
addressed by Herscovic [10] in terms of reduced decompositions of the Jordan-
Hölder permutation. He showed that the sublattice generated by two flags in a
semimodular lattice no longer has good properties; it needs not to be ranked
and is not known to be finite. He claims that in a semimodular lattice the
join-closed subset of shortest galleries of two flags is a natural
correspondent for the sublattice of two flags in a modular lattice.

In this note, we sharpen these investigations to establish an analogue of
Theorem 1.1 for a semimodular lattice. The above “generation by two flags” is
meant as repeated additions of join and meet of pairs from the elements in the
flags. We here consider a restricted generation by join and meet only for
modular pairs—pairs of elements satisfying the modularity equality for their
rank. We introduce a modular convex subset as a subset that is closed under
join and meet for modular pairs. The main result in this note is an extension
of Theorem 1.1 in terms of the modular convex hull, which clarifies the above
join-closed subset of two flags and establishes a link to antimatroids.
Specifically, we show that in a semimodular lattice with rank $n$ the modular
convex hull of two flags is isomorphic, as a poset, to a union-closed family
${\cal A}\subseteq 2^{[n]}$ having a (maximal) chain of length $n$. Such a
union-closed family is referred here to as a pre-antimatroid, since it
uniquely determines an antimatroid [6, 7, 11] as the union of all maximal
chains. This construction of an antimatroid from a union-closed family was
implicit in [11]. Its importance was recently recognized by [5, 14] in the
literature of Knowledge Space Theory (KST) [8]. We show that this antimatroid
coincides with the above join-closed subset of shortest galleries between the
two flags.

Various classes of antimatroids and semimodular lattices are known. It would
be an interesting future research to study how they are related via the
modular convex hull of two flags. Our proof is constructive, and will be
useful for such study.

##  2 Preliminaries

A lattice is a partially ordered set $L$ in which every pair $p,q$ of elements
has join $p\vee q$ (the minimum common upper bound) and meet $p\wedge q$ (the
maximum common lower bound). The partial order is denoted by $\leq$. By $p<q$
we mean $p\leq q$ and $p\neq q$. For a pair $p,q$ with $p\leq q$, the interval
$[p,q]$ is defined as the set of elements $z$ with $p\leq z\leq q$. We say
that $q$ covers $p$ if $p\neq q$ and $[p,q]=\\{p,q\\}$. A totally ordered
subset is called a chain, which will be denoted simply as
$p_{1}<p_{2}<\cdots$. The length of a chain is its cardinality minus one. A
subset $S$ of a lattice is said to be join-closed if $p,q\in S\Rightarrow
p\vee q\in S$. (Such a subset is called a subsemilattice in [2] and join-
sublattice in [10].) Two posets $P,Q$ are said to be isomorphic if there is an
order-preserving bijection from $P$ to $Q$. An order-preserving injection from
$P$ to $Q$ is called an embedding.

A lattice $L$ considered in this paper has the maximum element and minimum
element, which are denoted by $1$ and $0$. The rank of an element $p$ is
defined as the maximum length of a chain from $0$ to $p$, and is denoted by
$r(p)$. The rank of the lattice $L$ is defined as the rank of $1$. We only
consider lattices with a finite rank.

For an positive integer $n$, let $[n]:=\\{1,2,\ldots,n\\}$. The family
$2^{[n]}$ of all subsets of $[n]$ is viewed as a (Boolean) lattice by the
inclusion order. A subfamily ${\cal F}\subseteq 2^{[n]}$ is regarded as a
poset with respect to this order.

An (upper-)semimodular lattice is a lattice $L$ satisfying:

  * •

if $a$ covers $a\wedge b$, then $a\vee b$ covers $b$.

It is known [9, Theorem 375] that a semimodular lattice is precisely a lattice
whose rank function $r$ satisfies the semimodularity inequality:

$r(p)+r(q)\geq r(p\wedge q)+r(p\vee q)\quad(p,q\in L).$ (2.1)

A pair $(p,q)$ of elements is said to be modular if it holds $(x\vee p)\wedge
q=x\vee(p\wedge q)$ for every element $x\in L$ with $x\leq q$. In a
semimodular lattice, modular pairs $(p,q)$ are precisely those pairs which
satisfies (2.1) in equality; see [9, Theorem 381]. In particular, a pair
$(p,q)$ is modular if and only if $(q,p)$ is modular (which is called
M-symmetry).

An antimatroid on a finite set $E$ is a family ${\cal A}\subseteq 2^{E}$ of
subsets satisfying the following properties:

  * (A1)

$\emptyset,E\in{\cal A}$.

  * (A2)

For $X,Y\in{\cal A}$, it holds $X\cup Y\in{\cal A}$.

  * (A3)

For a nonempty set $X\in{\cal A}$, there is $e\in X$ such that
$X\setminus\\{e\\}\in{\cal A}$.

See e.g., [3, 11] for antimatroids. An antimatroid is a semimodular lattice
with respect to inclusion order $\subseteq$. Indeed, $X\vee Y$ equals $X\cup
Y$, and $X\wedge Y$ equals the union of all members contained in $X\cap Y$.
The rank is given by the cardinality $X\mapsto|X|$, from which the
semimodularity of the rank follows. It is known [6] that an antimatroid is
precisely a realization of a special semimodular lattice, called a join-
distributive lattice, in $2^{E}$.

We introduce a weaker notion of an antimatroid that determines an antimatroid
uniquely. A pre-antimatroid on a finite set $E$ is a family ${\cal K}\subseteq
2^{E}$ of subsets satisfying (A1), (A2), and

  * (A3′)

There is a (maximal) chain of length $|E|$.

For a pre-antimatroid ${\cal K}$, let ${\cal K}^{*}\subseteq{\cal K}$ be
defined as the union of all chains of length $|E|$.

######  Lemma 2.1 ([5]; see [14]).

Let ${\cal K}$ be a pre-antimatroid. Then ${\cal K}^{*}$ is an antimatroid.

###### Proof.

It suffices to verify that ${\cal K}^{*}$ satisfies the union-closedness (A2).
Indeed, if ${\cal X},{\cal Y}$ are chains of length $|E|$, $X\in{\cal X}$, and
$Y\in{\cal Y}$, then $\\{X^{\prime}\cup Y^{\prime}\mid X^{\prime}\in{\cal
X},Y^{\prime}\in{\cal Y}\\}\subseteq{\cal K}$ contains a chain of length $|E|$
having $X\cup Y$. ∎

Consider the family of all flags in a semimodular lattice of rank $n$, and
endow it with a graph structure as: Two flags $C,D$ are adjacent if and only
if $C\cap D=n-1$. A path in this graph is called a gallery. The flag-distance
$\mathop{\rm dist}(C,D)$ of two flags $C,D$ is the minimum length of a
shortest gallery between $C$ and $D$. It is known [1] that the flag-distance
can be computed from Jordan-Hölder permutation; see Theorem 3.5 below.

##  3 Result

Let $L$ be a semimodular lattice with rank $n$. A subset $S\subseteq L$ is
said to be modular convex if for every modular pair of elements $p,q\in S$ it
holds $p\vee q,p\wedge q\in S$. The modular convex hull of $S$, denoted by
$\mathop{\rm mConv}S$, is defined as the minimal modular convex set containing
$S$. Restricting the partial order of $L$, the modular convex hull
$\mathop{\rm mConv}S$ is regarded as a subposet of $L$. It is clear that in a
modular lattice $\mathop{\rm mConv}S$ is equal to the sublattice generated by
$S$.

The main result of this note clarifies the relationship among the modular
convex hull of two flags, their flag-distance interval, and an antimatroidal
structure.

######  Theorem 3.1.

Let $C,D$ be flags of $L$.

  * (1)

$\mathop{\rm mConv}(C\cup D)$ is isomorphic to a pre-antimatroid ${\cal K}$ on
$[n]$.

  * (2)

A flag $F$ belongs to $\mathop{\rm mConv}(C\cup D)$ if and only if $F$ belongs
to a shortest gallery between $C$ and $D$. In particular, the union of all
flags of all shortest galleries between $C$ and $D$ is isomorphic to the
antimatroid ${\cal K}^{*}$.

We start the proof. Suppose that $C$ and $D$ are given by
$0=c_{0}<c_{1}<\cdots<c_{n}=1$ and $0=d_{0}<d_{1}<\cdots<d_{n}=1$,
respectively. Consider $L^{\prime}:=\\{p\in L\mid p\geq d_{1}\\}$, which is a
semimodular sublattice with rank $n-1$. Define flags $C^{\prime},D^{\prime}$
of $L^{\prime}$ by $C^{\prime}:=C\vee d_{1}=\\{c_{i}\vee
d_{1}\\}_{i=0,1,\ldots,n}$ and $D^{\prime}:=D\vee
d_{1}=\\{d_{i}\\}_{i=1,\ldots,n}$. By semimodularity, $C^{\prime}$ is actually
a flag of $L^{\prime}$. Let $k$ be the maximum index for which $c_{k}\not\geq
d_{1}$. Then $C^{\prime}$ is written as

$d_{1}=c_{0}\vee d_{1}<c_{1}\vee d_{1}<\cdots<c_{k}\vee
d_{1}=c_{k+1}<\cdots<c_{n}=1.$

Define $\Delta\subseteq[0,c_{k}]$ by

$\Delta:=\\{c_{k}\wedge q\mid q\in[d_{1},c_{k+1}]\cap\mathop{\rm
mConv}(C^{\prime}\cup D^{\prime}):\mbox{$(c_{k},q)$ is a modular pair}\\}.$
(3.1)

######  Lemma 3.2.

$\mathop{\rm mConv}(C\cup D)$ equals $\mathop{\rm mConv}(C^{\prime}\cup
D^{\prime})\cup\Delta$, and is join-closed.

###### Proof.

Since $(d_{1},c_{i})$ is a modular pair, it holds
$C^{\prime}\subseteq\mathop{\rm mConv}(C\cup D)$ and $\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})\subseteq\mathop{\rm mConv}({C}\cup{D})$.
By definition (3.1), it holds $\mathop{\rm
mConv}({C}\cup{D})\supseteq\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})\cup\Delta$. Also $(c_{k},c_{i}\vee
d_{1})$ $(0\leq i\leq k)$ is a modular pair with $c_{k}\wedge(c_{i}\vee
d_{1})=c_{i}$. This implies that $\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})\cup\Delta$ contains both ${C}$ and ${D}$.
Therefore we have

$\mathop{\rm mConv}({C}\cup{D})\supseteq\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})\cup\Delta\supseteq{C}\cup{D}.$ (3.2)

We show:

######  Claim.

If $\mathop{\rm mConv}(C^{\prime}\cup D^{\prime})$ is join-closed and modular
convex, then so is $\mathop{\rm mConv}(C^{\prime}\cup D^{\prime})\cup\Delta$.

Then, by (3.2) and induction, we have the statement. Take any
$u,v\in\mathop{\rm mConv}({C}^{\prime}\cup{D}^{\prime})\cup\Delta$. Our goal
is to show $u\vee v\in\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})\cup\Delta$, and $u\wedge v\in\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})\cup\Delta$ if $(u,v)$ is modular.

Case 1: $u\in\mathop{\rm mConv}({C}^{\prime}\cup{D}^{\prime}),v\in\Delta$.
Write $v$ by $v=q\wedge c_{k}$ as in (3.1). Since $q$ covers $v$ (by
modularity), it must hold $q=d_{1}\vee v$. Then $u\vee v=u\vee d_{1}\vee
v=u\vee q$. Therefore, if $\mathop{\rm mConv}({C}^{\prime}\cup{D}^{\prime})$
is join-closed, then $u\vee v\in\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})$. Suppose that $(u,v)$ is a modular pair.
Then $(u,q)$ is also a modular pair. Indeed, $u\wedge q$ covers $u\wedge v$ or
equals $u\wedge v$; the latter is impossible by $u\wedge q\geq d_{1}\not\leq
u\wedge v$. Therefore $u\vee q=u\vee v\in\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})$, and $u\wedge
q\in[d_{1},c_{k+1}]\cap\mathop{\rm mConv}({C}^{\prime}\cup{D}^{\prime})$. Also
$(u\wedge q,c_{k})$ is a modular pair with $u\wedge q\wedge c_{k}=u\wedge v$.
Thus $u\wedge v\in\Delta$.

Case 2: $u,v\in\Delta$. Note that $z\mapsto d_{1}\vee z$ is an embedding from
$\Delta$ to $[d_{1},c_{k+1}]\cap\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})$ such that $c_{k}\wedge(d_{1}\vee z)=z$;
see [9, Lemma 384]. Note that $u\vee d_{1},v\vee
d_{1}\in[d_{1},c_{k+1}]\cap\mathop{\rm mConv}({C}^{\prime}\cup{D}^{\prime})$
with $u=(u\vee d_{1})\wedge c_{k}$ and $v=(v\vee d_{1})\wedge c_{k}$. Suppose
that $\mathop{\rm mConv}({C}^{\prime}\cup{D}^{\prime})$ is join-closed. Then
$(d_{1}\vee u)\vee(d_{1}\vee v)(=d_{1}\vee(u\vee v))$ exists in
$[d_{1},c_{k+1}]\cap\mathop{\rm mConv}(C^{\prime}\cup D^{\prime})$, and
necessarily covers $u\vee v$. Thus $((d_{1}\vee u)\vee(d_{1}\vee v),c_{k})$ is
a modular pair with $((d_{1}\vee u)\vee(d_{1}\vee v))\wedge c_{k}=u\vee
v\in\Delta$. Suppose in addition that $(u,v)$ is a modular pair. Then $(u\vee
d_{1},v\vee d_{1})$ is also modular. From $u\vee d_{1},v\vee
d_{1}\in\mathop{\rm mConv}({C}^{\prime}\cup{D}^{\prime})$, it holds $(u\vee
d_{1})\wedge(v\vee d_{1})$ belongs to $[d_{1},c_{k+1}]\cap\mathop{\rm
mConv}({C}^{\prime}\cup{D}^{\prime})$, and covers $u\wedge v$. This means that
$((u\vee d_{1})\wedge(v\vee d_{1}),c_{k})$ is a modular pair with $(u\vee
d_{1})\wedge(v\vee d_{1})\wedge c_{k}=u\wedge v$, implying $u\wedge
v\in\Delta$. ∎

By using this lemma, we obtain a simple recursive algorithm to construct
$\mathop{\rm mConv}({C}\cup{D})$. This recursive algorithm can be naturally
described by using the notion of the Jordan-Hölder permutation. For $i\in[n]$,
let $\sigma(i)=\sigma_{C,D}(i)$ denote the smallest index $j$ such that
$d_{i}\leq d_{i-1}\vee c_{j}$. The map $i\mapsto\sigma(i)$ is in fact a
bijection on $[n]$, and is called the Jordan-Hölder permutation with respect
to ${C},{D}$ [12, 13]. Observe that the above index $k$ is nothing but
$\sigma(1)-1$.

For $i=1,2,\ldots,n$, let $z_{i},z_{i}^{\prime}$ be elements defined by

$z_{i}^{\prime}:=c_{\sigma(i)}\vee d_{i}(=c_{\sigma(i)}\vee d_{i-1}),\quad
z_{i}:=c_{\sigma(i)-1}\vee d_{i-1}.$ (3.3)

Now $z_{i}$ is the maximal element of ${C}\vee d_{i-1}$ not greater than
$d_{i}$. Therefore, the argument of the above lemma is applicable to two flags
${C}\vee d_{i-1},{D}\vee d_{i-1}$ in $[d_{i-1},1]$, and obtains $\mathop{\rm
mConv}(({C}\vee d_{i-1})\cup({D}\vee d_{i-1}))$ from $\mathop{\rm
mConv}(({C}\vee d_{i})\cup({D}\vee d_{i}))$. Define $M_{i}\subseteq L$
($i=n,n-1,\ldots,1$) by

$\displaystyle M_{n}$ $\displaystyle:=$ $\displaystyle\\{d_{n-1},d_{n}\\},$
(3.4) $\displaystyle M_{i}$ $\displaystyle:=$ $\displaystyle
M_{i+1}\cup\\{q\wedge z_{i}\mid q\in[d_{i},z^{\prime}_{i}]\cap
M_{i+1}:\mbox{$(q,z_{i})$ is a modular pair}\\}.$ (3.5)

######  Corollary 3.3.

$\mathop{\rm mConv}({C}\cup{D})$ is equal to $M_{1}$ and is join-closed.

Define $\varphi:\mathop{\rm mConv}({C}\cup{D})\to 2^{[n]}$ by

$\varphi(u):=\\{i\in[n]\mid z_{i}\geq u\\}.$ (3.6)

######  Lemma 3.4.

The map $\varphi$ is an embedding from $\mathop{\rm mConv}({C}\cup{D})$ to
$2^{[n]}$ such that for $u,v\in\mathop{\rm mConv}({C}\cup{D})$,

  * (1)

$r(u)=n-|\varphi(u)|$, and

  * (2)

$\varphi(u\vee v)=\varphi(u)\cap\varphi(v)$.

###### Proof.

Let $u\in\mathop{\rm mConv}({C}\cup{D})$. Since $M_{1}=\mathop{\rm
mConv}({C}\cup{D})$, $u$ is the meet of a subset of $\\{z_{i}\\}$. Therefore
$u=\bigwedge_{i\in\varphi(u)}z_{i}$, and $\varphi$ is injective. Suppose that
$u\in M_{i}\setminus M_{i+1}$. Then $u=q\wedge z_{i}$ for some
$q\in[d_{i},z_{i}^{\prime}]\cap M_{i+1}$. It is clear that $r(u)=r(q)-1$ and
$\varphi(u)=\varphi(q)\cup\\{z_{i}\\}$ with $z_{i}\not\in\varphi(q)$. By
induction on $i$ from $n$, we have (1), while (2) is obvious from the
definition of $\varphi$. ∎

###### Proof of Theorem 3.1 (1).

Let $\bar{\varphi}:\mathop{\rm mConv}({C}\cup{D})\to 2^{[n]}$ by
$u\mapsto[n]\setminus\varphi(u)$. Then $\mathop{\rm mConv}({C}\cup{D})$ is
isomorphic to the image of $\bar{\varphi}$, which is union-closed (A2) and
contains $\emptyset,[n]$ (A1). By Lemma 3.4 (1), the image of ${C}$ (or $D$)
is a flag required by (A3′). Therefore, the injective image is a pre-
antimatroid. ∎

Next we show Theorem 3.1 (2). We note that the flag-distance $\mathop{\rm
dist}(C,D)$ is computed from Jordan-Hölder permutation $\sigma_{C,D}$. For a
permutation $\sigma$ on $[n]$, the inversion number of $\sigma$ is defined as
the number of pairs $i,j\in[n]$ with $i<j$ and $\sigma(i)>\sigma(j)$.

######  Theorem 3.5 ([1]; see [10]).

For flags $C,D$ in a semimodular lattice, the flag-distance $\mathop{\rm
dist}({C},{D})$ is equal to the inversion number of $\sigma_{{C},{D}}$.

###### Sketch of Proof.

It is clear that the inversion number gives an upper bound of the flag-
distance. In the setting of the proof of Lemma 3.2, the inversion number of
$\sigma_{{C},{D}}$ is $k$ plus the inversion number $\ell$ of
$\sigma_{{C}^{\prime},{D}^{\prime}}$. By induction, ${C}^{\prime}\cup\\{0\\}$
and ${D}$ are connected by a gallery of length $\ell$. Also
${C^{\prime}}\cup\\{0\\}$ and ${C}$ are connected by the gallery of length
$k$, which consists of $k+1$ flags

$0=c_{0}<c_{1}<\cdots c_{i}<c_{i}\vee d_{1}<\cdots<c_{k}\vee
d_{1}=c_{k+1}<\cdots<c_{n}=1$

for $i=0,1,\ldots,k$. ∎

###### Proof of Theorem 3.1 (2).

We first show that any flag in any shortest gallery belongs to $\mathop{\rm
mConv}({C}\cup{D})$. Choose any flag ${D}^{\prime}$ in a shortest gallery such
that it is adjacent to ${D}$. It suffices to show that
${D}^{\prime}\subseteq\mathop{\rm mConv}({C}\cup{D})$. Here ${D}^{\prime}$ is
given by

$0=d_{0}<d_{1}<\cdots<d_{i-1}<d_{i}^{\prime}<d_{i+1}<\cdots<d_{n}=1$

for $d^{\prime}_{i}\neq d_{i}$. By Theorem 3.5, it holds
$j:=\sigma_{{C},{D}}(i)>\sigma_{{C},{D}}(i+1)=:j^{\prime}$, and
$j=\sigma_{{C},{D}^{\prime}}(i+1)$. Then $d_{i+1}\leq d_{i}\vee
c_{j^{\prime}}\leq d_{i}\vee c_{j}$, and $d_{i}\vee c_{j}=d_{i+1}\vee c_{j}$.
Both $d_{i-1}\vee c_{j-1}$ and $d_{i}^{\prime}\vee c_{j-1}$ are covered by
$d_{i+1}\vee c_{j}=d_{i}\vee c_{j}$. Necessarily, they are equal. Now
$d_{i+1}$ and $d_{i-1}\vee c_{j-1}$ form a modular pair such that their meet
is $d^{\prime}_{i}$. Also $\mathop{\rm mConv}({C},{D})$ contains $d_{i-1}\vee
c_{j-1}$ since it is join-closed (Corollary 3.3). This concludes
$d_{i}^{\prime}\in\mathop{\rm mConv}({C},{D})$.

Next we show the conversion direction. Regard $\mathop{\rm mConv}({C}\cup{D})$
as a pre-antimatroid on $[n]$. Then the cardinality $|X|$ for $X\in\mathop{\rm
mConv}({C}\cup{D})$ equals the rank $r(X)$ in $L$. By this fact and the join-
closedness, if $X,Y\in\mathop{\rm mConv}({C}\cup{D})$ are moduler in $L$, then
$X\cup Y,X\cap Y\in\mathop{\rm mConv}({C}\cup{D})$. Therefore, $\mathop{\rm
mConv}({C}\cup{D})$ is a subset of the sublattice generated by $C,D$ in the
Boolean lattice $2^{[n]}$. Abels [2, Proposition 1.8] showed that a flag in
this sublattice is precisely a flag in a shortest gallery between $C$ and $D$
in $2^{[n]}$. On the other hand, the antimatroid ${\cal A}:=(\mathop{\rm
mConv}({C}\cup{D}))^{*}\subseteq 2^{[n]}$ is a semimodular lattice with
respect to the inclusion order, where the join and the rank are the same as in
$L$ and as in $2^{[n]}$. Consequently, the Jordan-Hölder permutation
$\sigma_{{C},{D}}$ in ${\cal A}$ is the same as in $L$ and as in $2^{[n]}$.
Together with Theorem 3.5, we conclude that any flag in $\mathop{\rm
mConv}({C}\cup{D})$ belongs to a shortest gallery in $L$. ∎

## Acknowledgments

The first author was supported by Grant-in-Aid for JSPS Research Fellow, Grant
No. JP19J22605, Japan. The second author was supported by JST PRESTO Grant
Number JPMJPR192A, Japan.

## References

  * [1] H. Abels: The gallery distance of flags. Order 8 (1991), 77–91.
  * [2] H. Abels: The geometry of the chamber system of a semimodular lattice. Order 8 (1991), 143–158.
  * [3] K. Adaricheva and J. B. Nation: Convex geometries. In G. Grätzer and F. Wehrung (eds). Lattice Theory: Special Topics and Applications, Volume 2, Birkhäuser, Cham, Switzerland, 2016, pp. 153–179.
  * [4] G. Birkhoff: Lattice Theory. American Mathematical Society, New York, 1940.
  * [5] J.-P. Doignon: Learning spaces, and how to build them. In Proceeding of 12th International Conference on Formal Concept Analysis (ICFCA’14), Lecture Notes in Computer Science 8478 (2014), pp. 1–14.
  * [6] P. H. Edelman: Meet-distributive lattices and the anti-exchange closure, Algebra Universalis 10 (1980), 290–-299.
  * [7] P. H. Edelman and R. E. Jamison: The theory of convex geometries. Geometricae Dedicata 19 (1985), pp. 247–270.
  * [8] J.-Cl. Falmagne and J.-P. Doignon: Learning Spaces. Springer-Verlag, Berlin, 2011.
  * [9] G. Grätzer: Lattice Theory: Foundation. Birkhäuser, Basel, 2011.
  * [10] D. S. Herscovici: Minimal paths between maximal chains in finite rank semimodular lattices. Journal of Algebraic Combinatorics 7 (1998), 17–37.
  * [11] B. Korte, L. Lovász, and R. Schrader: Greedoids. Springer-Verlag, Berlin, 1991.
  * [12] R. P. Stanley: Supersolvable lattices. Algebra Universalis 2 (1972), 197–217.
  * [13] R. P. Stanley: Finite lattices and Jordan-Hölder sets. Algebra Universalis 4 (1974), 361–371.
  * [14] H. Yoshikawa, H. Hirai and K. Makino: A representation of antimatroids by Horn rules and its application to educational systems. Journal of Mathematical Psychology 77 (2017), 82–93.