Note: 

(LaTeX) Abstract: 
A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph $G=(V,E)$ is
upperbounded by $\delta^{p} + 1$, where $\delta$ is the number of pairs of vertices in $V$ at distance 2, and $p$ is the cardinality of a maximum induced matching in $G$.
In this paper, we give an extension of this result for hypergraphs, or more generally for subsets of vectors $\cB$ in a product of $n$ lattices $\cL=\cL_1\times\cdots\times\cL_n$, where the notion of an induced matching in $G$ is replaced by a certain mapping of elements of $\cB$ to the nodes of a binary tree $\bT$ in some special way. Precisely, for $\cB\subseteq\cL$, let
$\gamma=\gamma(\cB)$ be the number of leaves in the largest tree for which such a mapping exists, denote by $\cI(\cB)$ the set of maximal independent elements of $\cB$, and let $\alpha=\cI(\cB)$ and $\beta=\cB$. We show that $\alpha \le\max\{Q,\beta^{\log \gamma/c(2Q,\beta)}\}$, where
$c(\rho,\theta)$ is the unique positive root of the equation $2^c(\rho^{c/\log \theta}1)=1$, and $Q=\sum_{i=1}^n\cL_i$.
In particular, our bound implies that $\alpha \le (2Q\beta)^{\log \gamma}$. We also give examples of hypergraphs with arbitrarily large $n$, $\alpha$ and $\beta$ for which $\alpha \ge \beta^{(1o(1)) \log \gamma/c}$.
As an application, we get an upper bound on the number
of maximal infeasible sets for a polymatroid inequality in terms of the number of feasible sets. We further show that such a bound allows for the incrementally efficient generation of all minimal feasible solutions to a given system of polymatroid inequalities $f_1(X) \ge t_1,\ldots,f_m(X) \geq t_m$ with quasipolynomially bounded right hand sides $t_1,\ldots,t_m$. 
URL for the Abstract: 

Categories,
Keywords: 
Hypergraphs, lattices, polymatroid functions, enumeration algorithms 
HyperLinks / References / URLs: 

Copyright Message: 

Personal Comments: 

Download
Access Level: 
Intranet 
