The Largest Number of Prime Implicants of k-term DNF and Cube Partitions
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
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