diff --git a/diagram_splittinglemma.pdf b/diagram_splittinglemma.pdf new file mode 100644 index 0000000000000000000000000000000000000000..6a52a067616df8b72b25a2617d826b2ebaa7add4 GIT binary patch literal 12314 zcma)?1#BJ7lBmsa%oMYIOfki9%*@Qp%*+fiGqW8tGc&UtW6TgUGgHhj|L(ogO7}^- zqmia+rnwm^yvBE`$81KajUBC&$@b@>8|LmFeJO8}vp^v+>=S!bR zQEnFq%G^I|X=Vxk9$s8m>N#Cuh3rjl$#0T^QCR8U8oR%QG<-`B+NZeUwsaxSp{yWn z?CRr+ot3!qy~s@w#)RTXRT3R@`k|bD_C>veG%a2#L!HPryxK6kwIFx0E5udvvG9(= z@CJO7D^Z&rGb-0Pyz$v4H-ea$J1hRr|L`;f%aNKW67XUTzxIQ@!>HO&E(+HM>cX&` zLQJB!d9}!EN14PCDf-KGi|r|3CCn!riqHuuuuG1JFkV-uA6e)H9R|Yi zk})(#&7oOo6mwXw1T7q+L&iw;IKShq1I}O3AFKI-IZ!ljF*;n+wmJkgZaTtr*wEi5 z+hmfz8}NQ6_15%^OY@{M*;G25|cB#1va7f+T9K0hHnoBqfL znY)wK6Cx9U(Sux4g~jxrl&KrCj9OIf&ugxga3-~icWq!2k8y(UIgWQ%*_#pIg31HH z;o36-4f+JJe;sn>4bS*8E%Ap1>L8>bg~D)B5@KldH}q%K(@Zasm_`fMi%~(ms<1g} zmK7Qn!_%afRZe_#&oYvuRMdzq)0nqo3z-H98XR>RLr|t)q%<3bjM)`M zl6(~d@EWvi8_9=u;C&@jpaEK?ME1*vNYX7YV#?;SAhrjMs~`V1L3(Ky%OJV`*>Qhu zRjR_8$85Vjl2a52qB=wX$$6{Mb8wiXprYwX`o}jy1iu5~@S14L(jP6-O^`}z*p`XR zkFX(3gYt!^=Wo))v!a$CePR#TN^p9`z7}4jZ8JF{rajpIjJuS1P|L%Q;PrJd4#sU;Od6zt^8-^g z|8{-?`6+nYZLKL!47d$YSXw9+oSq+rQmeCJJUWSNq?5!oRtTO6qR-(ae6dQu7r^z8 z|JxLXz~$y|OD)6=N@HGMs-Lhzn#yTvobtpN9Q`)6Ri(5thvce=Adt~9cq0t9H&@dv zCLs&Klm(hoM2OGXPU>nUP8o17DP4AP6jKpl@|S{=L7J)69FT6 zE1)3`B<=R?lXz7j5f2J*AtD5YEF2z2YkdXK#Vq3(o{X+-4e#`PEmT7ZJ)u($eKx1= z*g5VE=c8jCj_WIfN#pxctPerhny9@5{ah$|OZuCD&GEZiik&4=Ydz(ij>t8?Ez<9l}ic)d#4pYMj#YJ3_!#t~Z#FJl^5Lv&DOZ`H8eo_;|Em4%I8qo?Ek+`g&IJhj063L~WfQr^Uf0D0&?K}kYyU;2;iaA;g)CZ;E zU;z{#4sUn)3dpB&oGT(K$8vd7#Hsov-nQT6D!9%)bd30@iNry>Z8JOfCJOz{Bw-@q z2IJttI+%GLbRGtyH9w4AAW%6G6!kMMqVCQS94o*{D(-BuayEtK3GNY52HLl*$N@$rJNy4J~7s}v=R7ao@)V&_8+p|kNhM@i` zQ(8H@-PTCB0Xy`js}`%3x=tj*jk^=~fS-I=Lph0zuG)&{%Rz*d%#OXIrrlmtgUvk7 zEO~4rs}Jb|kts-r1lo>F7`?ZYaO|)eC+@WNk7stiHPU~+E6QJ%1MSd)%R3tlI*Hc( zvm#!#zgRB{Dj8O7db4Nb;tE zVMcX7<_X^LGGH~|+{}trjw5eVF^i41w6D@csdcAOh2-jmnSOLuV+<_v;&rG$T`D+= z5OC0`fNQ4|XeZ$Bv|u{}KjEyJ8o+(1d$ZO&v=F$6zB|QHmT=Wpe<(p;Qj$6a??V3K ztZ_#`+a;;_C#1S9I31vwZlV|=6+f?l)n*xez5a4DiEs2X3WCD3U=IQ%fE%kOnHo$9 zu+~Gzz4~XHh9L&JI%%FEnoe?DUZG2=B)k6=VO%0ru6tHMG3OX8VIH04yNrv+PJddu zZ4?!%DV45z?Nw6aAM1@s(OEY0+g}n@{;Pr0M<>`LO+|T>RC>}ud@prUxMSCoTmsstNYT`9@|g{!aS z#oEaP#-%}4utQ6!ha<=TW(n9m7%$<@=;^ZP6b~p9I`L`l@pSWapw;F{z$uwbe`Q ze`xdQoT+|`?0G&A)*9?O%`^Zl#w-13CG!6)p(|>$eGwoeKR=)j!&{>k<#m!k0Kt<+ z!GfJWZnwJ*W;8=K6mUppue5b38&LKuV5#TzuLHo^>c8PW!2?Fs9CyxuCZFn_ta3wS zYy#(>kpp!p$Ss$r6KbZB!f4}5s%J%ym;6hU3)x7Ay7+DNxRQJDfHYCn(_x^=uTUvW zN-cDJ;G>PGVS^Mbt=mI;9NTa{oatGGYk~JDk+s=bO9gi+^dt<4X0#v&nU&HfCf8o$ zO!%&dq!FYDUnMXa&BiLXro{rQlw%>!rbmsk&3QFnr{&N}z&<{3EkifaBXD3zAxVSy zc!4M%#YjYW7kuau4l@*n-j!Efqh3on%cRysH$~3cJhoT%h`r+D{mg~n?LzuV!WD(J z*7aoCIQ_`%;px|MmQy=_R!zNW==9jL@9TH#nJ%#y%|Uc)nsHKpo~YD2eA3{(L)eZR ziNqK&$pQ9p4QV{Ss1L&d_30kIgp*ZiImeB(7bqE|^}D_I9hH`6N9`X^ZKii@D**%y zVnw%%aKXh2w>sDb5Jp=t-2E$kN<>#Exhl?O)>;*w_~!z#?qt(LsG<9Ui;EsNY%7$( z1blwU$T5Or=u={H_uIE%e+EkxZ+Dcw0^gFc^U6w93K)40c)>mptuU2fmDP9dO1pZ6 zMZPOgks*R46Hsh8z)}?oMer%WgyIYX0>EJT2*7B64rcvLeLnX%j~Fk!YsTNCn#a6hP_l0FHjGG9K>JrO90lZzermz|TBb z?+r!}59p~Dy-200kC!T(j8x%s)b*Ls!o4ya{Zw~{uLy)f^LnskpO*3r9L@rz8&XgZ;wc$uH{olaY@XKeXvj^4EtIqEvYkOPw=)0Fco4{slDt9N_r@4#i(rCd;a(d#x^>L2c z{DpP3IOBzTC25@2^c*^!Cl5R0#g|W4PI`*{*YS&jDRg1qkFcx8n41_r=7(y#&yTa4 zBk@n?fKQ0`SLGvssh!EcYVyC*KlMC_(|1p0TG&je)SU}FEb#tdZqw+Lis z=VblA*8ef?uqsJwb8K^&fN%*)8en$trgtqMUlIuwm`qNdfIP=7btT&&bp=$d@Tbz{ zl1M12Cn(lsD|I|NwRa=sJoaABlHoH3VT*gm*jdN``twu{#pnxJ6MA`+91m9<6 zRTUHfL;d*+66zMMvCiKRNBnr}yU`b4Dgcsj-|z<{NnD^1<1!yK+#z0Bgg@j$4kv`b z8(4fij)Vpx9Mm;De3JpwS4{ zUqm#d{d*~-Np>DpIu;c2Ot8Uup4>9GmLLIm2OKR9=H5pfx(&J;4x&b4P!K+0BmGvfll6%zdjjc6HsoZS8R{O4BY?1;Fup=HyCLID=-kEhA@_q zmWseP`xem-Nff-s9rn1w3alwX;SX`$2r(G;cI_azzlXpl&6E0Ltq|j%E0gdPtO0oV zfX>0~7BKvDGR(Z{qW&PqK?iW4!JXri0{O1o8 z+mJvKkOdLT+%6tA6kvWuUDv@H9s5cZ}9^TVHjcb=24))K3?9eO}(ZVt)bRu-?y%})F&$;m*(b~_TQ}c{h$x_ zQSHFw?Y{GYvF8F&!5{$PV8ON6o1ay8I1sOuai2d`L)L&`y^-&yPcL~Nm#YU1=ymVK zsBV4yQI;e%P1~%@C|KG4fwjNg?RlLiYM@Cp^jmNL2}j>l95+9e%Ny<@Gm=z`RW~ZC zfwz&p4<>;0!*!PQ4NPxCzlJ{*&VTuOE0xNB`MC8Vj;=Z86IGujj@NQURBl@2Dfn6#o8%V+Y zsz%3ov^Uuv!Talgro_rUK-lhUF{}31iQ}8fLHt6;9PxXU5&LE1ZYGIjV@z5RS3_R2 zaG*6=VoS@#oN4>TLs`R~bQUeGX+mP1mO_%6w6>>W2Mkts*~e2YS31mu-gV?Q-$P+l ztsDbnDyi&1Vv`banRHVY>S#x50^R-n!*skmQ}foy|{nnc<7WjTeo&~T6*Qu^~kPFlWu-Rzu(vk4j|wZrcR3< zpVmcc&6!3t94J3ah~ySJb1&*s+5DB_W9p!Q0I%epi+6#e#owpVy7a%(CoSK;!AWS{AuWoI@Togv(krwGYsoM6)VwN9l!+QOi) zmV}f4Qx;ppseF@e^M^ez)U#Mv4iQ8er#Bs)Qc#Y;i^{Ltq4>miK`Bpk5s1*8$fxOz!MYz3Hbk1wj znXl6?WdhaVj%0A3$50#Cx)RG~ahRU+3Jd)L1tL-PAwiM1*Ba9mkdtb^1bnO#u*5R^43QUhoMRXn$ zK=a%$KP_!@c_UOK9x5tiG|(X1pwtefLqX!mXCH&TM&%^4v>R+--&uUfGw5@fIA@4z zjg(w^+_R$!NxTF>O&(mQv0ZK}PG-5HLy8v`-ZPoLbJ&<7Zr;D(IK!uEA{QIg%&=qjNe z*-7VPDI}j-4(4&;TF0~8->oP{n;eJA3Re%scE3DFp_zqwjSg~tx$~toQ*OYVrMR5- zKTq*SMveJ6YGS4w+m??L%*lPfoKYHR9Mp?8rIGd23e1H4VRIeS`|*?h25}x|(*()Z zn(UH!5>@w!UuTXc@_Z=zPs#exT!pbU z>H`vM@-4meZA-h6^Z28^|`*dO3S7t7yN9m}SS2zceB5G;G6c0Aq z?C3G4+`D|!Qra@+iHbCpHq9$<927hXj3dx$PurXAa@Dsob_5!#M4hP=m;xCb5*zsS zS)EN8CKAjHxe0FfWko5_wENj_zW-hCvp=Lm93-S#6PpgjaqriQCZhH=iVPm64b%*h5bk25MD@GzFvoPa`+;77#H zUWoQ3xvkvJS!SH`dl|Xy^fxTI0lQxH=S@l8EfX%bKkyx_VT(CV{k^Bo3-XdY2(y$1 zn?fB`t^@co`23mUt;VQW-tcveMNS;fmP8SUx?x80%3uN?mr+htKjFc9Gi#R8#IV>) z8NC-^V(sVYDp=X&6|P`sQ*V#aRzbLzXJIy&N*Rfp!}toPFl=tNoL@=$ZFuDDaZ zYrvV^BI6KF%gtWlAl~L%)6B3TNx1BVlB%q;L~g*U0kjqbv30=&htlEfcABG5Gc5T>@`p zQnne{2+PfDA!+a!FO)Jcto>L2LMq;7mr_t5GUir!9C>crp@lv`89pbBuLwgreS3VC zxpdCs8=><2yt}+~kBh4ModaSEubZPLILw<})j(T29E7tq~xmLwZ zap1;Msqbp%SJXaD3YNB$@zsDOx@Xp&xVB#x2{IHz!bv`kn2L8EZV;}%rLowt_zZMS zm<_BhMU||)^oT8p-7QI)r3amU!;_)Lut&$iFAo#0L3*d+4o)G;M&m-0m@2>kWO ze`bj6YL^%H>Ke{Cub`VR#~g;r289I`tVUvHxee!w3%kP8?KR=1w$$&N9~Hx>`>PY0 zwXi4Bsa`U-^34IGi#|WpVraFk=tuw1(d#rYBsi$}6P1_r^k+5+=h(YPw}Gsw$IcEY zQhbPTjrols?&^iYDO^Gr^YBKeHKW{9%PV&@G-EU>GF5~T56^Msl^?~X@=YRJT|n%2 z4^>dTe#!dD5!d1_@QDv?mQ+4ADYD45zTanyRr{_r!%*|kZpb!D)@)Pc1L$V`z;bjs zS#$W1G9$e1ERS8uU(7~LlvVncm5CMz3^|eaatdy&?Xq^GI<8<_mmnhFcz$50>lH}d z*x7$WWImecCYkL!M2h?Ps>UGh3Wk%LY4D(0GC@ED#ft&)qk!%$-1rHjO9_8(g{BOu z;SgbU$$g)Op>2%t$0nqAuu}Uh z6$a7D=!;)M?oYO;H{i+o*|Q>&x=|eyAJTdLq{dor6i|E^a1Mvz`BAl$L33`oq`S1{ zi0QR&r`l&N9aY_8XW!}Vg1H9Lku7HWMIb;E5 zGkjJnQ?zxXGb0m@*EBo{#-fMn8E$OP^xQA{pd1Gx4-JYvt?b2^&!)w}r@WqZ-?@)j z3r7%NfmZ}ZNl!Rf&q#q6Js2aHdPX6`Sbd#*r1CgT&Jiror5d}cxVjS~r3kf8JUNnT z2PCnhec0{!HX$m?zYgG&I9vJVmgnX9s(VG4AT|6F1p)Tz%(Oibs!9<~14g;M>}jKM z>d_g?ngPX}Opu!E1ef|hOT(WdYy6mr_rD)qY!`ya?=Hk|UNhgv6SK|iFM4e1xRZ-n z`@%)Oi5tb5&X_&LZY0-w7zM)H+bdZULznW!tTZraD-}TfV)5-68%A73&Rfi&=NDZY zQa?KM1v%a}JAskVaH!{Egd$c=@4d9p+68Oai93v?ab3CA!RX^`uBuGQo)O88h_YtN zEcZNpIy^kcz(&?NMCjUxXl@Bh`F*lzX{FjRf93bU?%jRx2m;?EVe)YK1vfkw5bN}6}J#77D)x?GU%M&qixb*;U%HqrlOsSOROiI;DY|^+z7=kU*K`2nF`RJ zlF+^~;W?r@B$gwG?!Vf`Ej5TY5nPCS?e?!n3OCUTI)=L&Ow=}32Tqu}Rv%6I+|Vi6 z_f~dt-ns8H_%M!QG9?#Pi~Bv|F{K;8Lmwhb)XUu zR*r);s}viai0!$T=>pulF-hnjeP|Z8Q*j>$viJObb>AB>cnNm&d&B%7GNM=Y& zuYj!9P=n`N$Du+H!GDj#NP@p{#DH&MntZC|8F zTZ_C0yi;(hCA&B+oyhcl8=j}yx>FEGwhk8wkU^n6Q*`Ppc?wxD{-aBmQoImf?U#+_+r`SN5$H=n9 zvV;i@HrnF3WwWmI!2g;s!Y-}+a&7h<&TjlbEDfaSiGHI|wb+R81j9?n9|oOue8!&m zqldAhmH1sN2(tSJB5|DA8M}LZwf7{FEr(|ZOYiZ_fP)Frn@lt5ppry6PF@TJ2z!(x zdfKtn)CP{R4)e>>E;UxRP3cTL(XWrPqV52)%Isk^yyy=D<^BOS=THKbbT!Yu(a5yP z7(`0Ntw(BnDZZZO`Wq*2MW^HN#6J>AO5HwWT7I)> za9$Rs+R3-6vTq%G?mv>rizpl5`b8qOh+Iy-sIwFSZ7M({X)bqN zWs={;g{mnzfPZHlA9Xn*BG`N+^rqbpKwk*Rs(LWd(=7iVv#GwPuNENm8?4}JRk;* z^&_TA(tx2wHAdbWGDVB;M9Ja3MZYJVnO@bsHoNo1=Ak&TEqGRS=_t=R7rAz$)%8xK zaNqs0zpHF13ZkUJc2#a7rX*+mw9$0b=!v>^q&@PJLIZe~0A7`DI1Z?qDw0 z^-f_hEPfO+ih1Lsv8hX=eD{LHO6{YnjKj$_b$9!2nC^WM7WsIg1WK9@J4>$w`Vjw`O=XxA%8PM5HDI9aQAj4iwJmgZ;PS859FQ z0{7v6bibp|@1}Fremb^*~c*@5M~7b(7Q^PSADunu25)p4f4+Kzs1bqs66>&xgfoT?N%t*bxeh27^t7zTKL|wU_2@k%o-N5=sL2o zbGl9hWv>7~VxP~wLz?Qc{gzVd%Be7v4y7`A_Ps%V{haYUSMFu+&Sn^|JVF|#1+CUz zrvQe+lh&@aAuzdbGqQv~^N;=%_G!aRqt#NU_yOM7(J+Q)&bLKu5l8f~j!o5H6ns`N zGigIb7zZ=}I%W>MJR$OHX!cP#*+!gv_^`6t_QBggWmOv#@FI|F*zH)~H zD2hE(Z`axNLZ&6uJBwA>2FpU=cOMxMbW)5i+h>RFt~lzl2>k0aUas_v7(Fy7t?(il1eBNED%lX>bwxuSbn=$8upy9e@Pf&lQXn$f$zl6<=bys5;F?xVIQ^^QSy2bw1ilwTU zbWo^n5q{2YJnJSd!{)>)BBE=&*vllUQ;$);jFNY>ho{1LjLC&9B)sZQRxb&F-O;|V zx;L03Q$#5J_UIayU%4&53Hu(UhfFPMqkw0ocgoq^N;gjafZ!O-3wx1qFE9l;B+R{! z>XBXS?0x{#D#wZ{;P1yu3Z^9sUcFO`iq)dM#(~K)%;y;GMCvf-e!{JQ8hFF zITB@8El@2OOE4B|XdqTr06t$&YThNP^Z3HkpeDhEM)q^_N8p~yHxq)kDRY|hk;iUD zFiE8sjiQL49N1;icoK{aduqq)f^n5SNk)gvy*9OX@c}6F>}bs7FmJ$(+5W-rVjfxQ zDckiS^^KlbUz4>B;jerwTv_fJx?HFcfM;sumj1iow9D_5_^Z~aB?@!)04;|FywS%# z!*X%A@(stn{rY-hYe8&liM7Sk<923wOOY**@Y(s%TfBF6&~qkl?9Gea8|-#8dr{ao zyi}s5KdBu=WQ*u<^~azMvo`r{-t@|4W1^}0#_-PDruambrMS8u5j*3k*bsE`zhqOX z?e=~a%UqgFSHS>?f)U@ND<=<#9^;5V67mbo;>@8`=rolxU~-+4Tzz5S0AKz{AY@HL`)g`lzEf<2$Z0<_-J`>@&`iy zGgM1^c+giW!?e%jux~o8U%$X|f3JjkMrR$G3z#>~jyrS(ck6P>c4;%qG<3z0a#_c|(8ap%$wAXx zRGkx3yMaYGpFG}1H`jN^7>0_wa!5M0d@uwMUBEV}?91lflY^sBrONlcO1I60D1m6JR$l5$}>HEPc(!u3IFo>)uqqWs@Z z%BRXPvjR^wpQf)aZBEuknrdGjz6$Bi!cb(%>y(9+h)Mrg8nlrs|3;+u@r3YKM*GB*F^bs`wq_YRWz)jtg>SJ)Z0m~7AMjw{mX{%n>Qbs zQ7bG#gCch8?06f~P2g zZVbg{3NDAYHH#4hP1xX?30^{0;q(N*UTVT&-hb=DOx=wn@_wFvGBJMf33um4;??HA z?U>8ASPqd#sPt5$E6SFLjJqPaO4S>NI%@!11^8Qe?-*BoD60}TAH6088}Fbq?FLwV zNPnr20<=vXC@aVj4U ztR_u}s%2z&x0L0}IbEy8HW5nQni0kBwoa)pSa}ut4c9w62^tGX4x{l7(1Jgzs^Ugi zy>6edAIyenR&0H>AKN^}Cfb405ZK6x<1hq;E_gIo4wW((DX?#*nE1}?P?{$FBrUNs zYuS`)`NsJ3*3hT60bq~f>4wD*4RF#fQiCHsu95N<-->Gmu#`ccy%{8nyl->TQ}2bd zrD@VPw4*)nSNF1p{(pA5IseB_x1g(wg}oCMHG_(!i;d~utFo(+m8r4IUrG2cvg-2p znT(-|sRq#9@-OLX;pt%N9dlH*qyKb)s@GG5c%w7nEgTqz7?O zGf10yy4yRMI8#vr{@atKy`9KkCKgB~!o|c0VrS$8F)}hUvVvG>8JQ><87cqT$=aLz zZzd{Eh7Jyxs0O{5tBsA3p`G1d@Rmx&!qOS|_x$hid;_YPIywLC z8puo!Vga#oGO@AJG10UAdz^pm|Gt}yrJE`6pFuGQIvHF1Rqb3osDaiFhAtM)riMVb zf4N|zXQF4O{s-s%7c;>6KPFP;@6-Sp(ukW? zkyySMy}FsZAB{AkLB$LF%tz6Y*ap8Q55W{c1t0YQgUAI1qXH&(XvI_z6@fg{B>52F zmf^=xb1dLFfzdYPOiUIwmVf94h~r^-@)p*K6TljnX9(U>Jz@RX5`4jR7al$hxPbt zh<%5O!0Z{innB4YRulo8jN-t*ncT@a?Xu3XS<75hl&O$J>*CZM_T z5g_0C;^2Gha#mMwSyebDFm$zWGV`<|-{{IMEq!gtwz{0?_hiB!=gY3`eLtVsFQJX7 z7hO>mhHSY`QH|feQ!wI`tG|oh0)0N+h4X~+2*ri3rag4M&zzYr6jHfQY_~fmgo@nQwe|G!TxrAm%cDL6f8WZzBa{&|Me|*9kN~UH221z>;QxBjv zBajKC3t&*T^!ghhe^D59pf(7|1pMcolD)kP5cCfYuk??(nLQBnPh$B;5dmuRFtG^< z3Nf;>2yt*S3Nng_iZZisa0m+t2@7*DiZQc_@&W&MlfS+ED{$EU9XJ1nz`^=Cf#wec zgPesDRe8fSfQ>f(wABDJAD=n6He*h>haL`xhrjiWz$xWkbaL_doA>}A5GN-)fPz9)UJUU608;X3EdT%j literal 0 HcmV?d00001 diff --git a/diagram_splittinglemma.tex b/diagram_splittinglemma.tex new file mode 100644 index 0000000000000000000000000000000000000000..21a19b1e6255d2a620c429b3667b3194189537ee --- /dev/null +++ b/diagram_splittinglemma.tex @@ -0,0 +1,56 @@ +\documentclass{standalone} +\usepackage[T1]{fontenc} +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{parskip} +\usepackage{marvosym} %Lightning symbol +\usepackage[usenames,dvipsnames]{color} +\usepackage[hidelinks]{hyperref} +\renewcommand*{\familydefault}{\sfdefault} + +\usepackage{bbm} %For \mathbbm{1} +%\usepackage{bbold} +\usepackage{tikz} + +\begin{document} + +\begin{tikzpicture}[scale=0.8] + \def\width{6}; + \def\height{4}; + %\draw[step=1cm] (0,0) grid (\width,\height); + + % Vertices and edges + \foreach \x in {0,...,\width} { + \foreach \y in {0,...,\height} { + \draw (\x,\y) circle (0.10); + \ifnum\x<\width + \draw (\x,\y)+(0.1,0) -- (\x+0.9,\y); + \fi + \ifnum\y<\height + \draw (\x,\y)+(0,0.1) -- (\x,\y+0.9); + \fi + } + } + + % + % The set S : red circles + % + + \draw[fill,red] (3,0) circle (0.08); + \draw[fill,red] (2,1) circle (0.08); + \draw[fill,red] (3,2) circle (0.08); + \draw[fill,red] (3,3) circle (0.08); + \draw[fill,red] (4,4) circle (0.08); + + \draw (3,-0.5) node {$S$}; + + % The set X + \draw[xshift=-0.2cm,dashed] (-0.5,-1.0) -- (2.5,-1.0) -- (2.5,0.5) -- (1.5,0.5) -- (1.5,1.5) -- (2.5,1.5) -- (2.5,3.5) -- (3.5,3.5) -- (3.5,4.5) -- (-0.5,4.5) -- cycle; + \draw (1,-0.5) node {$X$}; + + % The set Y + \draw[xshift=+0.2cm,dashed] (6.5,-1.0) -- (3.5,-1.0) -- (3.5,0.5) -- (2.5,0.5) -- (2.5,1.5) -- (3.5,1.5) -- (3.5,3.5) -- (4.5,3.5) -- (4.5,4.5) -- (6.5,4.5) -- cycle; + \draw (5,-0.5) node {$Y$}; + +\end{tikzpicture} +\end{document} diff --git a/main.tex b/main.tex index 107489a8f105c4f7e71169a4206feca1b6c7d134..e428444ca33218401baed0a5adf45764d4b9b0a8 100644 --- a/main.tex +++ b/main.tex @@ -611,8 +611,10 @@ Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. We de \end{definition} The following Lemma says that if a set $S$ splits the graph in two, then those two parts become independent if the vertices in $S$ never become zero. +\begin{center} + \includegraphics[scale=0.8]{diagram_splittinglemma.pdf} +\end{center} \begin{lemma}[Splitting lemma] \label{lemma:splitting} - \todo{Picture of $S,X,Y$.} Let $G=(V,E)$ be a graph. Let $S,X,Y\subseteq V$ be a partition of the vertices, such that $X$ and $Y$ are disconnected in the graph $G\setminus S$. Furthermore, let $A^X$ and $A^Y$ be any events that depends only on the sites in $X$ and $Y$ respectively. Then we have \begin{align*} \P^{G}_S(\NZ{S} \cap A^X \cap A^Y) @@ -625,7 +627,7 @@ The following Lemma says that if a set $S$ splits the graph in two, then those t %\newcommand{\initone}[1]{\textsc{InitOne}_#1} \begin{proof} - We are considering three different Markov Chains and we will consider paths (i.e. resampling sequences) of them. We will use a superscript to denote to which Markov Chain a path belongs. Let $\xi^G \in \NZ{S}$ be a path of the Markov Chain associated to the resample process on the graph $G$, that satisfies the event $\NZ{S}$. + We are considering three different Markov Chains, and the events $\NZ{S}$ in the different parts of the equation are events on different probability spaces. We will keep using the same notation for these events because it should be clear from the context which Markov Chain is being considered. We will consider paths (i.e. resampling sequences) and we will use a superscript to denote to which Markov Chain a path belongs. Let $\xi^G \in \NZ{S}$ be a path of the Markov Chain associated to the resample process on the graph $G$, that satisfies the event $\NZ{S}$. From $\xi^G$ we will now construct paths $\xi^{G\setminus Y} \in \NZ{S}$ and $\xi^{G \setminus X} \in \NZ{S}$ of the other Markov Chains satisfying the corresponding events on those Markov Chains. Let us write the path $\xi^G$ as an initialization and a sequence of resamplings: \begin{align*} @@ -644,35 +646,31 @@ The following Lemma says that if a set $S$ splits the graph in two, then those t \end{align*} Let $b|_{G\setminus X}$ be the restriction of $b$ to $G\setminus X$ and similar for $b|_{G\setminus Y}$. To construct $\xi^{G\setminus Y}$ and $\xi^{G\setminus X}$, start with $\xi^{G\setminus Y} = \left( (\text{initialize }b|_{G\setminus Y}) \right)$ and $\xi^{G\setminus X} = \left( (\text{initialize }b|_{G\setminus X}) \right)$. For each step $(z_i,v_i,r_i)$ in $\xi^G$ do the following: if $v_i \in X$ then append $(z^{X}_i,v_i,r_i)$ to $\xi^{G\setminus Y}$ and if $v_i \in Y$ then append $(z^{Y}_i,v_i,r_i)$ to $\xi^{G\setminus X}$. - Here $z^{X}_i$ is the number of zeroes that were in $X$ and $z^{Y}_i$ is the number of zeroes in $Y$. We have $z_i = z^{X}_i + z^{Y}_i$ because $\xi^G\in\NZ{S}$ so there can not be any zero in $S$; they all have to be in $X$ or $Y$. Furthermore, this also makes sure that we always have $v_i\in X$ or $v_i\in Y$ since only vertices that are zero can be chosen to resample. + Here $z^{X}_i$ is the number of zeroes that were in $X$ and $z^{Y}_i$ is the number of zeroes in $Y$. We have $z_i = z^{X}_i + z^{Y}_i$ because $\xi^G\in\NZ{S}$ so there can not be any zero in $S$; they all have to be in $X$ or $Y$. Furthermore, this also makes sure that we always have either $v_i\in X$ or $v_i\in Y$ since only vertices that are zero can be chosen to resample. - \todo{from here} - %Let the resulting paths be - %\begin{align*} - % \xi_1 &= \left( (z^{(1)}_{a_1}, s_{a_1}, r_{a_1}), (z^{(1)}_{a_2}, s_{a_2}, r_{a_2}), ..., (z^{(1)}_{a_{|\xi_1|}}, s_{a_{|\xi_1|}}, r_{a_{|\xi_1|}}) \right) \\ - % \xi_2 &= \left( (z^{(2)}_{b_1}, s_{b_1}, r_{b_1}), (z^{(2)}_{b_2}, s_{b_2}, r_{b_2}), ..., (z^{(2)}_{b_{|\xi_1|}}, s_{b_{|\xi_1|}}, r_{b_{|\xi_1|}}) \right) - %\end{align*} - Now $\xi_1$ is a valid (terminating) path from $b_1$ to $\mathbf{1}$, because in the original path $\xi$, all zeroes ``on the $b_1$ side'' have been resampled by resamplings ``on the $b_1$ side''. Since the sites $v,w$ inbetween never become zero, there can not be any zero ``on the $b_1$ side'' that was resampled by a resampling ``on the $b_2$ side''. - Vice versa, any two paths $\xi_1\in\start{b_1}\cap \mathrm{NZ}^{(v,w)}$ and $\xi_2\in\start{b_2}\cap\mathrm{NZ}^{(v,w)}$ also induce a path $\xi\in\start{b} \cap \mathrm{NZ}^{(v,w)}$ by simply interleaving the resampling positions. Note that $\xi_1,\xi_2$ actually induce $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ paths $\xi$ because of the possible orderings of interleaving the resamplings in $\xi_1$ and $\xi_2$. - For a fixed $\xi_1,\xi_2$ we will now show the following: + Now $\xi^{G\setminus Y}$ is a valid path of the Markov Chain associated to the graph $G\setminus Y$ (i.e. with vertices $X\cup S$), because in the original path $\xi^G$, all zeroes in $X$ have been resampled by resamplings in $X$. There can not be a vertex $v\in Y$ such that the resampling of $v$ changed a vertex in $X$, since $X$ and $Y$ are only connected through $S$ and we know $\xi^G\in\NZ{S}$. + + Vice versa, any two paths $\xi^{G\setminus Y}\in\NZ{S}$ and $\xi^{G\setminus X}\in\NZ{S}$ also induce a path $\xi^G\in\NZ{S}$ by simply interleaving the resampling positions. Note that $\xi^{G\setminus Y},\xi^{G\setminus X}$ actually induce $\binom{|\xi^{G\setminus Y}|+|\xi^{G\setminus X}|}{|\xi^{G\setminus Y}|}$ paths $\xi^G$ because of the possible orderings of interleaving the resamplings in $\xi^{G\setminus Y}$ and $\xi^{G\setminus X}$. + For a fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ we will now show the following: \begin{align*} - \sum_{\substack{\xi\in\start{b} \cap \mathrm{NZ}^{(v,w)} \text{ s.t.}\\ \xi \text{ decomposes into } \xi_1,\xi_2 }} \P^{(n)}_b[\xi] &= - \sum_{\text{interleavings of }\xi_1,\xi_2} \P(\text{interleaving}) \cdot \P^{(n)}_{b_1}[\xi_1] \cdot \P^{(n)}_{b_2}[\xi_2] \\ - &= \P^{(n)}_{b_1}[\xi_1] \cdot \P^{(n)}_{b_2}[\xi_2] + \sum_{\substack{\xi^G\in\NZ{S} \text{ s.t.}\\ \xi^G \text{ decomposes into } \xi^{G\setminus Y},\xi^{G\setminus X} }} \P^{G}_S(\xi^G) &= + \sum_{\text{interleavings of }\xi^{G\setminus Y},\xi^{G\setminus X}} \P(\text{interleaving}) \cdot \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot \P^{G\setminus X}_S(\xi^{G\setminus X}) \\ + &= \P^{G\setminus Y}_S(\xi^{G\setminus Y}) \cdot \P^{G\setminus X}_S(\xi^{G\setminus X}) \end{align*} - where both sums are over $\binom{|\xi_1|+|\xi_2|}{|\xi_1|}$ terms. - This is best explained by an example. Lets consider the following fixed $\xi_1,\xi_2$ and an example interleaving where we choose steps from $\xi_2,\xi_1,\xi_1,\xi_2,\cdots$: + where both sums are over $\binom{|\xi^{G\setminus Y}|+|\xi^{G\setminus X}|}{|\xi^{G\setminus Y}|}$ terms. + This is best explained by an example. Lets consider the following fixed $\xi^{G\setminus Y},\xi^{G\setminus X}$ and an example interleaving where we choose steps from $\xi^{G\setminus X},\xi^{G\setminus Y},\xi^{G\setminus Y},\xi^{G\setminus X},\cdots$: + \todo{from here} \begin{align*} - \xi_1 &= \left( (z_1, s_1, r_1), (z_2, s_2, r_2), (z_3, s_3, r_3), (z_4, s_4, r_4),\cdots \right) \\ - \xi_2 &= \left( (z_1', s_1', r_1'), (z_2', s_2', r_2'), (z_3', s_3', r_3'), (z_4', s_4', r_4'),\cdots \right) \\ + \xi^{G\setminus Y} &= \left( (z_1, s_1, r_1), (z_2, s_2, r_2), (z_3, s_3, r_3), (z_4, s_4, r_4),\cdots \right) \\ + \xi^{G\setminus X} &= \left( (z_1', s_1', r_1'), (z_2', s_2', r_2'), (z_3', s_3', r_3'), (z_4', s_4', r_4'),\cdots \right) \\ \xi &= \left( (z_1 + z_1', s_1', r_1'), (z_1+z_2', s_1, r_1), (z_2+z_2', s_2, r_2), (z_3+z_2', s_2', r_2'), \cdots \right) \end{align*} - The probability of $\xi_1$, started from $b_1$, is given by + The probability of $\xi^{G\setminus Y}$, started from $b_1$, is given by \begin{align*} \P^{(n)}_{b_1}[\xi_1] &= \P(\text{pick }s_1|z_1) \P(r_1) \P(\text{pick }s_2|z_2) \P(r_2) \cdots \P(\text{pick }s_{|\xi_1|}|z_{|\xi_1|}) \P(r_{|\xi_1|}) \\ &= \frac{1}{z_1} \P(r_1) \frac{1}{z_2} \P(r_2) \cdots \frac{1}{z_{|\xi_1|}} \P(r_{|\xi_1|}) . \end{align*} - and similar for $\xi_2$ but with primes. + and similar for $\xi^{G\setminus X}$ but with primes. The following diagram illustrates all possible interleavings, and the red line corresponds to the particular interleaving $\xi$ in the example above. \begin{center} \includegraphics{diagram_paths2.pdf} @@ -698,7 +696,6 @@ The following Lemma says that if a set $S$ splits the graph in two, then those t &= \P(\text{path in grid}) \; \P^{(n)}_{b_1}[\xi_1] \; \P^{(n)}_{b_2}[\xi_2] \end{align*} In the grid we see that at every point the probabilities sum to 1, and we always reach the end, so we know the sum of all paths in the grid is 1. This proves the required equality. - We obtain \begin{align*} \P^{(n)}_b(\mathrm{NZ}^{(v,w)},A_1,A_2) @@ -711,7 +708,6 @@ The following Lemma says that if a set $S$ splits the graph in two, then those t \; \cdot \; \P^{(n)}_{b_2}(\mathrm{NZ}^{(v,w)},A_2). \end{align*} - The second equality follows directly from $\mathbb{P}(A\mid B)=\mathbb{P}(A,B)/\mathbb{P}(B)$ and setting $A_1,A_2$ to the always-true event. \end{proof} \begin{lemma}[Conditional independence 2] \label{lemma:eventindependenceNewGen}