Maximal independent sets and separating covers

American Mathematical Monthly, 118 (2011), 418–423.

The answer to the fourth problem in MGIII (what is the largest integer which is the product of positive integers with sum n?) turns out to be an inverse to the solution of the last problem (Katona's problem of determining the maximum number of subsets in a separating family with n elements). We give a combinatorial explanation for this relationship, via Moon and Moser's answer to another question (how many maximal independent sets can a graph on n vertices have?).

Download the paper:

pdf
ps
source: zip

Related links:

My brief Maple package INTCOMP computes and plots (via PSTricks) the complexity of integers.
David R. Wood has recently given a very short proof of Moon and Moser's theorem in his paper “On the number of maximal independent sets in a graph”