צביעה של גרפים מקריים

  • Published on
    29-Jun-2015

  • View
    84

  • Download
    3

Embed Size (px)

DESCRIPTION

The chromatic number of random graphs. Made for a talk given in a graduate guided reading course on random graphs, TAU,IL. Based on Topics in Random Graphs course by Prop. Michael Krivelevich.

Transcript

  • 1. 7 31.21.13 GpV, E q ; G .G ?GG pn, pq ?. GG pn, pq ) ( n . 2 log n , 2 ) ( . 1.0 .log x : log2 x1 1.1 GpV, E q. A 1.1 V .E G ,G . pGqk G V1 Vk , f : V rk s k E pv, uq .f puq $ f pv q V Vi .i G k k. ,G , pGq k G k. 2.1 pGq:|V . |pGq V1 Vkkk V .k pGq ,G |Vi | k pGq1 i : 3.1 1 , .GG n 2 n 2 log n. pGqp1 o p1qq1 | .|V

2. 2.1 n k . k G pq k 2 1 2n k f pk qf pk, nq k , max tk|f pkq 1u k k 1 k sindep. sets of sizek#.E r .k 4.1 p2 o p1qq log n : 1:f pk q k 2log n log k k 2kikkj hk log k k!k log n log k n {k!2p q k2 log n k 2k1 n pkq 2 2 k 5.1 1 pGq k . : k 1 .f pk 1q: 1 1 k 2 2 p q n pk 1q pk1q n 2 log n 1 2 2 p qk 2 log n nO n n 1 2 2 k 1 k22nk2f p k 2q f pk 1 q o p1 q 1 sets of size k 2sf pk 2qf pk 1q On.indep#E r pp# indep. sets of size k 2q 1q E r# indep. sets of size k 2so p1q Pr p pGq k 1q1 o p1q Pr, 2.1 : n k n 1p1 o p1qq 2 log n 3.1 : 2n pGq . pGq 3. 1.3.1 pJansonq , , , . : 1. : )( . : r pr Rqpr . : 1 ,E pKnq 2,pr1 2Pr,.RG n)( I .tAi uiI )( : Ai .?R 2. : )( Ai R6 18Ai7Xi0 otherwise : pr pXi1qE rXisPrr Ai)( XiXi I pr E rXi si I r Ai E rX si I)( :? pX0qPr : tAi u , ,R )1( eprr Ai)(exppri I1r Ai pXi0qi IppAi Rq pAj Rqq i j,i j3 pX0qi I , ij $ PrPr Ai AjPr 4. : 6.1 ) ( , 2pX0q ePr ) ( 2 2 p X0q ePr tXi u :)1( . 2.3.1 : 1. . 2. GG pn, pq . 3. . 7.1 1 m k n, G n m k. m pGqn k: : : 1.GI : G , i1. | m |V pGI q Ci GI ,|Ci |k , : 1 .GI : GI Ci , i : i2. GI . 1 n{k n{k; m 2 . mn{ log2 n 1 ,n 2 1 8.1 2 , .GG m 3 k GG p1 o p1qq 2 log n B 4m p k q | ; k k pmqmax k 1 2 2 k k 2m 4k.Pr p pGq k qe4.k 5. kI p1 o p1qq k kp2 o p1qq log m )4.1( .f pk, mq2p2q : m kk f pk I 1, mq f pk I , mqI mI k 2kIm1op1q k 1 k.f pk, mq f pk, mq f pk 1, mq p f pk 2, mq f f kpk,2, mq f pk 1, mq mq loooomoooon k 3 m3op1q1: RE pKm q zE pGq )GG pm, pq R E pKm qASS k| S | k ,rms S .(Pr pe Rq rms 2 E pKm q e1 2: k S . , S XS2 :G S 6 817kASR0 ptherwise :G k Xr s | |XSS m S k: .Pr p pGq k qPr pX : E rX s r s | |E rXS s 0q :, , m pkq 2 2 kS m S k m3op1q S I | 2, S S I| k 1 AS , ASI 2p qp q k1 m k mk 1Pr pXS1 XS I1qki 2 ok o o i o i2 lo mo nlo mo nloooomoooon loooooomoooooon S S I:. Sk 2S SIS m pkq 2 2 kk1 k mSI Sz k 2pp qp qq k1 g piq i ki i2 looooooooooooooomooooooooooooooon i2 k 2i 1PrpAS AS I Rqi 2 pq: g ig p2q k 2m k ppkqp2qq 2 2 2 k2k4 2 m p1 o p1qq k22p q k 25mk m k 2 mkk:g p2q q2 k qp1 o p1qq k2 pm kq!!2 m pk 11q pm 2 pm 6. 1k , i g p2q 4 g piq g piq2 i ,g p2q4k 2 m2 ,1 k 4k 2 g piq 2 m 2i, 144k 2m2 3.3.12m 4k e2 2 Pr p pGq k qPr pX0q e 1n : 2 , GG n . pGq p1 o p1qq 2 log n, , ,mn{ log2 n 0 .|V0 |m ,rns V 1 ,.G rV0 sG m 2 , 8.1 2m 4kp pG rV0sq kqePr m $ kp2 o p1qq log n , mn{ log2 n o p1 q2m 4k n e m2n log8 n 2 e n phV0 rns , |V0|m : pG rV0s kqqPr G 7.1 k pmq 3 , mn{ log2 n n n mp2 o pnqq log n log2 np1 o p1qq 2 log n 1n k .k : pGq2 1.2 , . : 1.2 tS pvq |v V u c : V Z: S .pZ S q G S piiq d pv, wq E : c pvq $ c pwq6: c pv q S pv qpiq dv V 7. 2.2)( S pvqrks ,v G S ) rks (S k. 3.2 G k G S S |S pv q|k .v , k G k, .ch pGq StS pvq |v V u GtV, E u S puq S pvq pv, uq E G S ) (. 2.2 : pGq) ch pGq (. : : 4.2 12k k .n .ch pKn,n q k: k , . : GpA B, E q |B |n| |A . 12k k n k ,r2k 1s k r2k 1s A .B r2k1s kr2k1s k,f : A .g : B S A vB v6 8f vpq 7g pv q S pv q G S . r2k 1s c : A B S pv q c pv q ,v tc pbq |b B u tc paq |a AuTBTA :|TA| k 1 |TA| k |r2k 1s zTA| k r2k 1s X ,k .A X A a .S paq c paq. .|TB | k : ,TA , TB r2k 1s ,|TA | , |TB | k ,TA TB $ , c . . , .7 8. 2.2 : 5.2pKahnq .GG pn, pq .ch pGqp1 o p1qq pGq 6.2 7.2 1 k m n, pV, E q G n m .km 7.1n k ch pGq . StS pvq |v V u |S pvq|n{k m v: .V GS. , , : : 1 .GI : G , j1. c m, k .Ij k Ij ,c , c . .GI2.: 1 GI : GI Ij , j : j S pvq : S pvq z tcu v n{k , n{k, m, m, . : Y, F q pX : GIV GI Y tpv, cq X Y | c S pvquFis the output of the 1st stageS pv qv V pGI qX: X d pv q|S pv q| m)( v )( Y c d pcq GI c . 1 , d pcq m .Y c ) X X W |:(|W | |N pW q | m |W ' . 8 9. | m |W d pcq m c ,N pW q N pW q W N pW q .W :p q| m |N pW qd pcq p q d pv qv Wc N Wpq| m |W||W | |N pW q ,X X , m , . : : ) 5.2( mn{ log2 n k pmq 3 pq p2 o p1qq log n 8.1 , V pGq ,m k. ) k 4.1(. n mp1 o p1qq 2 log n 2.1n k .ch pGq n 2 log n. pGq p1 o p1qq, pGq ch pGq : n 2 log n.ch pGqp1 o p1qq9 7.2

Recommended

View more >