# Upper bound on the size of a Concept Lattice (Galois Lattice)?

A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ possesses the attribute $a$.

For $P \subseteq O$ and $B \subseteq A$ we define $P'=\{a \in A | \forall o \in P \, oIa \}$ and $B'=\{o \in O | \forall a \in B \, oIa \}$.

$P'$ is the set of attributes shared by all object of $P$ and $B'$ is the set of objects having all the attributes of $B$.

A concept of the context $(O, A, R)$ is a couple $(P, B)$ where $P \subseteq O$ and $B \subseteq A$ such that $P'=B$ and $P=B'$.

The concepts may be organised according to a partial order in a structure called a concept lattice (or "galois" lattice). For more info check the wikipedia page on Formal Concept Analysis.

The number of concepts in a concept lattice is bounded by :

• $2^{1+\sqrt{|R|}}$ as told in this paper (which mentions a result from this paper in german). Note that their upper bound is tighter - the one I give here is less precise.
• $2^{|O|+|A|}$ according to this paper (which is presented as a trivial easy upper bound).

I dont understand why these upper bounds are that large. Intuitively I would say that the number of concepts is bounded by $min(2^{|O|}, 2^{|A|})$. I get this intuition from the observation that since for any pair of concepts $(P_0, B_0)$ and $(P_1, B_1)$ we have $P_0=P_1$ iff $B_0=B_1$, then there can not be more concepts than the number of object sets neither than the number of attribute sets appearing in the lattice.

Could someone explain me if I did a mistake ?

Many thanks, Luz

• I don’t see what is the problem. Yes, $\min\{2^{|O|},2^{|A|}\}$ is an upper bound. The bound in the second paper is, as you say, “presented as a trivial easy upper bound”, which means there is nothing remarkable on the fact that it is not a good bound, nor is it worth wasting more than a minute to think about. The bound mentioned in the first paper (but coming from a completely different paper [13]) is strictly speaking incomparable with your bound, but usually it is stronger in typical cases where $|O|\sim|A|$. – Emil Jeřábek supports Monica Feb 22 '17 at 14:40
• Thank you for answering :) I'm sorry if my question was trivial. But the fact is that I did not find this easy upper bound $min\{2^{|O|}, 2^{|A|}\}$ anywhere... Those two bounds are the only one I could find. And this made me hesitate. Especially $2^{1+\sqrt{|R|}}$ for which if $|O|$ is much greater than $|A|^2$ then their upper bound leads to something close to $2^{1+\sqrt{|O|}}$, whereas the best upper bound is simply $2^{|A|}$. Maybe those papers should have written that a simple immediate upper bound is $min\{2^{|O|}, 2^{|A|}\}$ for newbies like me :) – Luz Feb 22 '17 at 15:04
• Do you think that by integrating the $2^{1+\sqrt{|R|}}$ upper bound we can say that one "good" upper bound is $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}} \}$ ? – Luz Feb 22 '17 at 15:08
• Yes, why not, if you have access to all the three parameters. – Emil Jeřábek supports Monica Feb 22 '17 at 15:34

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound.
When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$