Dual digraphs of finite semidistributive lattices

Andrew Craig; Miroslav Haviar; José São João

doi:10.56754/0719-0646.2403.0369

DOI:

https://doi.org/10.56754/0719-0646.2403.0369

Abstract

Dual digraphs of finite join-semidistributive lattices, meet-semidistributive lattices and semidistributive lattices 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.

Keywords

semidistributive lattice , TiRS digraph , join-semidistributive lattice , meet-semidistributive lattice , dual digraph , domination

Mathematics Subject Classification:

06B15 , 06A75 , 06D75 , 05C20 , 05C69

Andrew Craig Department of Mathematics and Applied Mathematics, University of Johannesburg, PO Box 524, Auckland Park, 2006, South Africa. https://orcid.org/0000-0002-4787-3760
Miroslav Haviar Department of Mathematics and Applied Mathematics, University of Johannesburg, PO Box 524, Auckland Park, 2006, South Africa – Department of Mathematics, Faculty of Natural Sciences, M. Bel University, Tajovského 40, 974 01 Banská Bystrica, Slovakia. https://orcid.org/0000-0002-9721-152X
José São João Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden – Department of Mathematics, KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden. https://orcid.org/0000-0001-5078-362X

Pages: 369–392
Date Published: 2022-12-21
Vol. 24 No. 3 (2022)

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.

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.

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.

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.

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.

G. Birkhoff, “On the combination of subalgebras”, Proc. Camb. Phil. Soc., vol. 29, no. 4, pp. 441–464, 1933.

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.

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.

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.

B. A. Davey, W. Poguntke and I. Rival, “A characterization of semi-distributivity”, Algebra Universalis, vol. 5, pp. 72–75, 1975.

R. Freese, J. Ježek and J. B. Nation, Free Lattices, Mathematical Surveys and Monographs, vol. 42, Providence, R.I.: American Mathematical Society, 1995.

B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Berlin: Springer, 1999.

H. S. Gaskill and J. B. Nation, “Join-prime elements in semidistributive lattices”, Algebra Universalis, vol. 12, no. 3, pp. 352–369, 1981.

G. Grätzer, Lattice Theory: Foundation, Basel: Birkhäuser, 2011.

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.

B. Jónsson, “Sublattices of a free lattice”, Canad. J. Math., vol. 13, pp. 256–264, 1961.

M. PlošÄica, “A natural representation of bounded lattices”, Tatra Mountains Math. Publ., vol. 5, pp. 75–88, 1995.

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.

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.

A. Urquhart, “A topological representation theory for lattices”, Algebra Universalis, vol. 8, no. 1, pp. 45–58, 1978.