Discovering all associations in discrete data using frequent minimally infrequent attribute sets

Associating categories with measured or observed attributes is a central challenge for discrete mathematics in life sciences. We propose a new concept to formalize this question: Given a binary matrix of objects and attributes, determine all attribute sets characterizing object sets of cardinality t1t1 that do not characterize any object set of size t2>t1t2>t1. We determine how many such attribute sets exist, give an output-sensitive quasi-polynomial time algorithm to determine them, and show that kk-sum matrix decompositions known from matroid theory are compatible with the characterization.