Fredman–Komlós bounds and information theory

Fredman and Komlós have applied an interesting information-theoretic lemma to two problems in combinatorics. They have derived good lower bounds on the minimum size of a family of partitions of an n-element set into at most b classes such that all the subsets (respectively, pairs of subsets) of a certain kind are “separated” by at least one partition in the family. Our aim is to show that the Fredman–Komlós lemma is a special case of a simple inequality between entropies of graphs. The, general inequality enables us to handle more problems on separating partition systems. Part of the problems relate to hashing.