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 
Upper bound on the size of a Concept Lattice (Galois Lattice)?
machine learning;upper bounds;lattice;relational structures;data mining
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|}}\}$