The Largest Number of Prime Implicants of k-term DNF and Cube Partitions

Robert Sloan

It is an often discovered result that every k-term DNF can

have at most 2^k-1prime 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.

This is joint work with Balazs Szorenyi and Gyorgy Turan