Dual digraphs of finite semidistributive lattices

Downloads

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
  • 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.

Downloads

Download data is not yet available.

Published

2022-12-21

How to Cite

[1]
A. Craig, M. Haviar, and J. São João, “Dual digraphs of finite semidistributive lattices”, CUBO, vol. 24, no. 3, pp. 369–392, Dec. 2022.

Issue

Section

Articles