Bipartite Digraphs with Modular Concept Lattices of height 2
DOI:
https://doi.org/10.31489/2025m3/68-74Keywords:
formal context, full context, formal concept, concept lattice, context graph, bipartite digraph, biclique, modular latticeAbstract
This paper investigates the interaction between Formal Concept Analysis (FCA) and graph theory, with a focus on understanding the structure and representation of concept lattices derived from bipartite directed graphs. We establish connections between the complete formal contexts and their associated bipartite digraphs, providing a foundation for studying modular lattices. Particular attention is given to the structure of concept lattices arising from such contexts and their relationship to the combinatorial properties of the corresponding graphs. The results show that the concept lattice of a complete formal context is isomorphic to a modular lattice of height 2 if and only if its associated bipartite digraph is a disconnected union of bicliques. This establishes a precise correspondence between a specific class of formal contexts and well-studied objects in graph theory. Several examples are presented to illustrate these properties and demonstrate the application of the obtained results. The analysis opens the way for further exploration of lattices associated with more complex graph structures and contributes to a deeper understanding of the relationship between discrete mathematics and formal methods of knowledge representation.
References
Wille, R. (1982). Restructuring lattice theory: An approach based on hierarchies of concepts. Ordered Sets, 445–470. https://doi.org/10.1007/978-94-009-7798-3_15
Ganter, B., & Wille, R. (1999). Formal Concept Analysis: Mathematical Foundations. Springer Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-59830-2
Ganter, B., & Obiedkov, S. (2016). Conceptual Exploration. Springer Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49291-8
Ferre, S., Huchard, M., Kaytoue, M., Kuznetsov, S.O., & Napoli, A. (2020). Formal Concept Analysis: From Knowledge Discovery to Knowledge Processing. A Guided Tour of Artificial Intelligence Research: Volume III: Interfaces and Applications of AI, 411–445. https://doi.org/10.1007/978-3-030-06167-8_13
Bondy, J.A., & Murty, U.S.R. (1976). Graph Theory with Applications. New York: Elsevier Science Ltd/North-Holland. https://doi.org/10.1007/978-1-349-03521-2
Gr¨atzer, G. (2003). General lattice theory. (2nd ed.). Basel: Birkh¨auser. https://doi.org/10.1007/978-3-0348-7633-9
Doerfel, S., Hanika, T., & Stumme, G. (2018). Clones in graphs. In M. Ceci, N. Japkowicz, J. Liu, G. Papadopoulos, Z. Ras (Eds.), Foundations of Intelligent Systems, Lecture Notes in Computer Science, 11177, 3–15. Springer, Cham.
Berry, A., & Sigayret, A. (2004). Representing a concept lattice by a graph. Discrete Applied Mathematics, 144, 27–42. https://doi.org/10.1016/j.dam.2004.02.016
Bazhenov, N., Mustafa, M., & Nurakunov, A.M. (2024). On concept lattices for numberings. Tsinghua Science and Technology, 29(6), 1642–1650. https://doi.org/10.26599/TST.2023.9010102
Bazhenov, N., Mustafa, M., & Nurakunov, A.M. (2022). On two types of concept lattices in the theory of numberings. Lecture Notes in Computer Science, 13571, 79–92. https://doi.org/10.1007/978-3-031-20350-3_8
