Content deleted Content added
No edit summary |
No edit summary |
||
Line 30:
The name container alludes to this last condition. Such containers often provide an effective approach to characterizing the family of independent sets (subsets of the containers) and to enumerating the independent sets of a hypergraph (by simply considering all possible subsets of a container).
The hypergraph container lemma achieves the above container decomposition in two pieces. It constructs a deterministic function {{math|''f''}}. Then, it provides an algorithm that extracts from each independent set {{math|''I''}} in hypergraph {{math|''H''}}, a relatively small collection of vertices <math>S \subset I</math>, called a ''fingerprint,'' with the property that <math> S \subset I \subset S \cup f(S)</math>. Then, the containers are the collection of sets <math>S \cup f(S)</math> that arise in the above process, and the small size of the fingerprints provides good control on the number of such container sets.
==Graph container algorithm==
Line 53:
===Analysis===
By construction, the output of the above algorithm has property that <math>\{v_{j_1}, \ldots, v_{j_q}\} \subset I \subset \{v_{j_1}, \ldots, v_{j_q}\} \cup (A \cap I)</math>, noting that <math>A \cap I</math> is a vertex subset that is completely determined by <math>\{j_1, \ldots, j_q\}</math> and not otherwise a function of <math>I</math>. To emphasize this we will write <math>A
This suggests that <math>S</math> might be a good choice of a ''fingerprint'' and <math>S(j_1, \ldots j_q) \cup A(j_1, \ldots, j_q)</math> a good choice for a ''container''. More precisely, we can bound the number of independent sets of <math>G</math> of some size <math>r \ge q</math> as a sum over output sequences <math>(j_1, \ldots j_q)</math>
| |||