Container method: Difference between revisions

Revision as of 02:27, 21 March 2024

Revision as of 19:23, 28 August 2024

Line 69:

:<math>i(G, r) \le {n \choose q}{R \choose r - q}.</math>

'''Lemma 2:''' Let <math>G</math> be a graph on <math>n</math> vertices and assume that an integer <math>q</math> and reals <math>R, D</math> are chosen such that <math>n \le R+ qD</math>. If all subsets <math>U</math> of at least <math>R</math> vertices have at least <math>D|U|/2</math> edges, then there is a collection <math>\mathcal{F}</math> of subsets of <math>q</math> vertices ("fingerprints") and a deterministic function <math>f:\colon \mathcal{C} \rightarrow \mathcal{P}(V(G))</math>, so that for every independent set <math>I \subset V(G)</math>, there is <math>S \in \mathcal{F}</math> such that <math>S \subset I \subset f(S) \cup S</math>.

==Hypergraph container lemma==