Intuitively I would say that the number of concepts is bounded by min(2|O| , 2|A|) where O and A are resp the objects and attributes sets. I get this (most likely wrong) intuition from the observaton that given X0, X1 included in O and the Y0 , Y1 included in A, for any pair of concepts (X0,Y0) and (X1,Y1) we have X0=X1 iff Y0=Y1. Thus there can not be more concepts than the number of object sets neither than the number of attribute sets appearing in the lattice. But the best upper bounds I find in some research papers are much more larger than the one I propose : for example 2|O|+|A|, or 2sqrt(|O|.|A|). And I really dont understand why... Could someone explain me where is my mistake ?
Your upper bound min(2|O| , 2|A|) is correct for the reason you indicate: "there can not be more concepts than the number of object sets neither than the number of attribute sets." This upper bound is achieved when O = A and every element of O is related by the incidence relation to every other element except itself. In this case, (S, O\S) is a concept for every subset S of O and there are no other concepts.
- Badges
- Science topic
- Similar topics
- Mathematics