85
Views
12
CrossRef citations to date
0
Altmetric
Original Articles

Why concept lattices are large: extremal theory for generators, concepts, and VC-dimension

&
Pages 440-457 | Received 15 Apr 2016, Accepted 09 Apr 2017, Published online: 06 Aug 2017
 

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.

Acknowledgements

We would like to deeply thank Bernhard Ganter for the invaluable feedback and fruitful discussions.

Notes

No potential conflict of interest was reported by the authors.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.