Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most delta(p)+1, where delta is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors beta in the product of n lattices L=L(1)x...xL(n), where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into beta. We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors xis an element ofL=L(1)x...xL(n) for a system of polymatroid inequalities f(1)(x) greater than or equal tot(1),...f(r)(x) greater than or equal to t(r) does not exceed max{Q,beta(logt/c(2Q,beta))}, where beta is the number of minimal feasible vectors for the system, Q=|L-1|+...+\L-n\, t=max{t(1),...,t(r)}, and c(rho,beta) is the unique positive root of the equation 2(c)(rho(c/logbeta)-1)=1. This bound is nearly sharp for the Boolean case L={0,1}(n), and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides t(1)..., t(r).