CUBO, A Mathematical Journal Vol. 24, no. 03, pp. 369–392, December 2022 DOI: 10.56754/0719-0646.2403.0369 Dual digraphs of finite semidistributive lattices Andrew Craig 1, B Miroslav Haviar 1, 2 José São João 3, 4 1Department of Mathematics and Applied Mathematics, University of Johannesburg, PO Box 524, Auckland Park, 2006, South Africa. acraig@uj.ac.za B 2Department of Mathematics, Faculty of Natural Sciences, M. Bel University, Tajovského 40, 974 01 Banská Bystrica, Slovakia. miroslav.haviar@umb.sk 3Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden. zealvro98@outlook.com 4Department of Mathematics, KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden. ABSTRACT Dual digraphs of finite join-semidistributive lattices, meet-semidistributive lattices and semidistributive lat- tices are characterised. The vertices of the dual digraphs are maximal disjoint filter-ideal pairs of the lattice. The approach used here combines representations of arbitrary lattices due to Urquhart (1978) and Ploščica (1995). The duals of finite lattices are mainly viewed as TiRS digraphs as they were presented and studied in Craig–Gouveia– Haviar (2015 and 2022). When appropriate, Urquhart’s two quasi-orders on the vertices of the dual digraph are also employed. Transitive vertices are introduced and their role in the domination theory of the digraphs is studied. In particular, finite lattices with the property that in their dual TiRS digraphs the transitive vertices form a dominating set (respectively, an in-dominating set) are characterised. A characterisation of both finite meet- and join-semidistributive lattices is provided via minimal closure systems on the set of vertices of their dual digraphs. Accepted: 22 August, 2022 Received: 01 June, 2022 c©2022 A. Craig et al. This open access article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. http://cubo.ufro.cl/ https://doi.org/10.56754/0719-0646.2403.0369 https://orcid.org/0000-0002-4787-3760 https://orcid.org/0000-0002-9721-152X https://orcid.org/0000-0001-5078-362X mailto:acraig@uj.ac.za mailto:miroslav.haviar@umb.sk mailto:zealvro98@outlook.com CUBO, A Mathematical Journal Vol. 24, no. 03, pp. 369–391, December 2022 DOI: 10.56754/0719-0646.2403.0369 RESUMEN Se caracterizan los digrafos duales de reticulados fini- tos unión-semidistributivos, encuentro-semidistributivos y semidistributivos. Los vértices de los digrafos duales son pares filtro-ideales disjuntos maximales del reticu- lado. El enfoque usado combina las representaciones de reticulados arbitrarios de Urquhart (1978) and Ploščica (1995). Los duales de reticulados finitos son vistos prin- cipalmente como digrafos TiRS como fueron presentados y estudiados en Craig–Gouveia–Haviar (2015 y 2022). Cuando sea apropiado, también se emplean los dos cuasi- órdenes de Urquhart en los vértices del digrafo dual. Se introducen los vértices transitivos y se estudia su rol en la teoŕıa de dominación de digrafos. En particular, se carac- terizan los reticulados finitos con la propiedad que en sus digrafos TiRS duales los vértices transitivos forman un conjunto dominante (respectivamente un conjunto do- minante interior). Se entrega una caracterización de re- ticulados encuentro- y unión-semidistributivos a través de sistemas de clausura mı́nima en el conjunto de vértices de sus digrafos duales. Keywords and Phrases: semidistributive lattice, TiRS digraph, join-semidistributive lattice, meet-semidistributive lattice, dual digraph, domination. 2020 AMS Mathematics Subject Classification: 06B15, 06A75, 06D75, 05C20, 05C69. Accepted: 22 August, 2022 Received: 01 June, 2022 c©2022 A. Craig et al. This open access article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. http://cubo.ufro.cl/ https://doi.org/10.56754/0719-0646.2403.0369 CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 371 1 Introduction Semidistributivity was first described by Jónsson [16] while he was studying sublattices of a free lattice. He proved [16, Lemma 2.6] that every free lattice is semidistributive. A lattice is join-semidistributive if it satisfies the following quasi-equation for all x,y,z ∈ L: (SD∨) x ∨ y = x ∨ z =⇒ x ∨ y = x ∨ (y ∧ z). Dually, L is meet-semidistributive if it satisfies: (SD∧) x ∧ y = x ∧ z =⇒ x ∧ y = x ∧ (y ∨ z). A lattice is semidistributive if it satisfies both (SD∨) and (SD∧). For background on semidistributive lattices we refer to the papers by Adaricheva et al. [1] and [2], the chapter by Adaricheva and Nation [3], and the paper by Davey et al. [10]. The aim of our paper is to investigate dual digraphs of finite semidistributive lattices. Theo- rem 3.6 provides a representation of finite semidistributive lattices via a certain class of TiRS digraphs (see Definition 2.4). This theorem is a generalisation of Birkhoff’s representation of finite distributive lattices via finite ordered sets [6] (see comments in the next paragraph regarding the distributive case). In addition, we study transitive vertices in the dual digraphs and their role in the domination theory of the digraphs, and also explore closure systems on the set of vertices of the dual digraphs. We employ representations for finite lattices due to Urquhart [20] and Ploščica [17]. In Urquhart’s representation the elements of the dual space are maximal disjoint filter-ideal pairs of the lattice. Urquhart considered two quasi-orders 61 and 62 on them and studied the dual of the lattice as a certain doubly (quasi-) ordered space. In Ploščica’s representation, the dual space of a lattice L is formed by maximal partial homomorphisms from L into the two-element lattice, which correspond to Urquhart’s maximal disjoint filter-ideal pairs of L. When L is a distributive lattice, these max- imal partial homomorphisms become total homomorphisms from L into the two-element lattice, which form the Priestley dual of L [18]. The close relationship between Ploščica’s representation of general lattices and Priestley’s representation of distributive lattices lies in the single binary re- lation E, which Ploščica considered on his dual space. When L is distributive, E becomes exactly Priestley’s order on the dual space. Ploščica’s dual space of a finite lattice L is therefore a finite digraph where the vertices are the maximal partial homomorphisms from L into the two-element lattice and the binary relation E, which mimics Priestley’s order, forms the edge set of the di- graph. These dual digraphs of lattices were presented and studied as TiRS digraphs in two papers by Craig, Gouveia and Haviar [7, 8]. In our approach we combine Urquhart’s and Ploščica’s representations of finite lattices: the vertices 372 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) of our dual digraphs are maximal disjoint filter-ideal pairs of the lattice in the Urquhart style, but we mainly study them as TiRS digraphs using the Ploščica binary relation E on the vertices. Only in a small part of our investigation do we swap Ploščica’s relation E for Urquhart’s two quasi- orders on the vertices to present our results in a different yet rather satisfactory way (the end of Section 3). In Section 2 we give preliminary results that will prove useful in the subsequent three sections of the paper. In Section 3 we provide several characterisations of the dual digraphs of finite meet- semidistributive, finite join-semidistributive, and finite semidistributive lattices. In Section 4 we introduce transitive vertices in the dual digraphs and we study their role in the domination theory of the digraphs. In particular, we are able to characterise finite lattices having the properties that in their dual TiRS digraphs the transitive vertices form a dominating set, respectively an in-dominating set. In Section 5 we characterise both finite meet-semidistributive and finite join- semidistributive lattices via minimal closure systems on the set of vertices of their dual digraphs. In Section 6 we make some concluding remarks and observations. In particular, we note connections to other representations of finite semidistributive lattices, and we propose several directions for future research in this area. 2 Preliminaries Ploščica’s representation of arbitrary bounded lattices [17] uses the set of maximal partial homo- morphisms (MPHs) from a bounded lattice L to the two-element bounded lattice ({0,1},∧,∨,0,1) as the underlying set of the dual space of L. We recall that a partial homomorphism from a bounded lattice (L,∧,∨,0,1) into the two-element bounded lattice ({0,1},∧,∨,0,1) is a partial map f : L → {0,1} such that domf is a bounded sublattice of L and the restriction f↾dom f is a bounded lattice homomorphism. A maximal partial homomorphism is a partial homomorphism with no proper extension. The set of MPHs is then equipped with a binary relation and a topology. Definition 2.1 ([20, Section 3]). Let L be a lattice. Then 〈F,I〉 is a disjoint filter-ideal pair of L if F is a filter of L and I is an ideal of L such that F ∩ I = ∅. We say that a disjoint filter-ideal pair 〈F,I〉 is maximal if there is no disjoint filter-ideal pair 〈G,J〉 6= 〈F,I〉 such that F ⊆ G and I ⊆ J. A maximal disjoint filter-ideal pair 〈F,I〉 of L is total in L if F ∪ I = L. There is a one-to-one correspondence between the set of MPHs from L to 2 = ({0,1},∧,∨,0,1) and the maximal disjoint filter-ideal pairs (MDFIPs) of L. The latter were used in the dual representation of Urquhart [20]. We will use a combination of the two approaches: for a lattice L, the elements of our dual set XL will be MDFIPs, but we will equip the set with the binary relation due to Ploščica, and hence will obtain a digraph. (Later, when desirable, we will also equip the CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 373 set XL of all MDFIPs of L with Urquhart’s two quasi-orders 61 and 62.) We do not require the topologies used by Ploščica and Urquhart because we are only working with finite lattices. Ploščica’s binary relation on the set of MPHs is defined as follows for MPHs f and g from L to 2: (E1) fEg ⇐⇒ (∀x ∈ domf ∩ domg)(f(x) 6 g(x)). The digraph dual to a finite bounded lattice L in Ploščica’s representation is GL = (VL,E) where the set of vertices VL is formed by all MPHs from L to 2 and the relation E is defined by (E1) above. We will now present this dual digraph as GL = (XL,E) where the set of vertices will be XL, i.e. is formed by all MDFIPs of L, and the corresponding Ploščica relation E will be defined below by (E2). For two MDFIPs 〈F,I〉 and 〈G,J〉, Ploščica’s relation E is determined as follows: (E2) 〈F,I〉E〈G,J〉 ⇐⇒ F ∩ J = ∅. For finite lattices every filter is the up-set of a unique element and every ideal is the down-set of a unique element, so we can represent every disjoint filter-ideal pair 〈F,I〉 by an ordered pair 〈↑x,↓y〉 where x = ∧ F and y = ∨ I. Hence for finite lattices we have 〈↑x,↓y〉E〈↑a,↓b〉 if and only if x b. In Figure 1 we present a number of examples of finite (non-distributive) lattices and their dual digraphs. To make the labelling more compact, we denote by xy the MDFIP 〈↑x,↓y〉. Also, to keep the display simpler, we have not included the loop on each vertex. Notice that the directed edge set is not a transitive relation. SD∨, not SD∧ 0 a b c d e 1 a b c d e SD∧, not SD∨ 0 1 0 a b c 1 SD∨ & SD∧ 1 a b c 0 1 Not SD∨, not SD∧ ea dc de cb dc ab cb ea ab bc ca ab ac ba bc ca cb Figure 1: Some finite lattices and their dual digraphs. The fact below was noted by Urquhart and will be useful later. 374 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) Proposition 2.2 ([20, p. 52]). Let L be a finite lattice. If 〈F,I〉 is a maximal disjoint ideal-filter pair of L then ∧ F is join-irreducible and ∨ I is meet-irreducible. Some of what appears in the proposition below can be found in the paper by Gaskill and Nation [13, p. 353]. We will make frequent use of this result and its proof reveals some important features of MDFIPs. Proposition 2.3. Let L be a finite lattice and 〈F,I〉 be a maximal disjoint filter-ideal pair of L. Then the following are equivalent: (i) ∧ F is join-prime; (ii) ∨ I is meet-prime; (iii) F ∪ I = L; (iv) F is a prime filter; (v) I is a prime ideal. The equivalences (iii) ⇔ (iv) ⇔ (v) hold even when L is not finite. Proof. Let L be a finite lattice and let 〈F,I〉 be a maximal disjoint filter-ideal pair of L. Let ∧ F = x and ∨ I = y. First we show that (iii) ⇒ (i). Assume that F ∪I = L. Let a,b ∈ L such that x 6 a∨b. We claim that a ∈ F or b ∈ F . Suppose for a contradiction that a /∈ F and b /∈ F . Then a,b ∈ L \ F = I. That implies a ∨ b ∈ I, whence x ∈ I, a contradiction. Now we show that (i) ⇒ (iii). Assume that x is join-prime. Let a ∈ L such that a /∈ F ∪ I. We will consider three cases for the element a ∨ y and derive a contradiction for each case. Case 1: If a ∨ y ∈ I then a 6 a ∨ y = y, thus a ∈ I, a contradiction. Case 2: If a ∨ y ∈ F then x 6 a ∨ y. Since x is join-prime, x 6 a or x 6 y. If x 6 a then a ∈ F , contradicting a /∈ F ∪ I. If x 6 y then x ∈ I, contradicting F ∩ I = ∅. Case 3: Suppose a∨y /∈ F ∪I. Since a∨y /∈ ↑x, ↓(a∨y)∩↑x = ∅. From a∨y /∈ ↓y it follows that ↓y ⊂ ↓(a ∨ y). Hence 〈↑x,↓(a ∨ y)〉 is a disjoint filter-ideal pair properly containing 〈F,I〉, which contradicts the maximality of 〈F,I〉. The equivalence of (ii) and (iii) can be shown analogously. Now we drop the assumption that L is finite and show that (iii) ⇒ (iv). Let a ∨ b ∈ F . If a /∈ F and b /∈ F then we have a,b ∈ L\F = I. Since I is an ideal we would get a∨b ∈ I, a contradiction. Therefore a ∈ F or b ∈ F . CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 375 To show (iv) ⇒ (iii), and the equivalence of (iv) and (v), one uses the fact that a filter F ⊆ L is prime if and only if L\F is a prime ideal. The properties of the digraphs dual to bounded lattices were described by Craig, Gouveia and Haviar [7]. There they were called TiRS graphs; in this paper we will use the terminology TiRS digraphs. We recall the necessary facts. (We note that in the definition below xE = { y ∈ V | (x,y) ∈ E } and Ex = { y ∈ V | (y,x) ∈ E }.) Definition 2.4 ([7, Definition 2.2]). A TiRS digraph G = (V,E) is a set V and a reflexive relation E ⊆ V × V such that: (S) If x,y ∈ V and x 6= y then xE 6= yE or Ex 6= Ey. (R) For all x,y ∈ V , if xE ⊂ yE then (x,y) /∈ E, and if Ey ⊂ Ex then (x,y) /∈ E. (Ti) For all x,y ∈ V , if xEy then there exists z ∈ V such that zE ⊆ xE and Ez ⊆ Ey. We recall that the vertices of the dual digraph GL of a bounded lattice L are formed by the set XL of MDFIPs of L and Ploščica’s relation E is determined by (E2). Using these facts, the following result can be stated. Proposition 2.5 ([7, Proposition 2.3]). For any bounded lattice L, its dual digraph GL = (XL,E) is a TiRS digraph. We recall from [17] a fact concerning general digraphs G = (X,E). Let 2∼ = ({0,1},6) denote the two-element digraph. A partial map ϕ: X → 2∼ is said to preserve the relation E if ϕ(x) 6 ϕ(y) whenever x,y ∈ domϕ and (x,y) ∈ E. The lattice of maximal partial E-preserving maps from G to 2∼ is denoted by G mp(G, 2∼). Lemma 2.6 ([17, Lemma 1.3]). Let G = (X,E) be a digraph and let us consider ϕ ∈ Gmp(G, 2∼). Then (i) ϕ−1(0) = { x ∈ X | there is no y ∈ ϕ−1(1) with (y,x) ∈ E }; (ii) ϕ−1(1) = { x ∈ X | there is no y ∈ ϕ−1(0) with (x,y) ∈ E }. The above lemma allows us to observe that for a digraph G = (X,E) and ϕ,ψ ∈ Gmp(G, 2∼) we have ϕ−1(1) ⊆ ψ−1(1) ⇐⇒ ψ−1(0) ⊆ ϕ−1(0). This implies that the reflexive and transitive binary relation 6 defined on Gmp(G, 2∼) by ϕ 6 ψ ⇐⇒ ϕ−1(1) ⊆ ψ−1(1) is a partial order. For a digraph G = (X,E) we let C(G) = (Gmp(G, 2∼),6). 376 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) Theorem 2.7 ([7, Theorem 1.7 and p. 87]). For any finite bounded lattice L we have that L is isomorphic to C(GL) and for any finite TiRS digraph G = (V,E) we have that G is isomorphic to GC(G). In later sections, we will frequently make use of Theorem 2.7 in the following way: given any finite TiRS digraph G = (V,E), we can consider G to be the dual digraph GL = (XL,E) for some finite lattice L. There are a number of different constructions that yield complete lattices isomorphic to the com- plete lattice C(G) described above, which is assigned to a digraph G = (X,E) (see [9]). In particular, later we will use the lattice obtained via the polarity K(G) = (X,X,E∁), which will be described in Section 5. At the end of this preliminary section we recall from [20] how the set XL of all MDFIPs of a finite bounded lattice L can be equipped with two quasi-orders 61 and 62. Urquhart in [20, p. 47] defined two binary relations 61 and 62 on the set set XL of all MDFIPs of an arbitrary lattice L as follows: for two MDFIPs 〈F,I〉 and 〈G,J〉, (61) 〈F,I〉 61 〈G,J〉 ⇐⇒ F ⊆ G; (62) 〈F,I〉 62 〈G,J〉 ⇐⇒ I ⊆ J. It is clear that the binary relations 61 and 62 are reflexive and transitive on the set XL, and hence are quasi-orders. 3 Characterisation of dual digraphs The theorem below will play a crucial role in the proof of our first result. Our presentation is slightly different to [3]; we have re-stated their items to suit our purposes. We use J(L), respectively M(L), to denote the join-irreducible, respectively meet-irreducible, elements of L. Theorem 3.1 ([3, Theorem 3-1.4]). Let L be a finite lattice. Then the following are equivalent: (i) L satisfies SD∨; (ii) For each x ∈ M(L), there exists a unique minimal element of the set S(x) = {k ∈ L | k x & k 6 x∗}, where x∗ is the unique upper cover of x, and moreover, this minimal element of S(x) is in J(L). CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 377 (iii) There exists a map κ: M(L) → J(L) such that for each x ∈ M(L), κ(x) is the minimal element of the set S(x). Using the previous result, in the next theorem we characterise finite join-semidistributive and meet-semidistributive lattices via their MDFIPs. Theorem 3.2. Let L be a finite lattice. (i) L is not join-semidistributive if and only if there exist distinct maximal disjoint filter-ideal pairs of the form 〈↑y,↓x〉 and 〈↑z,↓x〉 for some x,y,z ∈ L. (ii) L is not meet-semidistributive if and only if there exist distinct maximal disjoint filter-ideal pairs of the form 〈↑x,↓y〉 and 〈↑x,↓z〉 for some x,y,z ∈ L. Proof. For the necessity, assume L is not join-semidistributive, whence by Theorem 3.1, for some x ∈ M(L) there exist two minimal elements y and z of the set S(x). Then ↑y ∩ ↓x = ∅ and ↑z ∩ ↓x = ∅ so 〈↑y,↓x〉 and 〈↑z,↓x〉 are disjoint filter-ideal pairs. We claim that 〈↑y,↓x〉 and 〈↑z,↓x〉 are maximal. Suppose on the contrary that there is a disjoint filter-ideal pair 〈↑a,↓b〉 of L such that ↑y ⊆ ↑a and ↓x ⊆ ↓b but 〈↑a,↓b〉 6= 〈↑y,↓x〉. This gives us two possible cases: Case 1: If a 6= y then since y is minimal in the set S(x) and a 6 y 6 x∗ we have that a 6 x. But x 6 b, which implies that a 6 b, contradicting ↑a ∩ ↓b = ∅. Case 2: If b 6= x then x∗ 6 b since x∗ is the unique upper cover of x. But a 6 y 6 x∗, which implies that a 6 b, contradicting again ↑a ∩ ↓b = ∅. Thus 〈↑y,↓x〉 is maximal and we can use a similar argument to prove that 〈↑z,↓x〉 is maximal. For the sufficiency, assume that there exist distinct maximal disjoint filter-ideal pairs of the form 〈↑y,↓x〉 and 〈↑z,↓x〉 for some x,y,z ∈ L. We will prove that y and z are both minimal elements of the set S(x). If follows from ↑y ∩ ↓x = ∅ and ↑z ∩ ↓x = ∅ that y x and z x. We will argue y 6 x∗ by contradiction. Suppose y x∗, then ↑y ∩ ↓x∗ = ∅. Since x < x∗ implies that ↓x ⊂ ↓x∗, we get that 〈↑y,↓x〉 is properly contained in 〈↑y,↓x∗〉, which is a contradiction. Therefore y 6 x∗ and y ∈ S(x). Using a similar argument, z ∈ S(x). Now if a ∈ S(x) and a < y, then ↑y ⊂ ↑a. Since a x, we have ↑a ∩ ↓x = ∅. Therefore 〈↑a,↓x〉 is a disjoint filter-ideal pair with ↑y ⊂ ↑a, contradicting the maximality of 〈↑y,↓x〉. Similarly, if b ∈ S(x) such that b < z, then 〈↑b,↓x〉 is a disjoint filter-ideal pair properly containing 〈↑z,↓x〉, which is a contradiction. Therefore y and z are both minimal elements of S(x). The proof of (ii) follows by an order-dual argument. 378 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) Corollary 3.3. Let G = (V,E) be a finite TiRS digraph which is the dual digraph of a finite lattice L. If the relation E is antisymmetric, then L is semidistributive. Proof. In accordance with our remarks after Theorem 2.7, we can consider G to be GL and so its vertex set V will be XL. Suppose for a contradiction that L is not semidistributive. Then L is not join-semidistributive or L is not meet-semidistributive. If L is not join-semidistributive then by Theorem 3.2 (i) there are maximal disjoint filter-ideal pairs of the form 〈↑y,↓x〉 and 〈↑z,↓x〉 for some x,y,z ∈ L. Since G is the dual digraph of L, we have 〈↑y,↓x〉,〈↑z,↓x〉 ∈ V . Clearly 〈↑y,↓x〉E〈↑z,↓x〉 and 〈↑z,↓x〉E〈↑y,↓x〉. This contradicts the antisymmetry of the relation E. If L is not meet-semidistributive, then the argument is analogous. Remark 3.4. The converse to Corollary 3.3 does not hold. We can see it on the lattice in Figure 2. 0 a c b d 1 ac bd cb da Figure 2: A finite semidistributive lattice and its dual digraph. The lattice is semidistributive but we see on its dual digraph, which contains a “double arrow” between the elements ac and bd, that the relation E of the digraph is not antisymmetric. Hence the condition in Corollary 3.3 is sufficient but not necessary for a finite lattice to be semidis- tributive. An interesting task that is left open is to possibly weaken the given sufficient condition to some form of “weak antisymmetry” of the relation E so that the resulting condition on E is necessary and sufficient for a finite lattice to be semidistributive. In the statement and the proof of the following result we again use the fact that, by Theorem 2.7, G = (V,E) is isomorphic to the dual digraph GL = (XL,EL) of the lattice L, whose vertex set XL is the set of all MDFIPs of L. Lemma 3.5. Let G = (V,E) be a finite TiRS digraph with dual lattice L. Let u,v ∈ V be distinct. Then: (i) Eu = Ev if and only if u and v are the isomorphic images of 〈↑x,↓y〉 and 〈↑z,↓y〉 in XL for some x,y,z ∈ L; CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 379 (ii) uE = vE if and only if u and v are the isomorphic images of 〈↑x,↓y〉 and 〈↑x,↓z〉 in XL for some x,y,z ∈ L. Proof. Let u,v ∈ V . To show the sufficiency of the condition in (i), let u and v be the isomorphic images of the vertices 〈↑x,↓y〉 and 〈↑z,↓y〉 in GL for some x,y,z ∈ L. Since G is isomorphic to GL, we only need to show that EL〈↑x,↓y〉 = EL〈↑z,↓y〉. To this end, let 〈F,I〉 ∈ EL〈↑x,↓y〉, then F ∩ ↓y = ∅. Thus 〈F,I〉 ∈ EL〈↑z,↓y〉. Similarly, if 〈F,I〉 ∈ EL〈↑z,↓y〉, then F ∩ ↓y = ∅ and 〈F,I〉 ∈ EL〈↑x,↓y〉. Therefore EL〈↑x,↓y〉 = EL〈↑z,↓y〉 and Eu = Ev. For the necessity of the condition in (i), let 〈↑x,↓y〉 and 〈↑z,↓w〉 be isomorphic images of u and v in XL and let Eu = Ev. We will show ↓y = ↓w. Let a ∈ ↓y. For all 〈F,I〉 ∈ EL〈↑z,↓w〉 we have F ∩ ↓y = ∅ since EL〈↑x,↓y〉 = EL〈↑z,↓w〉. For S = ⋃ {F | 〈F,I〉 ∈ EL〈↑z,↓w〉} now a /∈ S as a ∈ ↓y. We claim that a ∈ ↓w. Suppose on the contrary that a /∈ ↓w. Then a w and ↑a ∩ ↓w = ∅. This shows 〈↑a,↓w〉 is a disjoint filter-ideal pair. Hence there is an MDFIP 〈H,J〉 such that ↑a ⊆ H and ↓w ⊆ J. But ↓w ⊆ J and H ∩ J = ∅ implies that H ∩ ↓w = ∅. Then 〈H,J〉 ∈ EL〈↑z,↓w〉, so H ⊆ S, which means a ∈ S, a contradiction. Thus a ∈ ↓w. The reverse inclusion can be shown analogously. Therefore ↓y = ↓w and the proof of (i) is complete. Part (ii) can be proven analogously. Theorem 3.6. Let G = (V,E) be a finite TiRS digraph with u,v ∈ V . Then (i) G is the dual digraph of a join-semidistributive lattice if and only if whenever u 6= v then Eu 6= Ev. (ii) G is the dual digraph of a meet-semidistributive lattice if and only if whenever u 6= v then uE 6= vE. (iii) G is the dual digraph of a semidistributive lattice if and only if whenever u 6= v then Eu 6= Ev and uE 6= vE. Proof. Let G be a finite TiRS digraph with dual lattice L. To show the necessity in (i), assume there exist distinct u,v ∈ V such that Eu = Ev. Then by Lemma 3.5 there exist distinct MDFIPs 〈↑x,↓y〉 and 〈↑z,↓y〉 in L. It then follows from Theorem 3.2(i) that L is not join-semidistributive. To show the sufficiency in (i), assume that L is not join-semidistributive. Then by Theorem 3.2(i) there exist distinct MDFIPs 〈↑x,↓y〉 and 〈↑z,↓y〉. By Lemma 3.5 there exist distinct vertices u,v ∈ V such that Eu = Ev. Part (ii) can be shown analogously, and part (iii) follows directly from (i) and (ii). We recall that the “separation property” (S) in the definition of TiRS digraphs is defined as follows: (S) If x,y ∈ V and x 6= y then xE 6= yE or Ex 6= Ey. 380 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) Hence it should be emphasized that the condition (iii) in the theorem above characterising the semidistributivity is clearly strengthening the separation condition (S) by replacing in it the logical connective “or” with “and”. Thus it can be considered as a certain “strong separation property”: (sS) If x,y ∈ V and x 6= y then xE 6= yE and Ex 6= Ey. It is interesting to realise that finite semidistributive lattices are exactly those finite lattices whose dual digraphs have the “separation property” (S) strengthened to the “strong separation property” (sS). A remark of Urquhart [20, Section 7] says that a finite lattice L is meet-semidistributive if and only if the quasi-order 61 is an order. We state that result (and its dual) below and prove it using the results from earlier in the section. Theorem 3.7. Let L be a finite lattice. (i) L is join-semidistributive if and only if the quasi-order 62 on the vertices of the dual digraph is an order. (ii) L is meet-semidistributive if and only if the quasi-order 61 on the vertices of the dual digraph is an order. Proof. Assume firstly that the quasi-order 62 on the vertices of the dual digraph is not an order, that is, the relation 62 is not antisymmetric. Then there exist distinct vertices x and y such that x 62 y and y 62 x. If we consider the vertices x and y as the MDFIPs x = 〈F,I〉 and y = 〈G,J〉, then by definition of 62 we have I ⊆ J and J ⊆ I, hence the MDFIPs x and y have the same ideal part. By Theorem 3.2 it follows that L is not join-semidistributive. Conversely, if L is not join-semidistributive, then by Theorem 3.2 there exist distinct MDFIPs x and y with the same ideal part, whence x 62 y and y 62 x. It follows that the relation 62 is not antisymmetric, hence the quasi-order 62 is not an order. Now we can rephrase Lemma 3.5 in terms of quasi-orders 61 and 62: Corollary 3.8. Let G = (V,E) be a finite TiRS digraph with dual lattice L. Let u,v ∈ V be distinct. Then: (i) Eu = Ev if and only if u 62 v and v 62 u; (ii) uE = vE if and only if u 61 v and v 61 u. We can finally summarise the previous results in the following characterisations of join-semidistribu- tivity, meet-semidistributivity and semidistributivity of finite lattices via the properties of their dual digraphs: CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 381 Corollary 3.9. Let G = (V,E) be a finite TiRS digraph. (1) The following are equivalent: (i) G is the dual digraph of a join-semidistributive lattice; (ii) for all u,v ∈ V , if u 6= v then Eu 6= Ev; (iii) the quasi-order 62 on V is an order. (2) The following are equivalent: (i) G is the dual digraph of a meet-semidistributive lattice; (ii) for all u,v ∈ V , if u 6= v then uE 6= vE; (iii) the quasi-order 61 on V is an order. (3) The following are equivalent: (i) G is the dual digraph of a semidistributive lattice; (ii) for all u,v ∈ V , if u 6= v then Eu 6= Ev and uE 6= vE; (iii) both the quasi-orders 61 and 62 on V are orders. 4 Domination in dual digraphs In the dual digraph of a lattice L, there are certain vertices that play an important role. It turns out that these vertices correspond to MDFIPs where F ∪ I = L. Definition 4.1. A vertex v of a digraph G = (V,E) is said to be transitive in G if uEv and vEw imply uEw for all u,w ∈ V . With respect to the illustration of the following result, the reader is reminded to return to Figure 1 for examples. Theorem 4.2. Let L be a lattice with dual digraph GL = (XL,E). A maximal disjoint filter-ideal pair 〈F,I〉 is total in L if and only if it is transitive in GL. Proof. Let 〈F,I〉 be total in L. Assume that 〈G,J〉 and 〈H,K〉 are maximal disjoint filter-ideal pairs such that 〈G,J〉E〈F,I〉 and 〈F,I〉E〈H,K〉. By the definition of E we have that G ∩ I = ∅ and F ∩ K = ∅. We claim that G ∩ K = ∅. Notice that since F ∩ K = ∅ and 〈F,I〉 is total, it follows that K ⊆ L\F = I. But G ∩ I = ∅ and hence G ∩ K = ∅. By the definition of E we get 〈G,J〉E〈H,K〉 and therefore 〈F,I〉 is transitive. 382 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) For the converse, assume that 〈F,I〉 is not total in L. Take x ∈ L\(F ∪I) and consider the disjoint filter-ideal pairs 〈↑x,I〉 and 〈F,↓x〉. These can be extended to maximal disjoint filter-ideal pairs 〈G,J〉 (where ↑x ⊆ G and I ⊆ J) and 〈H,K〉 (with F ⊆ H and ↓x ⊆ K). Since I ⊆ J, we have G ∩ I = ∅ and hence 〈G,J〉E〈F,I〉. Since F ⊆ H we get F ∩ K = ∅ and hence 〈F,I〉E〈H,K〉. But, since x ∈ G ∩ K we do not have 〈G,J〉E〈H,K〉 and so 〈F,I〉 is not transitive. The following result was first shown in a more restricted context by Gaskill and Nation [13]. This more general statement is folklore. Proposition 4.3 ([13, Lemma 1]). Let L be a join-semidistributive lattice with greatest element 1. Then L has a prime ideal. Dually, if L is a meet-semidistributive lattice with least element 0, then L has a prime filter. Proof. Let I be an ideal that is maximal with respect to not containing 1. Suppose that y,z /∈ I. Then there is an element x ∈ I such that x ∨ y = x ∨ z = 1. Since L satisfies SD∨ we get x ∨ (y ∧ z) = 1 and hence y ∧ z /∈ I. Corollary 4.4. Let L be a bounded lattice. If the dual digraph GL = (XL,E) does not have a transitive vertex then L satisfies neither SD∨ nor SD∧. Proof. Assume that GL does not have a transitive element. Then every MDFIP of L is such that F ∪ I 6= L. By Proposition 2.3 we have that no filter F ⊆ L can be prime. Since L has both a greatest and least element, by Proposition 4.3, L cannot be join-semidistributive and it cannot be meet-semidistributive. Notice that the converse of Corollary 4.4 does not hold. The lattice L3 from [10] satisfies neither SD∨ nor SD∧ but there exists a maximal disjoint filter-ideal pair 〈F,I〉 with F ∪ I = L (or, a total homomorphism from L3 to 2). As stated earlier, the transitive elements in a finite TiRS digraph can play a special role. Notice that when a TiRS digraph G is a poset (i.e. it is the dual digraph of a finite distributive lattice) then every element of G is transitive. The next lemma captures two familiar facts about finite join-semidistributive and meet-semidistribu- tive lattices. Lemma 4.5 ([13, Lemma 1]). (i) The co-atoms of a finite join-semidistributive lattice are meet- prime. (ii) The atoms of a finite meet-semidistributive lattice are join-prime. Proof. We prove only (i) as the proof of (ii) will follow using a dual argument. CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 383 Let L be a finite join-semidistributive lattice and let x ∈ L be a co-atom such that x > a ∧ b for some a,b ∈ L. Suppose that x � a and x � b. We then have x ∨ a > x and x ∨ b > x. Since x is a co-atom, we get x ∨ a = 1 = x ∨ b. However, since L is join-semidistributive, we get x = x ∨ (a ∧ b) = x ∨ a = 1, a contradiction. Thus x > a or x > b. In the definition below we note that the original source uses ‘arc’ instead of ‘edge’. Definition 4.6 ([15, Definition 2]). Given a digraph D = (V,E), with vertex set V and edge set E, a set S ⊆ V is a dominating set if for every vertex v ∈ V \S, there is a vertex u ∈ S such that uEv. Proposition 4.7. Let G = (V,E) be a finite TiRS digraph. If G is dual to a finite join-semidis- tributive lattice L, then the transitive vertices of G form a dominating set. Proof. Assume that G = GL = (XL,E) for some finite join-semidistributive lattice L. If x is a vertex of G then x = 〈↑a,↓b〉 for some a,b ∈ L. Since b 6= 1 we have that b 6 c for some co-atom c. By Lemma 4.5 we have that c is meet-prime and so by Proposition 2.3 we know that ↓c is a prime ideal and that there exists d ∈ L such that ↑d is a prime filter with ↑d ∩ ↓c = ∅ and ↑d ∪ ↓c = L. By Theorem 4.2, y = 〈↑d,↓c〉 is a transitive vertex of GL. Since ↓b ⊆ ↓c we have ↑d ∩ ↓b = ∅ and hence yEx. The converse of the above proposition does not hold. Let L′ be the diamond M3 with a new top element t. Then its dual digraph G is the same as the dual digraph of M3 (see Figure 1) except it has an extra vertex v = 〈↑t,↓1〉, which is transitive since it is total. In G the edges obviously go from the vertex v to every other vertex. Hence the set {v} of transitive vertices of G is the dominating set, yet the lattice L′ is not join-semidistributive as it contains a sublattice isomorphic to M3 (cf. [10]). Since transitive elements are connected to join- and meet-prime elements, the previous result is partly related to how the join-primes or meet-primes sit inside the lattice. The next result characterises finite TiRS digraphs G dual to finite lattices, in which the transitive vertices of G form a dominating set. Theorem 4.8. Let G = (V,E) be a finite TiRS digraph. Then G is dual to a finite lattice L in which every co-atom is meet-prime if and only if the transitive vertices of G form a dominating set. Proof. Let G = (V,E) be the dual digraph GL for some finite lattice L in which every co-atom is meet-prime. If x ∈ V then x = 〈↑a,↓b〉 for some a,b ∈ L. Since b 6= 1 we have that b 6 c for some co-atom c. By Proposition 2.3 we know that ↓c is a prime ideal and that there exists d ∈ L 384 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) such that ↑d is a prime filter with ↑d ∩ ↓c = ∅ and ↑d ∪ ↓c = L. By Theorem 4.2, y = 〈↑d,↓c〉 is a transitive vertex of GL = G. Since ↓b ⊆ ↓c we have ↑d ∩ ↓b = ∅ and hence yEx. Next, assume that the transitive vertices of G form a dominating set and let c be a co-atom of L. The pair 〈↑1,↓c〉 is a disjoint filter-ideal pair that can be extended to a maximal disjoint filter-ideal pair 〈↑b,↓c〉. Since the transitive vertices form a dominating set, there exists a transitive vertex 〈↑x,↓y〉 such that 〈↑x,↓y〉E〈↑b,↓c〉, i.e. ↑x ∩ ↓c = ∅. Since 〈↑x,↓y〉 is transitive, we have by Proposition 2.3 and Theorem 4.2 that x is join-prime. Now, we have that 〈↑x,↓c〉 is a disjoint filter-ideal pair which can be extended to a maximal disjoint filter-ideal pair 〈↑a,↓c〉 where a 6 x. Since a c we have c < a ∨ c = 1. Clearly now x 6 a ∨ c and hence x 6 a or x 6 c. The latter cannot happen as ↑x ∩ ↓c = ∅ so x 6 a and hence x = a. Now 〈↑x,↓c〉 is a maximal disjoint filter-ideal pair with x join-prime, and hence c is meet-prime. Remark 4.9. It is well-known (cf. [11, Theorem 2.24]; see also [3, Theorem 3-1.4]) that a finite lattice L satisfies SD∨ if and only if each element in L has a so-called canonical join representation. Using [13, Lemma 1(ii)] we are able to show that the equivalent conditions of Theorem 4.8 hold for the TiRS digraph G dual to a finite lattice L if and only if the top element 1 of L has a canonical join representation. Since canonical join representations are not the focus of this paper, we have decided to present the proof in a separate paper where this will be explored with the proper context and in more depth. Definition 4.10 ([15, Definition 3]). Given a digraph D = (V,E), with vertex set V and edge set E, a set S ⊆ V is an in-dominating set if for every vertex v ∈ V \S, there is a vertex u ∈ S such that vEu. Theorem 4.11. Let G = (V,E) be a finite TiRS digraph. Then G is dual to a finite lattice L in which every atom is join-prime if and only if the transitive vertices of G form an in-dominating set. Proof. Let GL = (XL,E) be the dual digraph of some finite lattice L in which every atom is join-prime. If x ∈ V then x = 〈↑a,↓b〉 for some a,b ∈ L. Assume that x is not transitive. Since a 6= 0 we have that c 6 a for some atom c ∈ L. By Proposition 2.3 we know that ↑c is a prime filter and that there exists d ∈ L such that ↓d is a prime ideal with ↑c ∩ ↓d = ∅ and ↑c ∪ ↓d = L. By Theorem 4.2, y = 〈↑c,↓d〉 is a transitive vertex of GL. Since ↑a ⊆ ↑c we have ↑c ∩ ↓b = ∅ and hence xEy. Next, assume that the transitive vertices of G = (V,E) form an in-dominating set and let c be an atom of L. The pair 〈↑c,↓0〉 is a disjoint filter-ideal pair that can be extended to an MDFIP 〈↑c,↓b〉. Since the transitive vertices form an in-dominating set, there exists a transitive vertex 〈↑x,↓y〉 such that 〈↑c,↓b〉E〈↑x,↓y〉, i.e. ↑c ∩ ↓y = ∅. Since 〈↑x,↓y〉 is transitive, we have by Proposition 2.3 and Theorem 4.2 that y is meet-prime. CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 385 Now, we have that 〈↑c,↓y〉 is a disjoint filter-ideal pair which can be extended to a maximal disjoint filter-ideal pair 〈↑c,↓a〉 where y 6 a. Since c a we have 0 = a ∧ c < c. Clearly now a ∧ c < y and hence a 6 y or c 6 y. The latter cannot happen as ↑c ∩ ↓y = ∅ so a 6 y and hence y = a. Now 〈↑c,↓y〉 is an MDFIP with y is meet-prime, and hence c is join-prime. Corollary 4.12. Let G = (V,E) be a finite TiRS digraph. If G is dual to a finite meet- semidistributive lattice L, then the transitive vertices of G form an in-dominating set. Proof. Let G = (V,E) be a finite TiRS digraph. Assume G is dual to a finite meet-semidistributive lattice L. Then by Lemma 4.5 the atoms of L are join-prime. It then follows from Theorem 4.11 that the transitive elements of L form an in-dominating set. We think it is an interesting problem to try and characterise the dual digraphs of finite join- semidistributive lattices within the class of finite TiRS digraphs whose transitive vertices form a dominating set (and dually). We attempted to do so but were unable to identify the required condition. 5 Minimal closure systems from dual digraphs Closure systems appear in many different areas of mathematics. They were investigated in relation to join-semidistributive lattices by Adaricheva et al. [1]. A comprehensive account of the theory can be found in the book chapters by Adaricheva and Nation [4, 5]. The definitions below all follow the notational conventions used in Adaricheva and Nation [4, Section 4-2] although in some cases the reference is to another source. Definition 5.1 ([14, Definition 30]). Let X be a set and φ : ℘(X) → ℘(X). Then φ is a closure operator on X if for all Y,Z ∈ ℘(X), (i) Y ⊆ φ(Y ), (ii) Y ⊆ Z implies φ(Y ) ⊆ φ(Z), (iii) φ(φ(Y )) = φ(Y ). If X is a set and φ a closure operator on X then the pair 〈X,φ〉 is called a closure system. For Y ⊆ X we say that Y is closed if φ(Y ) = Y . The closed sets of a closure operator φ on X form a complete lattice, denoted by Cld(X,φ). Example 5.2. Let L be a finite lattice. If a ∈ L let Ja = {x ∈ J(L) | x 6 a} and define τ : ℘(J(L)) → ℘(J(L)) by τ(A) = ⋂ {Ja | a ∈ L and A ⊆ Ja}. Then 〈J(L),τ〉 is a closure system. Notice that every finite lattice L is isomorphic to Cld(J(L),τ) via the isomorphism a 7→ Ja. 386 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) From any digraph G = (X,E) we get the closure system 〈X,E∁⊳ ◦E ∁ ⊲〉 (see [9, Theorem 3.3]). Here we recall necessary facts from [9, Section 3]. For a digraph G = (X,E) one can consider the triple (called a context) K(G) := (X,X,E∁), where the relation E∁ ⊆ X × X is the complement of the digraph relation E: E∁ = (X × X)\E. One can then define a Galois connection via so-called polars as follows. The maps E∁⊲ : ( ℘(X),⊆) → (℘(X),⊇) and E∁⊳ : ( ℘(X),⊇) → (℘(X),⊆) are given by E∁⊲(Y ) = { x ∈ X | (∀y ∈ Y )(y,x) /∈ E }, E∁⊳(Y ) = { z ∈ X | (∀y ∈ Y )(z,y) /∈ E }. The so-called concept lattice CL(K(G)) of the context K(G) = (X,X,E∁), given by CL(K(G)) = { Y ⊆ X | (E∁⊳ ◦ E ∁ ⊲)(Y ) = Y }, is a complete lattice when ordered by inclusion. The isomorphism in Proposition 5.3 below is different to the original source but is equivalent because of the one-to-one correspondence between the sets VL and XL. We recall that the definition of the lattice C(GL) is given directly before Theorem 2.7. Proposition 5.3 ([9, Proposition 3.1 and Corollary 3.2]). If L is a finite lattice and GL = (XL,E) is its dual digraph, we have L ∼= C(GL) ∼= CL(K(GL)). The map a 7→ { 〈F,I〉 ∈ XL | a ∈ F } is the isomorphism from L to CL(K(GL)). The definition below is important in understanding the notion of a minimal closure system later on. Definition 5.4 ([4, Definition 4-2.1]). Closure systems 〈X,φ〉 and 〈Y,ψ〉 are called equivalent if Cld(X,φ) ∼= Cld(Y,ψ). Two equivalent systems are called isomorphic if there exists a bijection ρ : X → Y such that ρ(φ(Z)) = ψ(ρ(Z)) for all Z ⊆ X. The left-most lattice in Figure 1 is referred to as L∂4 in [10]. We use this lattice to provide an illustration of Definition 5.4. Example 5.5. Let L = L∂4 and consider its dual digraph GL = (XL,E) = ({cb,de,dc,ea},E). From this digraph we get the closure system 〈XL,E ∁ ⊳ ◦ E ∁ ⊲〉 with Cld(XL,E ∁ ⊳ ◦ E ∁ ⊲) = {∅,{cb},{ea},{de,dc},{cb,de,dc},{ea,de,dc},XL}. CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 387 If we let Y = {cb,de,ea} and φY (S) = Y ∩ (E ∁ ⊳ ◦ E ∁ ⊲)(S) then Cld(Y,φY ) = {∅,{cb},{ea},{de},{cb,de},{ea,de},Y}. It is easy to see that 〈XL,E ∁ ⊳ ◦ E ∁ ⊲〉 and 〈Y,φY 〉 are equivalent but not isomorphic. Proposition 5.6. Let 〈X,φ〉 and 〈Y,ψ〉 be closure systems and let f : X → Y be a mapping. If f(A) is closed in Y for all closed sets A ⊆ X and f−1(B) is closed in X for all closed sets B ⊆ Y then f(φ(A)) = ψ(f(A)) for all A ⊆ X. Proof. Let f be such that f(A) is closed in Y for all closed sets A ⊆ X and f−1(B) is closed in X for all closed sets B ⊆ Y . Notice that for all S ⊆ X we have that φ(S) = ⋂ {A ⊆ X | S ⊆ A and A is closed in X}, and similarly for ψ. Let S ⊆ X. To show the inclusion f(φ(A)) ⊆ ψ(f(A)), let B ∈ Cld(Y,ψ) such that f(S) ⊆ B. Then S ⊆ f−1(B). But f−1(B) is closed in X by our assumption. Hence φ(S) ⊆ f−1(B) = φ(f−1(B)). This implies that f(φ(S)) ⊆ B. Since B was arbitrary, this is true for all closed sets containing f(S). Therefore f(φ(S)) ⊆ ψ(f(S)) = ⋂ {A ⊆ X | f(S) ⊆ A and A is closed in X}. For the reverse inclusion notice that since A ⊆ φ(A) we get that f(A) ⊆ f(φ(A)). But f(φ(A)) is closed by our assumption. Thus ψ(f(A)) ⊆ f(φ(A)). Further, Adaricheva and Nation [4] posed the following problem: given a closure system 〈X,φ〉, can we find a ⊆-minimal subset Y of X and a closure operator ψ on Y such that 〈Y,ψ〉 is equivalent to 〈X,φ〉? Such a closure system is then said to be minimal for 〈X,φ〉. Theorem 5.7 ([5, Lemma 4-2.13]). A closure system 〈X,φ〉 with lattice of closed sets L is minimal if and only if it is isomorphic to 〈J(L),τ〉. Proposition 5.8. Let L be a finite lattice and GL = (XL,E) its dual digraph. Then the mapping f : X → J(L) defined by f(〈F,I〉) = ∧ F is surjective and satisfies f(E∁⊳ ◦ E ∁ ⊲(S)) = τ(f(S)) for all S ⊆ X. Proof. We start by proving the surjectivity of f. Let x ∈ J(L) and let T(x) denote the set {a ∈ L | x∗ 6 a and x a} where x∗ is the unique lower cover of x. We notice that the set T(x) is non-empty since x∗ ∈ T(x). Let y ∈ T(x) be a maximal element (which exists since T(x) is a finite ordered set). Then we claim that 〈↑x,↓y〉 is an MDFIP. We have that ↑x ∩ ↓y = ∅ since x y. Now let 〈↑a,↓b〉 be an MDFIP such that ↑x ⊆ ↑a and ↓y ⊆ ↓b and 〈↑a,↓b〉 6= 〈↑x,↓y〉. We get two cases from this. Case 1: If ↑x 6= ↑a then a < x so a 6 x∗. Thus we get that a 6 x∗ 6 y 6 b, which is a contradiction. Case 2: If ↓y 6= ↓b then y < b and so x∗ 6 y < b. But y is maximal in T(x) so we have that a 6 x 6 b. Again, this is a contradiction. 388 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) Thus 〈↑x,↓y〉 is an MDFIP and f(〈↑x,↓y〉) = x. Hence f is surjective. To help us prove that f preserves closure, we define Ba = {〈F,I〉 ∈ XL | a ∈ F} and Ja = {x ∈ J(L) | x 6 a} for a ∈ L. Notice that the closed sets from 〈XL,E ∁ ⊳ ◦ E ∁ ⊲〉 are exactly the sets Ba for all a ∈ L and the closed sets from 〈J(L),τ〉 are exactly the sets Ja for all a ∈ L (see Proposition 5.3 and Example 5.2). We claim that f(Ba) = Ja and f −1(Ja) = Ba for all a ∈ L. Let a ∈ L. We prove firstly that f(Ba) = Ja. To show the inclusion f(Ba) ⊆ Ja, let x ∈ f(Ba). Then x = ∧ F for some 〈F,I〉 ∈ Ba. Since 〈F,I〉 ∈ Ba we have that a ∈ F . This implies that x 6 a. But x ∈ J(L) and thus x ∈ Ja. To show the reverse inclusion f(Ba) ⊇ Ja, let x ∈ Ja. Then by the surjectivity there is y ∈ L such that 〈↑x,↓y〉 ∈ XL. Then since x ∈ Ja, we have that x 6 a. This implies that a ∈ ↑x and that 〈↑x,↓y〉 ∈ Ba. Since 〈↑x,↓y〉 ∈ Ba, we get that x ∈ f(Ba). Thus f(Ba) = Ja. Now we prove that f−1(Ja) = Ba for all a ∈ L. To show f −1(Ja) ⊆ Ba, let 〈F,I〉 ∈ f −1(Ja). Then f(〈F,I〉) = x ∈ Ja. Since x ∈ Ja, we have that x 6 a and that a ∈ ↑x = F . Therefore 〈F,I〉 ∈ Ba. To show f −1(Ja) ⊇ Ba, let 〈F,I〉 ∈ Ba. Then a ∈ F and f(〈F,I〉) = ∧ F 6 a. Therefore f(〈F,I〉) ∈ Ja and 〈F,I〉 ∈ f −1(Ja). Thus f −1(Ja) = Ba. By Proposition 5.6 we get f(E∁⊳ ◦ E ∁ ⊲(S)) = τ(f(S)) for all S ⊆ X. The main result of this section is the theorem below. We again refer the reader to Figure 1 for basic illustrative examples, while Example 5.5 provides a demonstration of what can happen when L is not meet-semidistributive. Theorem 5.9. Let L be a finite lattice and GL = (XL,E) its dual digraph. Then 〈XL,E ∁ ⊳ ◦ E ∁ ⊲〉 is a minimal closure system for itself if and only if L is meet-semidistributive. Proof. The necessity will be proved by contraposition. Assume L is not meet-semidistributive. By Proposition 5.8 we have that |J(L)| ≤ |XL| since f is surjective. But by Theorem 3.2 there exist distinct MDFIPs 〈↑x,↓y〉 and 〈↑x,↓z〉 where x ∈ J(L). This implies that f is not injective and hence |J(L)| < |XL|. Therefore by [5, Lemma 4-2.13], 〈X,E ∁ ⊳ ◦ E ∁ ⊲〉 is not minimal. For the sufficiency, assume that L is meet-semidistributive. We will show that f defined in Propo- sition 5.8 is a bijection. We only need to show that f is injective. Let 〈F,I〉,〈G,J〉 ∈ X be such that f(〈F,I〉) = f(〈G,J〉) = x. Then F = G = ↑x. By Theorem 3.2 we have that I = J. Therefore 〈F,I〉 = 〈G,J〉 and hence f is injective. Thus it follows from Propositions 5.6 and 5.8 that f is an isomorphism of closure systems. By [5, Lemma 4-2.13] this implies that 〈X,E∁⊳ ◦ E ∁ ⊲〉 is minimal. Before stating the dual of Theorem 5.9, we need to make some observations. As observed earlier in the section, if L is a finite lattice, with GL = (XL,E) its dual digraph, then L ∼= Cld(XL,E ∁ ⊳ ◦E ∁ ⊲) ∼= CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 389 Cld(J(L),τ). If we reverse the order of the polar maps E∁⊳ and E ∁ ⊲, we again get a closure operator, but with L∂ ∼= Cld(XL,E ∁ ⊲◦E ∁ ⊳). For a finite lattice L, it is easy to show that g : XL → XL∂ , defined for 〈↑a,↓b〉 ∈ XL by g(〈↑a,↓b〉) = 〈↑b,↓a〉, is a bijection. From this we get that 〈XL,E ∁ ⊲ ◦ E ∁ ⊳〉 is isomorphic to 〈XL∂,E ∁ ⊳ ◦ E ∁ ⊲〉. Theorem 5.10. Let L be a finite lattice and GL = (XL,E) its dual digraph. Then 〈XL,E ∁ ⊲ ◦ E ∁ ⊳〉 is a minimal closure system for itself if and only if L is join-semidistributive. Proof. We know that L is join-semidistributive if and only if L∂ is meet-semidistributive. We can then apply Theorem 5.9 to the closure system 〈XL∂,E ∁ ⊳ ◦ E ∁ ⊲〉. Corollary 5.11. Let L be a finite lattice and GL = (XL,E) its dual digraph. Then 〈XL,E ∁ ⊳ ◦E ∁ ⊲〉 and 〈XL,E ∁ ⊲ ◦ E ∁ ⊳〉 are minimal closure systems for themselves if and only if L is semidistributive. 6 Conclusion and future research In this paper we characterised dual digraphs of finite meet-semidistributive, join-semidistributive and semidistributive lattices. We combined Urquhart’s and Ploščica’s representations of finite lattices in the following sense: the vertices of our dual digraphs were maximal disjoint filter-ideal pairs of the lattice in the Urquhart style, but we mainly viewed the duals as TiRS digraphs using the Ploščica binary relation E on the vertices. We introduced transitive vertices in our digraphs and explored their role in the domination theory. In particular, we characterised the finite lattices with the property that in their dual digraphs the transitive vertices form a dominating set resp. an in-dominating set. Finally, we characterised finite meet-semidistributive and join-semidistributive lattices via minimal closure systems on the set of vertices of their dual digraphs. We wish to take note of two other settings in which dual representations of finite semidistributive lattices have been developed. The older of these is that of Formal Concept Analysis, where a char- acterisation of both finite join-semidistributive and meet-semidistributive lattices is available [12, Section 6.3]. There is also a recent paper by Reading, Speyer and Thomas [19] where they give a representation of finite semidistributive lattices via two-acyclic factorization systems. They define a two-acyclic factorization system to be a 4-tuple 〈W,→,։, →֒〉 with a set W and three binary relations →, →֒,։ on W . The relations ։ and →֒ are required to be partial orders. The repre- sentation then comes from defining a factorization system on the set of join-irreducible elements of a semidistributive lattice. The triple (X, →֒,։) is isomorphic to Urquhart’s dual of the lattice L. We note that, in our representation, join- and meet-semidistributive lattices can be considered separately, but in the setting of factorization systems this separation is not yet possible (see [19, Remark 5.14]). 390 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) Lastly, we wish to point to some promising directions for future research. These would build on the representation of finite join- and meet-semidistributive lattices obtained in Section 3. The first of these would be to attempt to study finite sublattices of free lattices via their dual digraphs. This would require first finding a dual description of the well-known Whitman’s Condition. The second direction would be the study of finite convex geometries (see [1, 5]) via their dual digraphs. Finite convex geometries are closure systems that are often studied via their lattice of closed sets. These lattices of closed sets are join-semidistributive and lower semimodular. Work is already under way to find a dual characterisation of upper and lower semimodularity. Acknowledgements The first author acknowledges the National Research Foundation (NRF) of South Africa (grant 127266). The second author acknowledges his appointment as a Visiting Professor at the Uni- versity of Johannesburg from 1 June 2020 and the support by Slovak VEGA grants 1/0152/22 and 2/0078/20. The authors would like to express their appreciation for the referee’s suggestions, which improved the final version of this paper, in particular for the one that led to Remark 4.9. CUBO 24, 3 (2022) Dual digraphs of finite semidistributive lattices 391 References [1] K. V. Adaricheva, V. A. Gorbunov and V. I. Tumanov, “Join-semidistributive lattices and convex geometries”, Adv. Math., vol. 173, no. 1, pp. 1–49, 2003. [2] K. Adaricheva, M. Maróti, R. McKenzie, J. B. Nation and E. R. Zenk, “The Jónsson–Kiefer Property”, Studia Logica, vol. 83, no. 1–3, pp. 111–131, 2006. [3] K. Adaricheva and J. B. Nation, “Classes of semidistributive lattices”, in Lattice Theory: Special Topics and Applications, vol. 2, G. Grätzer and F. Wehrung, Basel: Birkhäuser, 2016, pp. 59–101. [4] K. Adaricheva and J. B. Nation, “Lattices of algebraic subsets and implicational classes”, in Lattice Theory: Special Topics and Applications, vol. 2, G. Grätzer and F. Wehrung, Basel: Birkhäuser, 2016, pp. 103–151. [5] K. Adaricheva and J. B. Nation, “Convex geometries”, in Lattice Theory: Special Topics and Applications, vol. 2, G. Grätzer and F. Wehrung, Basel: Birkhäuser, 2016, pp. 153–179. [6] G. Birkhoff, “On the combination of subalgebras”, Proc. Camb. Phil. Soc., vol. 29, no. 4, pp. 441–464, 1933. [7] A. P. K. Craig, M. J. Gouveia and M. Haviar, “TiRS graphs and TiRS frames: a new setting for duals of canonical extensions”, Algebra Universalis, vol. 74, no. 1–2, pp. 123–138, 2015. [8] A. P. K. Craig, M. J. Gouveia and M. Haviar, “Canonical extensions of lattices are more than perfect”, Algebra Universalis, vol. 83, no. 2, Paper No. 12, 17 pages, 2022. [9] A. Craig and M. Haviar, “Reconciliation of approaches to the construction of canonical ex- tensions of bounded lattices”, Math. Slovaca, vol. 64, no. 6, pp. 1335–1356, 2014. [10] B. A. Davey, W. Poguntke and I. Rival, “A characterization of semi-distributivity”, Algebra Universalis, vol. 5, pp. 72–75, 1975. [11] R. Freese, J. Ježek and J. B. Nation, Free Lattices, Mathematical Surveys and Monographs, vol. 42, Providence, R.I.: American Mathematical Society, 1995. [12] B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Berlin: Springer, 1999. [13] H. S. Gaskill and J. B. Nation, “Join-prime elements in semidistributive lattices”, Algebra Universalis, vol. 12, no. 3, pp. 352–369, 1981. [14] G. Grätzer, Lattice Theory: Foundation, Basel: Birkhäuser, 2011. 392 A. Craig, M. Haviar & J. São João CUBO 24, 3 (2022) [15] T. W. Haynes, S. T. Hedetniemi and M. A. Henning, “Domination in digraphs”, in Structures of Domination in Graphs, vol. 66, Cham: Springer, 2021, pp. 387–428. [16] B. Jónsson, “Sublattices of a free lattice”, Canad. J. Math., vol. 13, pp. 256–264, 1961. [17] M. Ploščica, “A natural representation of bounded lattices”, Tatra Mountains Math. Publ., vol. 5, pp. 75–88, 1995. [18] H. A. Priestley, “Representation of distributive lattices by means of ordered Stone spaces”, Bull. Lond. Math. Soc., vol. 2, no. 2, pp. 186–190, 1970. [19] N. Reading, D. E. Speyer and H. Thomas, “The fundamental theorem of finite semidistributive lattices”, Selecta Math., vol. 27, no. 4, Paper No. 59, 53 pages, 2021. [20] A. Urquhart, “A topological representation theory for lattices”, Algebra Universalis, vol. 8, no. 1, pp. 45–58, 1978. Introduction Preliminaries Characterisation of dual digraphs Domination in dual digraphs Minimal closure systems from dual digraphs Conclusion and future research