▲ | Introduction to Random Graphs [pdf](math.cmu.edu) | |
5 points by ibobev 16 hours ago | 2 comments | ||
▲ | vivzkestrel 12 hours ago | parent | next [-] | |
Let T1, . . . , Tc be the components of T . Since each Ti is isomorphic to a subgraph of G1, for every i ∈ [c] we have |E(Ti)|/(|V (Ti)| − 1) ≤ m1(G1). In particular, |S| = c ∑ i=1 |E(Ti)| ≤ m1(G1) c ∑ i=1 (|V (Ti)| − 1) = m1(G1)(v − c), so (v − c)/|S| ≥ 1/m1(G1). Therefore μ′({F ⊆ G2 : E(F) ⊇ S}) ≤ Cm1(G1) 1 n !|S|(v−c)/|S| ≤ C1 n1/m1(G1) |S| , as desired. End of proof of Lemma 23.9. Proof of Theorem 23.7 We randomly partition V (G) into random clusters U1, . . . ,Um where |V (F)| | |Ui| and |Ui| ∼ C log n for i = 1, 2, . . . , m. The degree of v ∈ Ui in G[Ui] dominates Bin((δF +α)n, (|Ui|−1)/(n−1)) and so if C is sufficiently large, then w.h.p. δ (Ui) ≥ (δF + α/2)|Ui| for i = 1, 2, . . . , m. So, w.h.p. each Ui con- tains an F-factor. A simple calculation shows that for every set of distinct vertices x1, . . . , xs ∈ V (H) and every function f : [s] → [m], Pr xi ∈ Uf (i) for each i ∈ [s] ≤ C log n n s . (23.23) Theorem 23.7 from Lemma 23.9 (with C replaced by C log n) and Theorem 23.1. this is the kinda stuff that truly scares me. i dont want to sit and decipher what you are trying to explain, i want to understand what you are trying to explain. i wish there was a resource that explained absolutely complex ideas like these in the simplest of words | ||
▲ | znpy 16 hours ago | parent | prev [-] | |
> Introduction > open PDF file > 698 pages jesus |