Content deleted Content added
m Open access bot: arxiv updated in citation with #oabot. |
m →Main idea and informal statement: Fixed typo |
||
Line 18:
In the above (and many other) instances, there are usually two natural classes of problems posed about a hypergraph {{math|''H''}}:
* What is the size of a maximum independent set in {{math|''H''}}? What does the collection of maximum-sized independent sets in {{math|''H''}} look like?
* How
These problems are connected by a simple observation. Let <math>\alpha(H)</math> be the size of a largest independent set of {{math|''H''}} and suppose <math>H</math> has <math>i(H)</math> independent sets. Then,
:<math>2^{\alpha(H)} \le i(H) \le \sum_{r = 0}^{\alpha(H)} {|V(H)| \choose r},</math>
| |||