It is an often discovered result that every k-term DNF can have at most 2^k - 1 prime implicants and this bound is sharp. We complete this result by giving an explicit description of all k-term DNF with the maximal number of prime implicants: these are DNF that can be represented as a certain kind of decision tree.

The proof uses a splitting lemma for partitions of the hypercube into neighboring cubes. We then consider the splittability of general cube partitions, measuring the influence of variables for the cube partition. We also discuss the connection between this topic and decompositions of complete graphs into complete bipartite graphs. Time permitting, we mention several related open problems.

This is joint work with Bob Sloan and Balazs Szorenyi.