Upper bound to number of closed itemsets Given a set $I$ of $n$ items, and a collection $D$ of $m&lt;2^n$ subsets of $I$, a closed itemset is a subset $A$ of $I$ that is contained in strictly more elements of $D$ than any of its proper supersets. Closed itemsets are important in data mining because they provide a compact representation of the dataset. 

I'm trying to find some non-trivial upper bound to the number of closed itemsets. It seems a natural combinatorial question and I'm surprised I can't find anything non-trivial. 

Any suggestion/reference? Thank you.
The bound is $2^{\min(n, m)}$. It is an upper bound because no two "formal concepts" (i.e., closed itemsets with their respective transaction sets) can have the same subset of items or the same subset of transactions. Considering $D$ as an $n$ by $m$ matrix of $0$ or $1$ such that each cell indicates whether item $i$ is part of the $j$-th transaction of $D$, you can reach the bound by filling the matrix to '1' and setting to '0' a "diagonal" (well, not really a diagonal since the matrix is rectangular). If you wish, you can then permute the rows and/or the columns and the number of closed itemsets obviously remains the same. Any number of '1' out of the square matrix where there is the diagonal can be turned into '0' too.

Quite recently, Richard Émilion published in Discrete Applied Mathematics the average and the variance of the number of (frequent) closed itemsets in a rectangular 0/1 matrix with a Bernoulli distribution of the '1's: http://www.univ-orleans.fr/mapmo/membres/emilion/publ/sizeofgl.pdf

That is interesting because real-life datasets usually are very sparse. I am not aware of any bound of the number of (closed) itemsets w.r.t. the density. I believe the formula would not be beautiful at all!

I have already told that to a3nm at ICDT'14: you guys (I am not a theorist, just a data miner) want to read about the so-called "Formal Concept Analysis" (FCA): https://en.wikipedia.org/wiki/Formal_concept_analysis