Why concept lattices are large: extremal theory for generators, concepts, and VC-dimension. Issue 5 (4th July 2017)

• Record Type: Journal Article
• Authors: Albano, Alexandre; Chornomaz, Bogdan
• Is Part Of: International journal of general systems. Volume 46:Issue 5(2017)
• Page Start: 440
• Page End: 457
• Publication Date: 2017-07-04
• Subjects: Number of concepts -- minimal generators -- upper bound -- Vapnik–Chervonenkis dimension -- shattered sets -- contranominal scales; System theory -- Periodicals; 003
• DOI: 10.1080/03081079.2017.1354798
• Languages: English
• ISSNs: 0308-1079

Abstract

Abstract: A unique type of subcontexts is always present in formal contexts with many concepts: the contranominal scales. We make this precise by giving an upper bound for the number of minimal generators (and thereby for the number of concepts) of contexts without contranominal scales larger than a given size. We give an interpretation of this bound in terms of the Vapnik–Chervonenkis dimension of the concept lattice. Extremal contexts are constructed which meet this bound exactly. They are completely classified.