*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