(original) (raw)

%!PS-Adobe-2.0 %%Creator: dvips 5.511 Copyright 1986, 1993 Radical Eye Software %%Title: reed.dvi %%CreationDate: Fri Aug 1 11:42:37 1997 %%Pages: 3 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%EndComments %DVIPSCommandLine: dvips -o reed.ps reed %DVIPSSource: TeX output 1997.08.01:1142 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N} B /TR{translate}N /isls false N /vsize 11 72 mul N /@rigin{isls{[0 -1 1 0 0 0] concat}if 72 Resolution div 72 VResolution div neg scale isls{Resolution hsize -72 div mul 0 TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{ CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N} B /I{cc 1 add D}B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook} if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255 {IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V{}B /RV statusdict begin /product where{ pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false}ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{ gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail}B /c{-4 M} B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{ p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet TeXDict begin 39158280 55380996 1000 300 300 (/a/home/pommard/algo/salvy/Tex/Sem/Sem97/reed.dvi) @start /Fa 5 58 df<01001F00E700070007000700070007000700070007000700070007000700FFF00C 107D8F13>49 D<1FC06070C038E03CE01C003C00380038006000C00300060408043FF87FF8FFF8 0E107E8F13>I<0F8030E0207070787038207800780070006000C00F8000E000700038003C003C 403CE03CE03C8038407030E00F800E177E8F13>I<40007FFE7FFC7FFC40088010802080200040 0080008001800180030003000300030007000700070007000700070002000F187E9013>55 D<0F80186030306030E018E018E01CE01CE01CE01C603C303C185C0F9C001C0018001800387030 7060606021801F000E177E8F13>57 D E /Fb 33 123 df45 D<000F8200706200C01603801E07000C0E000C1C000C18000C380008300008700000700000E000 00E00000E00000E00000E00020E00020E00020E000406000406000803001001006000C180003E0 00171A7A991B>67 D<03FFF80000700E00007007000070030000E0018000E0018000E0018000E0 01C001C001C001C001C001C001C001C001C0038003800380038003800380038003000700070007 00070007000E0007000C000E001C000E0038000E0070000E00E0001C038000FFFE00001A1A7D99 1D>I<01FF8000380000380000380000700000700000700000700000E00000E00000E00000E000 01C00001C00001C00001C0000380000380000380000380000700000700000700000700000E0000 FFE000111A7E990F>73 D<03FF8000700000700000700000E00000E00000E00000E00001C00001 C00001C00001C0000380000380000380000380000700000700100700100700200E00200E00600E 00400E00C01C0380FFFF80141A7D9918>76 D<03F8001FC00078003C000078003C000078005C00 00B800B80000B800B800009C013800009C013800011C027000011C027000011C047000011C0870 00021C08E000021C10E000021C10E000021C20E000041C41C000041C41C000041C81C000041C81 C000080F038000080F038000080E038000180C038000380C070000FF083FF000221A7D9922>I< 001F8000706001C03003001806001C0E000C1C000C18000E38000E30000E70000E70000EE0001C E0001CE0001CE00038E00038E00030E00070E000E0E000C06001807003003806001C1C0007E000 171A7A991D>79 D<003F1000609001807001007003002006002006002006002006000007000007 C00003F80001FE00007F00000F8000038000018000018020018020018060030060030060060070 0C00C8180087E000141A7D9916>83 D<3FFFFC381C0C201C04401C044038048038048038048038 0400700000700000700000700000E00000E00000E00000E00001C00001C00001C00001C0000380 00038000038000038000078000FFF800161A79991B>I87 D<03CC0E2E181C381C301C701CE038E038E038E038C072C072C07260F261341E180F10 7C8F14>97 D<7E000E000E000E001C001C001C001C00380038003BC03C307830701870187018E0 38E038E038E038C070C060C0E060C063801E000D1A7C9912>I<01F006080C1818383010700060 00E000E000E000E000E008E010602030C01F000D107C8F12>I<001F8000038000038000038000 0700000700000700000700000E00000E0003CE000E2E00181C00381C00301C00701C00E03800E0 3800E03800E03800C07200C07200C0720060F2006134001E1800111A7C9914>I<01E006181C08 380870087010FFE0E000E000E000E000E0086010602030C01F000D107C8F12>I<000700001980 001B80003B0000300000300000700000700000700000700007FF0000E00000E00000E00000E000 00E00001C00001C00001C00001C00001C000038000038000038000038000038000070000070000 070000660000E40000CC0000700000112181990C>I<00F300038B800607000E07000C07001C07 00380E00380E00380E00380E00301C00301C00301C00183C0018780007B8000038000038000070 00607000E0E000C1C0007F000011177E8F12>I<1F800003800003800003800007000007000007 00000700000E00000E00000E7C000F86001E07001E07001C07001C0700380E00380E00380E0038 1C00701C80701C80703880703900E01900600E00111A7E9914>I<030706000000000000384C4E 8E9C9C1C3838707272E2E4643808197C980C>I<3F0707070E0E0E0E1C1C1C1C38383838707070 70E4E4E4E46830081A7D990A>108 D<307C1E00598663009E0783809E0703809C0703809C0703 80380E0700380E0700380E0700380E0E00701C0E40701C0E40701C1C40701C1C80E0380C806018 07001A107C8F1F>I<307C005986009E07009E07009C07009C0700380E00380E00380E00381C00 701C80701C80703880703900E01900600E0011107C8F16>I<01F006180C0C180E300E700E600E E00EE00EE00CE01CE018E030606030C01F000F107C8F14>I<030F000590C009E0C009C06009C0 6009C0600380E00380E00380E00380E00701C00701800703800703000E8E000E78000E00000E00 001C00001C00001C00001C0000FF00001317808F14>I<03C20E2E181C381C301C701CE038E038 E038E038C070C070C07060F061E01EE000E000E001C001C001C001C01FF00F177C8F12>I<30F0 59189E389C189C009C0038003800380038007000700070007000E00060000D107C8F10>I<03E0 04300830187018601C001F801FC00FE000E00060E060E06080C041803E000C107D8F10>I<0600 0E000E000E000E001C001C00FFC01C0038003800380038007000700070007000E100E100E100E2 00640038000A177C960D>I<38064C074E0E8E0E9C0E9C0E1C1C381C381C381C70397039703930 79389A0F0C10107C8F15>I<38184C1C4E1C8E0C9C0C9C0C1C0838083808380870107010702030 4018C00F000E107C8F12>I<078F0008D18010F38020E18020E00020E00001C00001C00001C000 01C000038200038200C38200E78400C5880078F00011107E8F12>120 D<38064C074E0E8E0E9C 0E9C0E1C1C381C381C381C703870387038307838F00F700070006060E0E1C0C18047003C001017 7C8F13>I<038207C40FFC10081010002000400180030004000808100820187FF043E081C00F10 7E8F10>I E /Fc 62 124 df<01C0000003200000061000000E1000000E1000000E1000000E10 00000E2000000E4000000E40000007807F8007001E0007000800078010000B80100013C0200031 C0200060E04000E0F08000E0788000E0390000E01E0080E00E0080700F01003873C3000F807C00 191A7E991E>38 D<00800100020004000C00080018003000300030006000600060006000E000E0 00E000E000E000E000E000E000E000E0006000600060006000300030003000180008000C000400 02000100008009267D9B0F>40 D<8000400020001000180008000C000600060006000300030003 000300038003800380038003800380038003800380038003000300030003000600060006000C00 08001800100020004000800009267E9B0F>I<000C0000000C0000000C0000000C0000000C0000 000C0000000C0000000C0000000C0000000C0000000C0000000C0000FFFFFF80FFFFFF80000C00 00000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C 0000000C0000191A7E951E>43 D<60F0F07010101020204080040B7D830B>II<60F0F06004047D830B>I<078018603030303060186018E01CE01CE01CE01CE01CE01CE0 1CE01CE01CE01CE01CE01C6018601870383030186007800E187E9713>48 D<03000700FF000700070007000700070007000700070007000700070007000700070007000700 0700070007000700FFF00C187D9713>I<0F80106020304038803CC01CE01C401C003C00380038 0070006000C001800100020004040804100430083FF87FF8FFF80E187E9713>I<0F8010E02070 607870382038007800700070006000C00F8000E000700038003C003CE03CE03CC03C4038407030 E00F800E187E9713>I<00300030007000F000F001700370027004700C70087010703070207040 70C070FFFF00700070007000700070007007FF10187F9713>I<30183FF03FE03FC02000200020 002000200027C03860203000380018001C001C401CE01CE01C80184038403030E00F800E187E97 13>I<01E006100C1818383038300070006000E000E7C0E860F030F018E018E01CE01CE01C601C 601C701830183030186007C00E187E9713>I<40007FFE7FFC7FFC400880108010802000400040 0080018001800100030003000300030007000700070007000700070002000F197E9813>I<0780 18603030201860186018601870103C303E600F8007C019F030F86038401CC00CC00CC00CC00C60 08201018600FC00E187E9713>I<07801860303070306018E018E018E01CE01CE01C601C603C30 3C185C0F9C001C00180018003870307060604021801F000E187E9713>I<000C0000000C000000 0C0000001E0000001E0000003F000000270000002700000043800000438000004380000081C000 0081C0000081C0000100E0000100E00001FFE00002007000020070000600780004003800040038 0008001C0008001C001C001E00FF00FFC01A1A7F991D>65 DI<003F0201C0C603 002E0E001E1C000E1C0006380006780002700002700002F00000F00000F00000F00000F00000F0 00007000027000027800023800041C00041C00080E000803003001C0C0003F00171A7E991C>I< FFFF000E01C00E00E00E00300E00380E001C0E001C0E000E0E000E0E000F0E000F0E000F0E000F 0E000F0E000F0E000F0E000F0E000E0E000E0E001E0E001C0E00380E00380E00700E01C0FFFF00 181A7E991D>I<003F020001C0C60003002E000E001E001C000E001C0006003800060078000200 7000020070000200F0000000F0000000F0000000F0000000F0000000F001FFC070000E0070000E 0078000E0038000E001C000E001C000E000E000E000300160001C06600003F82001A1A7E991E> 71 DII<1FFC00E000E000E000 E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E040E0E0E0E0E041C0 61801E000E1A7D9914>II77 DI<007F000001C1C000070070000E0038001C001C003C001E0038000E0078000F 0070000700F0000780F0000780F0000780F0000780F0000780F0000780F0000780F00007807800 0F0078000F0038000E003C001E001C001C000E0038000700700001C1C000007F0000191A7E991E >II82 D<0FC21836200E6006C006C002C002C002E00070007E003FE01FF807FC003E000E000700 03800380038003C002C006E004D81887E0101A7E9915>I<7FFFFF00701C0700401C0100401C01 00C01C0180801C0080801C0080801C0080001C0000001C0000001C0000001C0000001C0000001C 0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C0000001C000000 1C0000001C000003FFE000191A7F991C>I87 D89 D<7FFFC0780380700380600700400700400E00401C00401C0000380000380000700000E00000E0 0001C00001C0000380000700400700400E00400E00401C00C0380080380180700380700780FFFF 80121A7E9917>II93 D<3F8070C070E020700070007007F01C7030707070 E070E071E071E0F171FB1E3C10107E8F13>97 DI<07F80C1C381C30087000E000 E000E000E000E000E0007000300438080C1807E00E107F8F11>I<007E00000E00000E00000E00 000E00000E00000E00000E00000E00000E0003CE000C3E00380E00300E00700E00E00E00E00E00 E00E00E00E00E00E00E00E00600E00700E00381E001C2E0007CFC0121A7F9915>I<07C01C3030 187018600CE00CFFFCE000E000E000E0006000300438080C1807E00E107F8F11>I<01F0031807 380E100E000E000E000E000E000E00FFC00E000E000E000E000E000E000E000E000E000E000E00 0E000E000E007FE00D1A80990C>I<0FCE187330307038703870387038303018602FC020006000 70003FF03FFC1FFE600FC003C003C003C0036006381C07E010187F8F13>II<18 003C003C001800000000000000000000000000FC001C001C001C001C001C001C001C001C001C00 1C001C001C001C001C00FF80091A80990A>I107 DIII<07E01C38300C700E6006E007E007E007E007E007E0 076006700E381C1C3807E010107F8F13>II114 D<1F2060E04020C020C020F0007F003FC01FE000F080 708030C030C020F0408F800C107F8F0F>I<0400040004000C000C001C003C00FFC01C001C001C 001C001C001C001C001C001C201C201C201C201C200E4003800B177F960F>IIIIII123 D E /Fd 7 116 df82 D<03FC000E0E001C1F003C1F00781F00780E00F80000F80000F80000F80000F80000F800 007800007801803C01801C03000E0E0003F80011127E9115>99 D<01FC000F07001C03803C01C0 7801C07801E0F801E0F801E0FFFFE0F80000F80000F800007800007C00603C00601E00C00F0380 01FC0013127F9116>101 D<007F0001E38003C7C00787C00F87C00F83800F80000F80000F8000 0F80000F8000FFF800FFF8000F80000F80000F80000F80000F80000F80000F80000F80000F8000 0F80000F80000F80000F80000F80007FF8007FF800121D809C0F>I110 D114 D<1FD830786018E018E018F000FF807FE07FF01FF807FC007CC01CC01CE01CE018F830CFC00E12 7E9113>I E /Fe 1 1 df0 D E /Ff 1 81 df80 D E /Fg 4 55 df<00C00000C00000C00000C00000C00000C00000C00000C00000 C000FFFF80FFFF8000C00000C00000C00000C00000C00000C00000C00000C00000C00011147E8F 17>43 D<0C003C00CC000C000C000C000C000C000C000C000C000C000C000C000C00FF8009107E 8F0F>49 D<1F00618040C08060C0600060006000C00180030006000C00102020207FC0FFC00B10 7F8F0F>I<0780184030C060C06000C000CF00F080E040C060C060C060406060C030801F000B10 7F8F0F>54 D E /Fh 5 104 df0 D<01FF8007FF800E0000180000 300000600000600000600000C00000C00000FFFF80FFFF80C00000C00000600000600000600000 3000001800000E000007FF8001FF8011167D9218>50 D<0003000300060006000C000C00180018 003000300060006000C000C00180018003000300060006000C000C001800180030003000600060 00C0004000101E7B9600>54 D<007800C001800300030003000300030003000300030003000300 030006000C00F0000C00060003000300030003000300030003000300030003000300018000C000 780D217E9812>102 DI E /Fi 28 122 df<00003FC0FF800000E0E38040000181E600E0000381EC01E00003 00DC01E00007001C00C0000700180000000700380000000E00380000000E00380000000E003800 00000E0070000000FFFFFFFF80001C00700380001C00700700001C00700700001C00700700001C 00E00700001C00E00E00003800E00E00003800E00E00003800E00E00003801C01C00003801C01C 00007001C01C00007001C01C40007001C0388000700380388000700380388000E00380388000E0 0380190000E003000E0000E00700000000C00700000001C00600000001C00600000031860E0000 00798F0C000000F31E18000000620C300000003C07C00000002B29829F28>14 D<1C3C3C3C3C040408081020204080060E7D840E>44 D<7FF0FFE07FE00C037D8A10>I<70F8F8 F0E005057B840E>I<01FFFFFC001E0038001E0018001E0008001E0008003C0008003C0008003C 0008003C00080078001000780800007808000078080000F0100000F0300000FFF00000F0300001 E0200001E0200001E0200001E0200003C0000003C0000003C0000003C000000780000007800000 07800000078000000F800000FFF800001E1F7D9E1E>70 D<01FFF0001F00001E00001E00001E00 003C00003C00003C00003C0000780000780000780000780000F00000F00000F00000F00001E000 01E00001E00001E00003C00003C00003C00003C0000780000780000780000780000F8000FFF800 141F7D9E12>73 D<00F1800389C00707800E03801C03803C0380380700780700780700780700F0 0E00F00E00F00E00F00E20F01C40F01C40703C40705C40308C800F070013147C9317>97 D<07803F8007000700070007000E000E000E000E001C001C001CF01D0C3A0E3C0E380F380F700F 700F700F700FE01EE01EE01EE01CE03CE038607060E031C01F0010207B9F15>I<007E0001C100 0300800E07801E07801C07003C0200780000780000780000F00000F00000F00000F00000F00000 70010070020030040018380007C00011147C9315>I<0000780003F80000700000700000700000 700000E00000E00000E00000E00001C00001C000F1C00389C00707800E03801C03803C03803807 00780700780700780700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C40308C800F07 0015207C9F17>I<007C01C207010E011C013C013802780C7BF07C00F000F000F000F000700070 0170023804183807C010147C9315>I<00007800019C00033C00033C000718000700000700000E 00000E00000E00000E00000E0001FFE0001C00001C00001C00001C000038000038000038000038 0000380000700000700000700000700000700000700000E00000E00000E00000E00000C00001C0 0001C0000180003180007B0000F300006600003C00001629829F0E>I<003C6000E27001C1E003 80E00700E00F00E00E01C01E01C01E01C01E01C03C03803C03803C03803C03803C07003C07001C 0F001C17000C2E0003CE00000E00000E00001C00001C00301C00783800F0700060E0003F800014 1D7E9315>I<01E0000FE00001C00001C00001C00001C000038000038000038000038000070000 070000071E000763000E81800F01C00E01C00E01C01C03801C03801C03801C0380380700380700 380700380E10700E20700C20701C20700C40E00CC060070014207D9F17>I<00C001E001E001C0 00000000000000000000000000000E003300230043804300470087000E000E000E001C001C001C 003840388030807080310033001C000B1F7C9E0E>I<03C01FC003800380038003800700070007 0007000E000E000E000E001C001C001C001C0038003800380038007000700070007100E200E200 E200E200640038000A207C9F0C>108 D<1C0F80F0002630C318004740640C004780680E004700 700E004700700E008E00E01C000E00E01C000E00E01C000E00E01C001C01C038001C01C038001C 01C038001C01C0708038038071003803806100380380E100380380620070070066003003003800 21147C9325>I<1C0F802630C04740604780604700704700708E00E00E00E00E00E00E00E01C01 C01C01C01C01C01C03843803883803083807083803107003303001C016147C931A>I<007C0001 C3000301800E01C01E01C01C01E03C01E07801E07801E07801E0F003C0F003C0F003C0F00780F0 0700700F00700E0030180018700007C00013147C9317>I<01C1E002621804741C04781C04701E 04701E08E01E00E01E00E01E00E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0 072380071E000700000700000E00000E00000E00000E00001C00001C0000FFC000171D809317> I<1C1E002661004783804787804707804703008E00000E00000E00000E00001C00001C00001C00 001C000038000038000038000038000070000030000011147C9313>114 D<00FC030206010C030C070C060C000F800FF007F803FC003E000E700EF00CF00CE00840102060 1F8010147D9313>I<018001C0038003800380038007000700FFF007000E000E000E000E001C00 1C001C001C003800380038003820704070407080708031001E000C1C7C9B0F>I<0E00C03300E0 2301C04381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C07101C0E20 180E20180E201C1E200C264007C38014147C9318>I<0E03803307802307C04383C04301C04700 C08700800E00800E00800E00801C01001C01001C01001C02001C02001C04001C04001C08000E30 0003C00012147C9315>I<0E00C1C03300E3C02301C3E04381C1E04301C0E04701C06087038040 0E0380400E0380400E0380401C0700801C0700801C0700801C0701001C0701001C0602001C0F02 000C0F04000E13080003E1F0001B147C931E>I<0383800CC4401068E01071E02071E02070C040 E00000E00000E00000E00001C00001C00001C00001C040638080F38080F38100E5810084C60078 780013147D9315>I<0E00C03300E02301C04381C04301C04701C08703800E03800E03800E0380 1C07001C07001C07001C07001C0E00180E00180E001C1E000C3C0007DC00001C00001C00003800 F03800F07000E06000C0C0004380003E0000131D7C9316>I E /Fj 10 90 df<00200040008001800300020006000C000C001C001800180038003000300070007000700070 006000E000E000E000E000E000E000E000E000E000E000E000E000E000E0006000700070007000 7000300030003800180018001C000C000C0006000200030001800080004000200B36798115>0 D<8000400020003000180008000C000600060007000300030003800180018001C001C001C001C0 00C000E000E000E000E000E000E000E000E000E000E000E000E000E000E000C001C001C001C001 C0018001800380030003000700060006000C000800180030002000400080000B367E8115>I12 D<000180000300000600000C0000180000380000300000600000E00000C0000180000380000300 000700000700000600000E00000C00001C00001C00001800003800003800003800003800007000 00700000700000700000700000700000E00000E00000E00000E00000E00000E00000E00000E000 00E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E000007000007000 007000007000007000007000003800003800003800003800001800001C00001C00000C00000E00 0006000007000007000003000003800001800000C00000E000006000003000003800001800000C 00000600000300000180115178811B>16 DI<0000060000 0C0000180000380000300000600000C00001C0000180000380000700000600000E00000C00001C 0000180000380000380000700000700000E00000E00001E00001C00001C00003C0000380000380 000780000700000700000F00000F00000E00000E00001E00001E00001C00001C00003C00003C00 003C00003C00003C00003800007800007800007800007800007800007800007800007800007000 00F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F000 00F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F000 00F00000F000007000007800007800007800007800007800007800007800007800003800003C00 003C00003C00003C00003C00001C00001C00001E00001E00000E00000E00000F00000F00000700 0007000007800003800003800003C00001C00001C00001E00000E00000E0000070000070000038 00003800001800001C00000C00000E000006000007000003800001800001C00000C00000600000 3000003800001800000C0000061788758124>32 DI80 D88 DI E /Fk 5 111 df<072018E0306060606060C0C0C0C0C0C841C862D0 3C700D0B7E8A11>97 D<0780184030C060006000C000C000C000402060C01F000B0B7E8A0E>99 D<040C0000000000705898983030606464683006127E910B>105 D<0020002000000000000000 000000038004C008C008C000C0018001800180018003000300030003004600CC0078000B178091 0D>I<71F09A189C18981818183030303030323062606460380F0B7E8A13>110 D E /Fl 14 107 df0 D<70F8F8F87005057C8D0D>I<000000 C0000003C000000F0000003C000000F0000003C00000070000001C00000078000001E000000780 00001E00000078000000E0000000780000001E0000000780000001E0000000780000001C000000 0700000003C0000000F00000003C0000000F00000003C0000000C0000000000000000000000000 000000000000000000000000000000007FFFFF80FFFFFFC01A247C9C23>20 D<003FFFC000FFFFC003C00000070000000C000000180000003000000030000000600000006000 0000C0000000C0000000C0000000C0000000C0000000C0000000C0000000C00000006000000060 0000003000000030000000180000000C0000000700000003C0000000FFFFC0003FFFC01A1C7C98 23>26 D<0000000400000000020000000002000000000100000000008000000000400000000020 FFFFFFFFFCFFFFFFFFFC0000000020000000004000000000800000000100000000020000000002 00000000040026107D922D>33 D<03E0001F000FFC007FC01C7E00C020301F018010600F830008 4007C600084003EC00088001F800048001F800048000F8000480007C000480007E000480007E00 044000DF000840018F8008400307C018200603E030100C01F8E00FF800FFC003E0001F0026147D 932D>49 D<003FF800FFF803C0000700000C0000180000300000300000600000600000C00000C0 0000C00000FFFFF8FFFFF8C00000C00000C000006000006000003000003000001800000C000007 000003C00000FFF8003FF8151C7C981E>I<0000FC0007FE001C3E00201E00C01E01801C03801C 07003C0600380E00381C00601C00003C0000380000380000780000780000700000700000F00000 F00000F00000F00000F00000F00000F80018F800307800707C00C07E00803F83001FFC0007F000 1721809F18>67 D<00FE0003FF800F01E01C007030001860000C60000CC00006C00006C00006C0 0006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C00006C0 0006C00006C00006C00006400002171C7D9A1E>92 D<7FE0FFE0C000C000C000C000C000C000C0 00C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000 C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C000C00040000B2E78 A114>100 DI<000F0038006000E001C001C0 01C001C001C001C001C001C001C001C001C001C001C001C001C0038007001E00F8001E00070003 8001C001C001C001C001C001C001C001C001C001C001C001C001C001C001C000E000600038000F 102D7DA117>II106 D E /Fm 15 122 df<03E01FF83818200020003F803F80400080008000801040207FC01F80 0D0E7F8D10>34 D<60F0F06004047D830A>58 D<60F0F070101020204040040A7D830A>I<0008 001800300030003000600060006000C000C000C0018001800180030003000600060006000C000C 000C00180018001800300030003000600060006000C000C0000D217E9812>61 D86 D<071018F0307060706060C060C060C06080C080C480C4C1C446C838700E0E7E8D13>97 D<07C00C20107020706000C000C000C00080008000C010C02060C03F000C0E7E8D0F>99 D<07C01C20301060106020FFC0C000C000C000C000C010402060C01F000C0E7E8D10>101 D<0300038003000000000000000000000000001C002400460046008C000C001800180018003100 3100320032001C0009177F960C>105 D<00180038001000000000000000000000000001C00220 04300430086000600060006000C000C000C000C001800180018001806300E300C60078000D1D80 960E>I<1F0006000600060006000C000C000C000C00181C1866188E190C32003C003F00318060 C060C460C460C8C0C8C0700F177E9612>I<383C0044C6004702004602008E06000C06000C0600 0C0C00180C00180C40181840181880300880300F00120E7F8D15>110 D<1C3C22462382230346 030603060306030C060C060C0C0C081A3019E018001800300030003000FC001014808D12>112 D<1C04260E4606460686040C040C040C0418081808181018100C6007800F0E7F8D11>118 D<1C02260646064606860C0C0C0C0C0C0C18181818181818380C7007B000300060706070C02180 1E000F147F8D11>121 D E /Fn 11 62 df<001800001800003C00003C00004E00004E00008700 0087000103800303C00201C00601E00400E00C00F008007010007810003820003C20001C40001E 7FFFFEFFFFFFFFFFFF18177E961D>1 D<0102040C1818303070606060E0E0E0E0E0E0E0E0E0E0 60606070303018180C04020108227D980E>40 D<8040203018180C0C0E06060607070707070707 0707070606060E0C0C18183020408008227E980E>I<0030000030000030000030000030000030 00003000003000003000003000003000FFFFFCFFFFFC0030000030000030000030000030000030 0000300000300000300000300000300016187E931B>43 D<07C018303018701C600C600CE00EE0 0EE00EE00EE00EE00EE00EE00EE00E600C600C701C30181C7007C00F157F9412>48 D<03000700FF000700070007000700070007000700070007000700070007000700070007000700 07007FF00C157E9412>I<0F8030E040708030C038E0384038003800700070006000C001800300 06000C08080810183FF07FF0FFF00D157E9412>I<0FE030306018701C701C001C001800380060 07E000300018000C000E000EE00EE00EC00C401830300FE00F157F9412>I<00300030007000F0 01F001700270047008701870107020704070C070FFFE0070007000700070007003FE0F157F9412 >I<01F00608080C181C301C70006000E000E3E0EC30F018F00CE00EE00EE00E600E600E300C30 18183007C00F157F9412>54 D61 D E /Fo 26 122 df<0F00008013C0010021C0010001E0020000E004 0000F008000070100000702000007840000038400000388000003D0000001E0000001C0000001C 0000000E0000001E0000002E0000004F0000008700000107000002078000020380000403800008 03C0001001C0002001E2004000E20080003C00191D7F931C>31 D<007C0001FF000703800C0100 1800001000001000001000001000000FF0000F6000108000200000400000400000800000800000 C002004004007018003FF0000FC00011167F9415>34 D<70F8F8F87005057C840D>58 D<70F8FCFC74040404080810102040060E7C840D>I<000001C00000078000001E000000780000 01E00000078000000E00000038000000F0000003C000000F0000003C000000F0000000F0000000 3C0000000F00000003C0000000F0000000380000000E0000000780000001E0000000780000001E 0000000780000001C01A1A7C9723>I<000100030003000600060006000C000C000C0018001800 1800300030003000600060006000C000C000C00180018001800300030003000600060006000C00 0C000C00180018001800300030003000600060006000C000C000C000102D7DA117>II<00000200000006000000 0E0000000E0000001E0000001F0000002F0000002F0000004F0000008F0000008F0000010F0000 010F0000020F0000040F0000040F0000080F8000080780001007800020078000200780007FFF80 0040078000800780018007800100078002000780020007C0040003C00C0003C01E0007C0FF807F FC1E207E9F22>65 D<00FFFFFF000F000E000F0006000F0002000F0002001E0002001E0002001E 0002001E0002003C0404003C0400003C0400003C0C0000781800007FF800007818000078180000 F0100000F0100000F0100000F0000401E0000801E0000801E0001001E0001003C0002003C00060 03C0004003C001C0078007C0FFFFFF80201F7E9E22>69 D<00007E0100038183000E0046003800 2E0070001E00E0000E01C0000C0380000C0700000C0F00000C1E0000081E0000083C0000003C00 000078000000780000007800000078000000F0000000F0007FFCF00001E0F00001E0F00003C070 0003C0700003C0700003C038000780380007801C000F800C000B80060033000380C100007F0000 20217E9F24>71 D<00FF803FF0000F800780000F800200000BC00200000BC002000013C0040000 11E004000011E004000011E004000020F008000020F008000020F8080000207808000040781000 00403C100000403C100000403C100000801E200000801E200000801E200000800F200001000F40 0001000F4000010007C000010007C00002000780000200038000020003800006000380000F0001 0000FFE0010000241F7E9E25>78 D86 D<00FFF83FF8000FC00F80000F80060000078004000007C008000003C010000003C020000003E0 40000001E080000001F100000000F300000000F600000000FC0000000078000000007C00000000 7C000000007C00000000BE000000011E000000021E000000061F0000000C0F000000080F800000 100780000020078000004007C000008003C000010003E000030003E0000F0007E000FFE01FFE00 251F7F9E26>88 DI<007FFFF800FC00F000E001E000C003C001 8007800100078003000F0002001E0002003C00040078000000F8000000F0000001E0000003C000 00078000000F0000000F0000001E0000003C00000078008000F0008001F0010001E0010003C003 00078002000F0006001E0004003E000C003C003C007800F800FFFFF8001D1F7D9E1F>I<00F180 0389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E10 F01C20F01C20703C20705C40308C400F078014147E9318>97 D<007C01C207010E0F1E0F1C0E3C 04780078007800F000F000F000F000F00070017002300418380FC010147E9314>99 D<0000780003F80000700000700000700000700000E00000E00000E00000E00001C00001C000F1 C00389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00F00E00F00E 10F01C20F01C20703C20705C40308C400F078015207E9F18>I<007C01C207010E011C013C0138 02780C7BF07C00F000F000F000F0007000700170023004183807C010147E9315>I<00E001E001 E000C000000000000000000000000000000E00130023804380438043808700070007000E000E00 1C001C001C20384038403840388019000E000B1F7E9E10>105 D<0000C00001E00001E00001C0 000000000000000000000000000000000000000000001E00006300004380008380010380010380 020700000700000700000700000E00000E00000E00000E00001C00001C00001C00001C00003800 00380000380000380000700000700030700078E000F1C0006380003E00001328819E13>I<01E0 000FE00001C00001C00001C00001C0000380000380000380000380000700000700000701E00706 100E08700E10F00E20F00E40601C80001D00001E00001FC000387000383800383800381C207038 40703840703840701880E01880600F0014207E9F18>I<1E07802318C023A06043C07043807043 80708700E00700E00700E00700E00E01C00E01C00E01C00E03821C03841C07041C07081C030838 03101801E017147E931B>110 D<03C1E004621804741C08781C08701E08701E10E01E00E01E00 E01E00E01E01C03C01C03C01C03C01C0380380780380700380E003C1C0072380071E0007000007 00000E00000E00000E00000E00001C00001C0000FFC000171D819317>112 D<0F01801183C02183E021C1E041C0E04380608380400700400700400700400E00800E00800E00 800E01000E01000C02000E04000E040006180001E00013147E9316>118 D<0F00601180702180E021C0E041C0E04380E08381C00701C00701C00701C00E03800E03800E03 800E03800E07000C07000C07000E0F00061E0003EE00000E00000E00001C007818007838007070 0060600021C0001F0000141D7E9316>121 D E /Fp 31 123 df<0F1F1F3F7E78F0E00808759F 1A>19 D<387CFEFFFF7F3B030306060E0C18702008107C9F0F>39 D<387CFEFEFE7C3807077C86 0F>46 D<00E00001E0000FE000FFE000F3E00003E00003E00003E00003E00003E00003E00003E0 0003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E00003E0 0003E00003E000FFFF80FFFF80111D7C9C1A>49 D<0000E000000000E000000001F000000001F0 00000001F000000003F800000003F800000006FC00000006FC0000000EFE0000000C7E0000000C 7E000000183F000000183F000000303F800000301F800000701FC00000600FC00000600FC00000 C007E00000FFFFE00001FFFFF000018003F000018003F000030001F800030001F800060001FC00 060000FC000E0000FE00FFE00FFFE0FFE00FFFE0231F7E9E28>65 D<0007FC0200003FFF0E0000 FE03DE0003F000FE0007E0003E000FC0001E001F80001E003F00000E003F00000E007F00000600 7E000006007E00000600FE00000000FE00000000FE00000000FE00000000FE00000000FE003FFF E0FE003FFFE07E00007E007E00007E007F00007E003F00007E003F00007E001F80007E000FC000 7E0007E0007E0003F000FE0000FE01FE00003FFF8E000007FC0600231F7D9E29>71 D73 D76 D80 D<7FFFFFFC7FFFFFFC7C07E07C7007E01C6007E00C6007E00CE007E00EC007E006C007E006C007 E006C007E0060007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E00000 07E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E00003FFFFC0 03FFFFC01F1E7E9D24>84 D<07FC001FFF003F0F803F07C03F03E03F03E00C03E00003E0007FE0 07FBE01F03E03C03E07C03E0F803E0F803E0F803E0FC05E07E0DE03FF8FE0FE07E17147F9319> 97 DI<01FE0007FF801F0FC03E0F C03E0FC07C0FC07C0300FC0000FC0000FC0000FC0000FC0000FC00007C00007E00003E00603F00 C01F81C007FF0001FC0013147E9317>I<0007F80007F80000F80000F80000F80000F80000F800 00F80000F80000F80000F80000F801F8F80FFEF81F83F83E01F87E00F87C00F87C00F8FC00F8FC 00F8FC00F8FC00F8FC00F8FC00F87C00F87C00F87E00F83E01F81F07F80FFEFF03F8FF18207E9F 1D>I<01FE0007FF800F83C01E01E03E00F07C00F07C00F8FC00F8FFFFF8FFFFF8FC0000FC0000 FC00007C00007C00003E00181E00180F807007FFE000FF8015147F9318>I<01FC3C07FFFE0F07 9E1E03DE3E03E03E03E03E03E03E03E03E03E01E03C00F07800FFF0009FC001800001800001C00 001FFF800FFFF007FFF81FFFFC3C007C70003EF0001EF0001EF0001E78003C78003C3F01F80FFF E001FF00171E7F931A>103 DI<1C 003E007F007F007F003E001C00000000000000000000000000FF00FF001F001F001F001F001F00 1F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B217EA00E>I108 DII<01FF0007FFC01F83F03E00F83E00F87C007C7C007CFC007EFC007EFC007EFC00 7EFC007EFC007E7C007C7C007C3E00F83E00F81F83F007FFC001FF0017147F931A>II<01F81807FE381F87783F01F83E01F87E00F87C00F8FC00F8FC00F8 FC00F8FC00F8FC00F8FC00F87C00F87E00F87E00F83F01F81F87F80FFEF803F8F80000F80000F8 0000F80000F80000F80000F80000F80007FF0007FF181D7E931C>II<0FE63FFE701E600EE006E006F800FFC07FF83FFC1FFE 03FE001FC007C007E007F006F81EFFFCC7F010147E9315>I<0180018001800380038003800780 0F803F80FFFCFFFC0F800F800F800F800F800F800F800F800F800F800F860F860F860F860F8607 CC03F801F00F1D7F9C14>III121 D<3FFFE03FFFE03C07C0380F80701F80603F00603E00 607C0000F80001F80003F00003E06007C0600F80601F80E03F00C03E01C07C03C0FFFFC0FFFFC0 13147F9317>I E /Fq 71 123 df<00008000000001C000000001C000000003E000000003E000 000005F000000004F000000008F80000000878000000107C000000103C000000203E000000201E 000000401F000000400F000000800F80000080078000010007C000010003C000020003E0000200 01E000040001F000040000F000080000F80008000078001000007C001000003C002000003E0020 00001E007FFFFFFF007FFFFFFF00FFFFFFFF8021207E9F26>1 D<003FC00000E0700003801C00 07000E000F000F001E0007803E0007C03C0003C07C0003E07C0003E07C0003E07C0003E07C0003 E07C0003E07C0003E03C0003C03E0007C01E0007801E0007800E0007000F000F0007000E000300 0C0003801C0001801800818018108080101040C03020404020207FC03FE03FC03FC03FC03FC01C 207E9F21>10 D<001F83E000F06E3001C078780380F8780300F030070070000700700007007000 07007000070070000700700007007000FFFFFF8007007000070070000700700007007000070070 000700700007007000070070000700700007007000070070000700700007007000070070000700 70000700700007007000070070007FE3FF001D20809F1B>I<003F0000E0C001C0C00381E00701 E00701E0070000070000070000070000070000070000FFFFE00700E00700E00700E00700E00700 E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700 E07FC3FE1720809F19>I<003FE000E0E001C1E00381E00700E00700E00700E00700E00700E007 00E00700E00700E0FFFFE00700E00700E00700E00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E00700E00700E00700E07FE7FE1720809F19>I<001F81 F80000F04F040001C07C06000380F80F000300F00F000700F00F00070070000007007000000700 700000070070000007007000000700700000FFFFFFFF0007007007000700700700070070070007 007007000700700700070070070007007007000700700700070070070007007007000700700700 07007007000700700700070070070007007007000700700700070070070007007007007FE3FE3F F02420809F26>I<07070F1C383060C00808779F17>19 D<7038F87CFC7EFC7E743A0402040204 020804080410081008201040200F0E7E9F17>34 D<70F8FCFC74040404080810102040060E7C9F 0D>39 D<0020004000800100020006000C000C00180018003000300030007000600060006000E0 00E000E000E000E000E000E000E000E000E000E000E00060006000600070003000300030001800 18000C000C000600020001000080004000200B2E7DA112>I<800040002000100008000C000600 06000300030001800180018001C000C000C000C000E000E000E000E000E000E000E000E000E000 E000E000E000C000C000C001C001800180018003000300060006000C0008001000200040008000 0B2E7DA112>I<0006000000060000000600000006000000060000000600000006000000060000 00060000000600000006000000060000000600000006000000060000FFFFFFF0FFFFFFF0000600 000006000000060000000600000006000000060000000600000006000000060000000600000006 0000000600000006000000060000000600001C207D9A23>43 D<70F8FCFC740404040808101020 40060E7C840D>II<70F8F8F87005057C840D>I<03F0000E1C001C0E00 180600380700700380700380700380700380F003C0F003C0F003C0F003C0F003C0F003C0F003C0 F003C0F003C0F003C0F003C0F003C0F003C07003807003807003807807803807001806001C0E00 0E1C0003F000121F7E9D17>48 D<018003800F80F3800380038003800380038003800380038003 8003800380038003800380038003800380038003800380038003800380038007C0FFFE0F1E7C9D 17>I<03F0000C1C00100E00200700400780800780F007C0F803C0F803C0F803C02007C00007C0 000780000780000F00000E00001C0000380000700000600000C0000180000300000600400C0040 1800401000803FFF807FFF80FFFF80121E7E9D17>I<03F0000C1C00100E00200F00780F807807 80780780380F80000F80000F00000F00000E00001C0000380003F000003C00000E00000F000007 800007800007C02007C0F807C0F807C0F807C0F00780400780400F00200E001C3C0003F000121F 7E9D17>I<000600000600000E00000E00001E00002E00002E00004E00008E00008E00010E0002 0E00020E00040E00080E00080E00100E00200E00200E00400E00C00E00FFFFF0000E00000E0000 0E00000E00000E00000E00000E0000FFE0141E7F9D17>I<4000007FFFC07FFF807FFF80400100 80020080020080040000080000080000100000200000200000400000400000C00000C00001C000 018000038000038000038000038000078000078000078000078000078000078000078000030000 121F7D9D17>55 D<03F0000E18001C0C00380600380700700700700380F00380F00380F003C0F0 03C0F003C0F003C0F003C07007C07007C03807C0180BC00E13C003E3C000038000038000038000 0700300700780600780E00700C002018001070000FC000121F7E9D17>57 D<70F8F8F8700000000000000000000070F8F8F87005147C930D>I<70F8F8F870000000000000 0000000070F0F8F878080808101010202040051D7C930D>I<7FFFFFE0FFFFFFF0000000000000 0000000000000000000000000000000000000000000000000000FFFFFFF07FFFFFE01C0C7D9023 >61 D<000100000003800000038000000380000007C0000007C0000007C0000009E0000009E000 0009E0000010F0000010F0000010F00000207800002078000020780000403C0000403C0000403C 0000801E0000801E0000FFFE0001000F0001000F0001000F000200078002000780020007800400 03C00E0003C01F0007E0FFC03FFE1F207F9F22>65 DI<000FC0 40007030C001C009C0038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000407C00 004078000040F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8 000000780000007C0000407C0000403C0000401C0000401E0000800E0000800700010003800200 01C0040000703800000FC0001A217D9F21>I69 DI72 DI76 DII<001F800000F0F00001C038000780 1E000F000F000E0007001E0007803C0003C03C0003C07C0003E0780001E0780001E0F80001F0F8 0001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0780001E07C0003E0 7C0003E03C0003C03C0003C01E0007800E0007000F000F0007801E0001C0380000F0F000001F80 001C217D9F23>II82 D<07E0800C1980100780300380600180600180E00180E00080E00080E00080F00000F00000 7800007F00003FF0001FFC000FFE0003FF00001F800007800003C00003C00001C08001C08001C0 8001C08001C0C00180C00380E00300F00600CE0C0081F80012217D9F19>I<7FFFFFE0780F01E0 600F0060400F0020400F0020C00F0030800F0010800F0010800F0010800F0010000F0000000F00 00000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F 0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000001F800007FFFE001C 1F7E9E21>II87 D91 D<080410082010201040204020804080408040B85CFC7EFC7E7C3E381C0F0E7B9F17>I< FEFE06060606060606060606060606060606060606060606060606060606060606060606060606 06060606FEFE072D7FA10D>I<1FE000303000781800781C00300E00000E00000E00000E0000FE 00078E001E0E00380E00780E00F00E10F00E10F00E10F01E10781E103867200F83C014147E9317 >97 D<0E0000FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0000 0E3E000EC3800F01C00F00E00E00E00E00700E00700E00780E00780E00780E00780E00780E0078 0E00700E00700E00E00F00E00D01C00CC300083E0015207F9F19>I<03F80E0C1C1E381E380C70 007000F000F000F000F000F000F00070007000380138011C020E0C03F010147E9314>I<000380 003F8000038000038000038000038000038000038000038000038000038000038003E380061B80 1C0780380380380380700380700380F00380F00380F00380F00380F00380F00380700380700380 3803803807801C07800E1B8003E3F815207E9F19>I<03F0000E1C001C0E003807003807007007 00700380F00380F00380FFFF80F00000F00000F000007000007000003800801800800C01000706 0001F80011147F9314>I<007C00C6018F038F07060700070007000700070007000700FFF00700 070007000700070007000700070007000700070007000700070007000700070007007FF0102080 9F0E>I<0000E003E3300E3C301C1C30380E00780F00780F00780F00780F00780F00380E001C1C 001E380033E0002000002000003000003000003FFE001FFF800FFFC03001E0600070C00030C000 30C00030C000306000603000C01C038003FC00141F7F9417>I<0E0000FE00000E00000E00000E 00000E00000E00000E00000E00000E00000E00000E00000E3E000E43000E81800F01C00F01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C0FFE7FC16207F9F19>I<1C003E003E003E001C000000000000000000000000000E007E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFC00A1F809E 0C>I<00E001F001F001F000E0000000000000000000000000007007F000F00070007000700070 007000700070007000700070007000700070007000700070007000700070007000706070F060F0 C061803F000C28829E0E>I<0E0000FE00000E00000E00000E00000E00000E00000E00000E0000 0E00000E00000E00000E0FF00E03C00E03000E02000E04000E08000E10000E30000E70000EF800 0F38000E1C000E1E000E0E000E07000E07800E03800E03C00E03E0FFCFF815207F9F18>I<0E00 FE000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E00FFE00B20809F0C>I<0E1F01F000FE618618 000E81C81C000F00F00E000F00F00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E0 0E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00 E00E000E00E00E00FFE7FE7FE023147F9326>I<0E3E00FE43000E81800F01C00F01C00E01C00E 01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0FF E7FC16147F9319>I<01F800070E001C03803801C03801C07000E07000E0F000F0F000F0F000F0 F000F0F000F0F000F07000E07000E03801C03801C01C0380070E0001F80014147F9317>I<0E3E 00FEC3800F01C00F00E00E00E00E00F00E00700E00780E00780E00780E00780E00780E00780E00 700E00F00E00E00F01E00F01C00EC3000E3E000E00000E00000E00000E00000E00000E00000E00 000E0000FFE000151D7F9319>I<03E0800619801C05803C0780380380780380700380F00380F0 0380F00380F00380F00380F003807003807803803803803807801C0B800E138003E38000038000 0380000380000380000380000380000380000380003FF8151D7E9318>I<0E78FE8C0F1E0F1E0F 0C0E000E000E000E000E000E000E000E000E000E000E000E000E000E00FFE00F147F9312>I<1F 9030704030C010C010C010E00078007F803FE00FF00070803880188018C018C018E030D0608F80 0D147E9312>I<020002000200060006000E000E003E00FFF80E000E000E000E000E000E000E00 0E000E000E000E000E080E080E080E080E080610031001E00D1C7F9B12>I<0E01C0FE1FC00E01 C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01 C00E03C00603C0030DC001F1FC16147F9319>III<7FC3FC0F01E00701C007018003810001C20000E400 00EC00007800003800003C00007C00004E000087000107000303800201C00601E01E01E0FF07FE 1714809318>II<3FFF380E200E201C40384078407000E0 01E001C00380078007010E011E011C0338027006700EFFFE10147F9314>I E /Fr 7 118 df<03FFFFE0003E0078003C003C003C001E003C001F003C000F003C000F007800 0F0078001F0078001F0078001F0078003E0078003C00F0007800F001F000F007C000FFFFC000F0 01F000F000F801E0007801E0007C01E0003C01E0003E01E0003E01E0003E03C0003C03C0007C03 C0007C03C000F803C000F003C001E0078003C007C00F80FFFFFC0020227EA123>66 D<03FFFF0000003E01E000003C007800003C003C00003C003C00003C003E00003C003E00007800 3E000078003E000078003E000078003E000078007C00007800780000F000F00000F001E00000F0 07800000FFFC000000F00C000000F007000001E007000001E003800001E003800001E003C00001 E003C00001E003C00003C007C00003C007C00003C007C00003C007C00003C007C04003C007C080 078007C08007C003E100FFFC01E3000000007C0022237EA124>82 D<00FF000381C00603C00C03 C01C0180380000780000700000F00000F00000F00000F00000F00000E00000F00000F000807001 007001003806001C180007E00012157C9416>99 D<00001E0000FE00001C00001C00001C00001C 00001C00001C00003800003800003800003800003800003800FC700383700700F00C00F01C0070 3800707800E07000E0F000E0F000E0F000E0F000E0E001C0E001C0E001C0E001C07003C07003C0 380F801C33C007C3F817237CA21B>I<00FE000383800701C00C00E01C00E03800E07800E07000 E0FFFFE0F00000F00000F00000F00000E00000E00000F000407000803000801803000E0C0003F0 0013157D9416>I<01C7C01FC8E001D1E001E1E001E0C001C00003C00003800003800003800003 80000380000700000700000700000700000700000700000E00000F0000FFF00013157F9413> 114 D<0E0070FE07F00E00F00E00700E00700E00701C00E01C00E01C00E01C00E01C00E01C00E0 3801C03801C03801C03801C03803C03805C0380B801C13C007E3F815157C941B>117 D E /Fs 19 119 df<0003FE0040001FFFC0C0007F00F1C001F8003FC003F0000FC007C00007C0 0FC00003C01F800003C03F000001C03F000001C07F000000C07E000000C07E000000C0FE000000 00FE00000000FE00000000FE00000000FE00000000FE00000000FE00000000FE000FFFFC7E000F FFFC7F00001FC07F00001FC03F00001FC03F00001FC01F80001FC00FC0001FC007E0001FC003F0 001FC001FC003FC0007F80E7C0001FFFC3C00003FF00C026227DA12C>71 D<07FC001FFF803F07C03F03E03F01E03F01F01E01F00001F00001F0003FF003FDF01FC1F03F01 F07E01F0FC01F0FC01F0FC01F0FC01F07E02F07E0CF81FF87F07E03F18167E951B>97 DI<00FF8007FFE00F83 F01F03F03E03F07E03F07C01E07C0000FC0000FC0000FC0000FC0000FC0000FC00007C00007E00 007E00003E00301F00600FC0E007FF8000FE0014167E9519>I<0001FE000001FE0000003E0000 003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E0000003E00 01FC3E0007FFBE000F81FE001F007E003E003E007E003E007C003E00FC003E00FC003E00FC003E 00FC003E00FC003E00FC003E00FC003E00FC003E007C003E007C003E003E007E001E00FE000F83 BE0007FF3FC001FC3FC01A237EA21F>I<00FE0007FF800F87C01E01E03E01F07C00F07C00F8FC 00F8FC00F8FFFFF8FFFFF8FC0000FC0000FC00007C00007C00007E00003E00181F00300FC07003 FFC000FF0015167E951A>I<03FC1E0FFF7F1F0F8F3E07CF3C03C07C03E07C03E07C03E07C03E0 7C03E03C03C03E07C01F0F801FFF0013FC003000003000003800003FFF801FFFF00FFFF81FFFFC 3800FC70003EF0001EF0001EF0001EF0001E78003C7C007C3F01F80FFFE001FF0018217E951C> 103 DI<1C003E007F00 7F007F003E001C000000000000000000000000000000FF00FF001F001F001F001F001F001F001F 001F001F001F001F001F001F001F001F001F001F001F00FFE0FFE00B247EA310>I108 DII<00FE0007FFC00F83E01E00F03E00F87C007C7C007C7C007CFC007EFC007EFC007EFC007EFC00 7EFC007EFC007E7C007C7C007C3E00F81F01F00F83E007FFC000FE0017167E951C>II114 D<0FF3003FFF00781F00600700E00300E00300F00300FC00007FE0007F F8003FFE000FFF0001FF00000F80C00780C00380E00380E00380F00700FC0E00EFFC00C7F00011 167E9516>I<0180000180000180000180000380000380000780000780000F80003F8000FFFF00 FFFF000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F80000F8180 0F81800F81800F81800F81800F830007C30003FE0000F80011207F9F16>III E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 1 1 1 0 bop 418 269 a Fs(Graph)19 b(colouring)f(via)g(the)g(probabilistic)f (metho)r(d)852 396 y Fr(Bruce)e(Reed)697 462 y Fq(\023)693 474 y(Equip)q(e)h(Com)o(binatoire)g(CNRS)509 528 y(Univ)o(ersit)o(\023)-21 b(e)16 b(Pierre)f(et)g(Marie)h(Curie,)f(P)o(aris,)g(F)l(rance)834 627 y(April)i(21,)d(1997)583 727 y([summary)g(b)o(y)h(F.)g(Morain)g(and)g(P)l (.)g(Rob)q(ert])800 861 y(1.)26 b Fp(In)o(tro)q(duction)50 942 y Fq(Colouring)17 b(a)f(graph)h(with)g(the)f(minim)o(um)i(n)o(um)o(b)q (er)f(of)f(colours)h(is)h(a)e(classical)i(problem)f(in)h(graph)e(theory)0 996 y(and)h(has)f(man)o(y)g(applications.)25 b(F)l(or)16 b(instance,)h(think) g(of)f(a)g(cellular)j(phone)e(net)o(w)o(ork)e(on)i(whic)o(h)g(eac)o(h)f(v)o (ertex)0 1050 y(\(phone\))i(m)o(ust)f(use)i(a)e(di\013eren)o(t)i(frequency)f (with)h(its)f(neigh)o(b)q(ours.)29 b(This)18 b(problem)h(is)g(also)f(kno)o (wn)f(to)h(b)q(e)g(a)0 1104 y(di\016cult)f(one)e(\(see)g(for)g(instance)h([3) o(]\).)50 1157 y(The)i(purp)q(ose)h(of)e(the)i(talk)f(is)g(to)g(presen)o(t)g (a)f(naiv)o(e)i(algorithm)f(for)f(colouring)i(a)f(certain)h(t)o(yp)q(e)f(of)f (graphs)0 1211 y(and)e(explain)i(ho)o(w)e(to)f(analyze)i(it)g(with)f(elemen)o (tary)h(probabilistic)h(to)q(ols)e(that)g(w)o(e)g(will)i(describ)q(e)g (\014rst.)736 1316 y(2.)26 b Fp(Probabilistic)19 b(to)q(ols)50 1397 y Fq(Throughout)14 b(this)h(section)h(w)o(e)e(denote)h(b)o(y)g(Pr\()p Fo(A)p Fq(\))f(the)h(probabilit)o(y)h(of)e(the)h(ev)o(en)o(t)g Fo(A)p Fq(,)f Fo(E)s Fq(\()p Fo(X)t Fq(\))f(the)i(exp)q(ected)0 1451 y(v)m(alue)g(of)f(the)g(random)f(v)m(ariable)j Fo(X)t Fq(,)d(and)h Fo(E)s Fq(\()p Fo(X=)m(A)881 1458 y Fn(1)899 1451 y Fo(;)8 b(:)g(:)g(:)d(;)j(A)1035 1458 y Fm(n)1058 1451 y Fq(\))13 b(the)h(conditional)i(exp)q(ectation)e(of)g Fo(X)j Fq(relativ)o(e)e(to)0 1505 y(the)g(ev)o(en)o(ts)g Fo(A)250 1512 y Fn(1)270 1505 y Fo(;)8 b(:)g(:)g(:)d(;)j(A)406 1512 y Fm(n)429 1505 y Fq(.)0 1595 y(2.1.)25 b Fp(The)20 b(Lo)o(v\023)-26 b(asz)19 b(Lo)q(cal)i(lemma.)i Fq(Supp)q(ose)17 b(that)g(on)f(some)h(probabilit)o(y)h(space)f(\012,)g(there) g(are)f Fo(n)h Fq(ev)o(en)o(ts)0 1649 y Fo(A)34 1656 y Fn(1)54 1649 y Fo(;)8 b(:)g(:)g(:)d(;)j(A)190 1656 y Fm(n)226 1649 y Fq(that)14 b(are)f(undesirable.)22 b(W)l(e)14 b(wish)h(to)e(estimate)h(if)g (there)h(is)f(a)g(p)q(ositiv)o(e)h(probabilit)o(y)g(to)f(a)o(v)o(oid)f(an)o (y)0 1703 y(of)i(them,)g(i.e.,)f(if)i(there)f(is)h(a)f(p)q(ositiv)o(e)h(lo)o (w)o(er)f(b)q(ound)h(for)f(the)g(quan)o(tit)o(y)799 1781 y(\001)e(=)g(Pr)7 b(\()p Fl(\\)1002 1762 y Fm(n)1002 1792 y(i)p Fn(=1)1061 1781 y Fo(A)1095 1762 y Fm(c)1095 1792 y(i)1113 1781 y Fq(\))g Fo(;)0 1858 y Fq(where)15 b Fo(A)165 1842 y Fm(c)165 1871 y(i)196 1858 y Fq(=)d(\012)e Fl(\000)h Fo(A)366 1865 y Fm(i)380 1858 y Fq(.)20 b(If)15 b(the)h(ev)o(en)o(ts)f(are)f(indep)q(enden)o(t,)k(that)c (is)i(for)e(an)o(y)h Fo(k)q Fq(-tuple)i(1)12 b Fl(\024)h Fo(i)1576 1865 y Fn(1)1608 1858 y Fo(<)g Fl(\001)8 b(\001)g(\001)j Fo(<)i(i)1786 1865 y Fm(k)1819 1858 y Fl(\024)g Fo(n)p Fq(,)709 1983 y(Pr)o(\()p Fl(\\)805 1964 y Fm(k)805 1994 y(j)r Fn(=1)869 1983 y Fo(A)903 1990 y Fm(i)915 1995 y Fk(j)933 1983 y Fq(\))f(=)1032 1926 y Fm(k)1013 1940 y Fj(Y)1011 2037 y Fm(j)r Fn(=1)1080 1983 y Fq(Pr\()p Fo(A)1181 1990 y Fm(i)1193 1995 y Fk(j)1211 1983 y Fq(\))p Fo(;)0 2108 y Fq(then)765 2211 y(\001)h(=)884 2154 y Fm(n)866 2168 y Fj(Y)864 2265 y Fn(1=1)926 2211 y Fq(\(1)d Fl(\000)g Fq(Pr\()p Fo(A)1123 2218 y Fm(i)1137 2211 y Fq(\)\))p Fo(:)0 2329 y Fq(The)21 b(problem)g(is)g(that)f(in)h(practice,)h(the)f(ev)o (en)o(ts)f(are)g(not)g(alw)o(a)o(ys)g(completely)h(indep)q(enden)o(t)i(but)e (w)o(eakly)0 2382 y(indep)q(enden)o(t,)j(in)d(the)g(sense)g(that)f(for)f(eac) o(h)i Fo(i)f Fq(there)h(exists)f(a)h(subset)f Fo(V)1330 2389 y Fm(i)1365 2382 y Fl(\032)i(f)p Fq(1)p Fo(;)8 b(:)g(:)g(:)d(;)j(n)p Fl(g)19 b Fq(suc)o(h)i(that)f Fo(A)1885 2389 y Fm(i)1919 2382 y Fq(is)0 2436 y(indep)q(enden)o(t)d(of)d(the)h(ev)o(en)o(ts)f Fo(A)557 2443 y Fm(j)576 2436 y Fo(;)8 b(j)14 b Fl(2)f Fo(V)709 2420 y Fm(c)700 2449 y(j)727 2436 y Fq(.)19 b(In)c(other)g(w)o(ords,)e Fo(A)1110 2443 y Fm(i)1139 2436 y Fq(is)i(p)q(ossibly)h(dep)q(enden)o(t)g(of) f Fo(A)1663 2443 y Fm(j)1696 2436 y Fq(with)g Fo(j)h Fq(in)g(the)0 2491 y(\\neigh)o(b)q(ourho)q(o)q(d")g Fo(V)383 2498 y Fm(i)412 2491 y Fq(of)e Fo(i)p Fq(.)20 b(If)15 b(the)g(cardinalit)o(y)h(of)f(the)g Fo(V)1019 2498 y Fm(i)1032 2491 y Fq('s)g(is)g(small,)h(one)f(migh)o(t)g(exp) q(ect)h(an)e(estimate)h(close)0 2545 y(to)g(the)g(one)g(w)o(e)g(sa)o(w)f(for) h(the)g(indep)q(enden)o(t)j(case.)i(This)c(is)f(the)h(conclusion)h(of)d(Lo)o (v\023)-23 b(acs's)15 b(lemma,)g(see)g([1].)0 2629 y Fp(Lemma)i(1.)23 b Fi(If)15 b(the)i(events)e(ar)n(e)h(such)h(that)g(for)f(al)r(l)g Fq(1)d Fl(\024)g Fo(i)f Fl(\024)h Fo(n)p Fi(,)966 2679 y Fn(1)p eop %%Page: 2 2 2 1 bop 0 22 a Fn(2)48 120 y Fq(1.)22 b(Pr\()p Fo(A)207 127 y Fm(i)221 120 y Fq(\))12 b Fl(\024)h Fo(p)p Fi(,)48 174 y Fq(2.)22 b Fo(A)140 181 y Fm(i)170 174 y Fi(is)16 b(indep)n(endent)f(of)i Fq(\()p Fo(A)577 181 y Fm(j)595 174 y Fq(\))613 181 y Fm(j)r Fh(62)p Fm(V)674 186 y Fk(i)688 174 y Fi(,)48 228 y Fq(3.)22 b Fl(j)p Fo(V)146 235 y Fm(i)159 228 y Fl(j)12 b(\024)h Fo(d)p Fi(,)0 297 y(and)j(if)g Fo(ep)p Fq(\()p Fo(d)10 b Fq(+)g(1\))i Fo(<)h Fq(1)j Fi(then)g(none)g(of)g(the)h(events)e Fo(A)927 304 y Fm(i)941 297 y Fi(,)h Fo(i)d Fq(=)g(1)p Fo(;)8 b(:)g(:)g(:)t(;)g(n)p Fi(,)16 b(o)n(c)n(curs)g(with)h(p)n(ositive)e(pr)n(ob)n(ability.)0 384 y Fq(2.2.)25 b Fp(Azuma's)17 b(inequalit)o(y.)23 b Fq(If)16 b(\()p Fo(Y)663 391 y Fm(i)677 384 y Fq(\))g(b)q(e)g(a)g(sequence)h(of)e (indep)q(enden)o(t)k(random)c(v)m(ariables)i(with)f(the)g(same)0 438 y(distribution)j(on)f Fl(f)p Fq(0)p Fo(;)8 b Fq(1)p Fl(g)p Fq(,)15 b Fo(p)i Fq(=)f(Pr\()p Fo(Y)641 445 y Fm(i)672 438 y Fq(=)g(1\);)i(The)g(result)g(of)f(successiv)o(e)h(coin)g(tossings)g(is)g(a) f(go)q(o)q(d)g(mo)q(del)i(for)0 493 y(this)g(sequence)h(of)f(random)f(v)m (ariables.)32 b(It)19 b(is)g(w)o(ell)h(kno)o(wn)f(that)f(the)h(time)g(a)o(v)o (erages)1555 475 y Fn(1)p 1554 482 22 2 v 1554 508 a Fm(n)1587 459 y Fj(P)1635 472 y Fm(n)1635 506 y(i)p Fn(=1)1702 493 y Fo(Y)1728 500 y Fm(i)1761 493 y Fq(con)o(v)o(erges)0 547 y(exp)q(onen)o (tially)e(fast)e(to)f Fo(p)h Fq(as)g Fo(n)e Fl(!)g Fq(+)p Fl(1)p Fq(.)21 b(Rigourously)l(,)16 b(this)f(is)h(Cherno\013)t('s)e(b)q(ound)606 669 y(Pr)663 591 y Fj( )699 589 y(\014)699 616 y(\014)699 644 y(\014)699 671 y(\014)699 698 y(\014)721 638 y Fq(1)p 719 658 28 2 v 719 700 a Fo(n)781 612 y Fm(n)759 625 y Fj(X)763 723 y Fm(i)p Fn(=1)832 669 y Fo(Y)858 676 y Fm(i)882 669 y Fl(\000)d Fo(p)951 589 y Fj(\014)951 616 y(\014)951 644 y(\014)951 671 y(\014)951 698 y(\014)979 669 y Fo(>)i(a)1051 591 y Fj(!)1099 669 y Fo(<)g Fq(2)p Fo(e)1191 650 y Fh(\000)p Fm(a)1237 638 y Fg(2)1254 650 y Fm(=)p Fn(3)p Fm(np)1331 669 y Fo(;)0 799 y Fq(it)20 b(sa)o(ys)e(basically)j(that)e(with)h(high)g(probabilit)o(y)h([)p Fo(p=a)976 783 y Fn(2)995 799 y Fq(])e(coin)h(tossings)f(are)g(su\016cien)o (t)h(to)f(get)g(an)g(estimate)0 853 y(of)f Fo(p)f Fq(with)i(an)f(accuracy)g (of)f(the)h(order)g(of)g Fo(a)p Fq(.)28 b(This)19 b(kind)g(of)e(result)i(has) f(b)q(een)h(extended,)g(for)f(indep)q(enden)o(t)0 907 y(v)m(ariables,)e(to)f (the)g(case)g(of)g(arbitrary)g(distributions,)h(i.e.,)f(not)g(only)h(with)f (v)m(alues)i(in)f Fl(f)p Fq(0)p Fo(;)8 b Fq(1)p Fl(g)p Fq(,)13 b(as)i(long)g(as)g(they)0 961 y(ha)o(v)o(e)g(an)g(exp)q(onen)o(tial)i(momen)o (t.)i(This)d(is)f(a)g(part)g(of)g(large)g(deviations)h(theory)l(,)f(see)g([2) o(].)50 1015 y(Another)g(p)q(ossible)i(generalization)f(is)g(to)e(consider)i (the)g(case)f(where)g(instead)h(of)f(the)g(sum)g(of)g(indep)q(enden)o(t)0 1069 y(v)m(ariables,)f(one)e(lo)q(oks)h(at)e(some)h(functional)i Fo(X)h Fq(of)d(some)g(arbitrary)g(random)f(v)m(ariables)j Fo(Y)1546 1076 y Fn(1)1566 1069 y Fo(;)8 b(:)g(:)g(:)d(;)j(Y)1694 1076 y Fm(n)1729 1069 y Fq(with)13 b(v)m(alues)0 1123 y(in)h Fl(f)p Fq(0)p Fo(;)8 b Fq(1)p Fl(g)p Fq(.)18 b(Azuma's)13 b(inequalit)o(y)i(sa)o(ys) e(that)f(if)i(the)g(conditional)h(exceptions)f(of)f Fo(X)k Fq(with)d(resp)q(ect)g(to)e Fo(Y)1788 1130 y Fn(1)1809 1123 y Fo(;)c(:)g(:)g(:)t(;)g(Y)1936 1130 y Fm(i)0 1177 y Fq(do)j(not)g(jump)h (sharply)f(as)g Fo(i)g Fq(go)q(es)g(from)g(1)g(to)f Fo(n)p Fq(,)i(then)g Fo(X)i Fq(is)e(concen)o(trated)f(around)g(its)h(a)o(v)o(erage)e (v)m(alue,)j(formally)l(,)0 1264 y Fp(Prop)q(osition)19 b(1.)j Fi(If)16 b(for)g(e)n(ach)h Fo(i)12 b Fl(\024)h Fo(n)p Fi(,)215 1347 y Fq(max)129 1380 y Fm(y)146 1385 y Fg(1)164 1380 y Fm(;:::)o(;y)230 1385 y Fk(i)p Fg(+1)282 1380 y Fh(2f)p Fn(0)p Fm(;)p Fn(1)p Fh(g)393 1347 y Fl(j)p Fo(E)s Fq(\()p Fo(X=)s(Y)551 1354 y Fn(1)581 1347 y Fq(=)g Fo(y)651 1354 y Fn(1)671 1347 y Fo(;)8 b(:)g(:)g(:)d(;)j(Y)799 1354 y Fm(i)825 1347 y Fq(=)13 b Fo(y)895 1354 y Fm(i)910 1347 y Fo(;)8 b(Y)957 1354 y Fm(i)p Fn(+1)1028 1347 y Fq(=)13 b Fo(y)1098 1354 y Fm(i)p Fn(+1)1157 1347 y Fq(\))d Fl(\000)h Fo(E)s Fq(\()p Fo(X=)s(Y)1376 1354 y Fn(1)1406 1347 y Fq(=)i Fo(y)1476 1354 y Fn(1)1496 1347 y Fo(;)8 b(:)g(:)g(:)d(;)j(Y) 1624 1354 y Fm(i)1650 1347 y Fq(=)13 b Fo(y)1720 1354 y Fm(i)1734 1347 y Fq(\))p Fl(j)f(\024)h Fo(c)1845 1354 y Fm(i)1859 1347 y Fo(;)-1872 b Fq(\(1\))0 1458 y Fi(then)637 1568 y Fq(Pr)7 b(\()p Fl(j)p Fo(X)13 b Fl(\000)d Fo(E)s Fq(\()p Fo(X)t Fq(\))p Fl(j)g Fo(>)j(a)p Fq(\))g Fl(\024)g Fq(2)p Fo(e)1153 1532 y Fh(\000)1222 1518 y Fk(a)1239 1508 y Fg(2)p 1185 1524 109 2 v 1185 1550 a(2)1206 1532 y Ff(P)1235 1542 y Fk(n)1235 1563 y Fg(1)1262 1550 y Fk(c)1276 1542 y Fg(2)1276 1563 y Fk(i)1300 1568 y Fo(:)50 1655 y Fq(Azuma's)h(inequalit)o(y)j(is)e(surprisingly)i(sharp) e(considering)i(the)e(w)o(eak)f(h)o(yp)q(otheses)h(of)g(the)g(prop)q (osition.)20 b(In)0 1709 y(the)15 b(indep)q(enden)o(t)j(case,)d(for)f Fo(X)i Fq(=)616 1675 y Fj(P)664 1688 y Fm(n)664 1722 y Fn(1)695 1709 y Fo(Y)721 1716 y Fm(i)735 1709 y Fq(,)f(condition)h(\(1\))f(is)g (satis\014ed)h(with)f Fo(c)1379 1716 y Fm(i)1406 1709 y Fq(=)e(1,)h(hence)i (the)g(inequalit)o(y)g(is)0 1763 y(in)g(this)g(case,)628 1885 y(Pr)684 1807 y Fj( )720 1805 y(\014)720 1832 y(\014)720 1860 y(\014)720 1887 y(\014)720 1914 y(\014)742 1854 y Fq(1)p 740 1874 28 2 v 740 1916 a Fo(n)802 1828 y Fm(n)780 1842 y Fj(X)784 1939 y Fm(i)p Fn(=1)853 1885 y Fo(Y)879 1892 y Fm(i)904 1885 y Fl(\000)10 b Fo(p)972 1805 y Fj(\014)972 1832 y(\014)972 1860 y(\014)972 1887 y(\014)972 1914 y(\014)1000 1885 y Fo(>)j(a)1072 1807 y Fj(!)1120 1885 y Fo(<)g Fq(2)p Fo(e)1212 1866 y Fh(\000)1244 1852 y Fe(\000)p Fk(a)1285 1842 y Fg(2)p 1245 1858 59 2 v 1257 1879 a(2)p Fk(n)1310 1885 y Fo(;)0 2009 y Fq(whic)o(h)j(is)g(v)o(ery)f(close) g(to)g(Cherno\013)t('s)f(b)q(ound.)757 2131 y(3.)26 b Fp(Graph)17 b(colouring)50 2212 y Fq(W)l(e)i Fi(c)n(olour)25 b Fq(a)19 b(graph)g Fo(G)g Fq(suc)o(h)h(that)f(ev)o(ery)g(pair)h(of)f(adjacen)o(t)g(v)o (ertices)h(receiv)o(e)g(di\013eren)o(t)g(colours.)33 b(The)0 2266 y Fi(chr)n(omatic)17 b(numb)n(er)j Fq(of)14 b Fo(G)p Fq(,)h(noted)g Fo(\037)p Fq(\()p Fo(G)p Fq(\))g(is)g(the)h(minim)o(um)g(n)o(um)o(b)q(er)f (of)g(colours)g(required)i(to)d(colour)i Fo(G)p Fq(.)j(It)c(is)0 2320 y(easy)g(to)g(see)g(that,)f(if)i(\001\()p Fo(G)p Fq(\))e(denotes)h(the)h (maximal)f(degree)h(of)f Fo(G)p Fq(,)f(then)i Fo(\037)p Fq(\()p Fo(G)p Fq(\))c Fl(\024)h Fq(\001\()p Fo(G)p Fq(\))c(+)h(1.)50 2374 y(W)l(e)16 b(can)h(obtain)f(go)q(o)q(d)g(b)q(ounds)i(for)d Fo(\037)p Fq(\()p Fo(G)p Fq(\))h(for)g(certain)h(t)o(yp)q(es)f(of)g(graphs,)g (as)g(explained)i(in)f([4].)23 b(F)l(or)15 b(\014xed)0 2428 y Fo(")f(>)g Fq(0,)i(w)o(e)f(sa)o(w)g(that)h(a)f(v)o(ertex)h Fo(v)h Fq(is)g Fo(")p Fi(-sp)n(arse)i Fq(if)d(the)g(subgraph)g(induced)i(b)o (y)e Fo(N)1422 2435 y Fm(v)1442 2428 y Fq(,)g(the)g(neigh)o(b)q(ourho)q(o)q (d)h(of)f Fo(v)r Fq(,)0 2488 y(has)f(at)g(most)f(\(1)9 b Fl(\000)i Fo(")p Fq(\))388 2466 y Fn(\001\(\001)p Fh(\000)p Fn(1\))p 388 2477 132 2 v 445 2504 a(2)539 2488 y Fq(edges.)20 b(A)c(graph)f(is)g Fo(")p Fi(-sp)n(arse)k Fq(if)c(eac)o(h)h(of)e(its)i(v)o(ertices)f(is)h Fo(")p Fq(-sparse.)0 2575 y Fp(Theorem)h(1.)22 b Fi(F)m(or)14 b Fq(\001)g Fi(su\016ciently)f(lar)n(ge,)h(if)g Fo(G)g Fi(has)g(maximum)i(de) n(gr)n(e)n(e)d Fq(\001)h Fi(and)g Fo(G)g Fi(is)f Fo(")p Fi(-sp)n(arse,)i (then)e Fo(\037)p Fq(\()p Fo(G)p Fq(\))g Fl(\024)0 2629 y Fq(\(1)d Fl(\000)g Fo("=)p Fq(2)p Fo(e)184 2612 y Fn(6)203 2629 y Fq(\)\001)p Fi(.)p eop %%Page: 3 3 3 2 bop 1932 22 a Fn(3)50 120 y Fq(Let)15 b(us)g(indicate)i(a)d(rough)h(pro)q (of)f(of)h(this)g(theorem.)20 b(In)15 b(a)g(\014rst)g(step,)f(w)o(e)h (construct)g(a)f(partial)i(colouring)f Fl(C)0 174 y Fq(of)f Fo(G)g Fq(suc)o(h)h(for)f(eac)o(h)h(v)o(ertex)f Fo(v)r Fq(,)g(the)g(n)o(um)o (b)q(er)h(of)f(neigh)o(b)q(ours)i(of)e Fo(v)i Fq(whic)o(h)f(are)f(coloured)i (exceeds)f(the)g(n)o(um)o(b)q(er)0 228 y(of)g(colours)g(app)q(earing)h(on)f Fo(N)517 235 y Fm(v)552 228 y Fq(b)o(y)h(at)e(least)800 210 y Fm(")p 782 217 52 2 v 782 245 a Fn(2)p Fm(e)816 236 y Fg(6)839 228 y Fq(\001)c(+)g(1.)50 288 y(F)l(rom)15 b(this,)i(w)o(e)f(complete)h(the)g (colouring)g(of)f Fl(C)j Fq(to)c(a)1004 251 y Fj(\000)1024 288 y Fq(1)10 b Fl(\000)1125 270 y Fm(")p 1108 277 V 1108 305 a Fn(2)p Fm(e)1142 295 y Fg(6)1164 251 y Fj(\001)1192 288 y Fq(\001-colouring)18 b(of)e Fo(G)g Fq(in)h(a)f(greedy)g(manner:)0 342 y(W)l(e)j(colour)h(the)g(remaining)g(v)o(ertices)g(one)f(at)g(a)g(time.) 33 b(When)19 b(w)o(e)g(come)h(to)e(colour)i Fo(v)r Fq(,)g(there)f(m)o(ust)g (b)q(e)h(an)0 396 y(a)o(v)m(ailable)g(colour:)27 b(Since)21 b Fo(v)f Fq(has)e(at)g(most)g(\001)h(neigh)o(b)q(ours)g(\(this)g(is)g(where)g (the)g(sparseness)g(comes)f(in\),)i(the)0 450 y(n)o(um)o(b)q(er)c(of)e (colours)i(app)q(earing)g(in)g Fo(N)673 457 y Fm(v)708 450 y Fq(is)g(b)q(ounded)g(b)o(y)796 534 y(\001)10 b Fl(\000)890 484 y Fj(\020)943 503 y Fo(")p 922 524 64 2 v 922 565 a Fq(2)p Fo(e)966 552 y Fn(6)990 534 y Fq(\001)g(+)h(1)1107 484 y Fj(\021)1141 534 y Fo(:)0 627 y Fq(Hence)16 b(few)o(er)f(than)360 590 y Fj(\000)381 627 y Fq(1)10 b Fl(\000)482 609 y Fm(")p 464 616 52 2 v 464 644 a Fn(2)p Fm(e)498 634 y Fg(6)520 590 y Fj(\001)549 627 y Fq(\001)15 b(colours)g(app)q(ear)h(in)g(its)f(neigh)o(b)q(ourho)q(o)q (d.)50 681 y(Let)f(us)h(come)f(bac)o(k)h(to)f(the)g(construction)h(of)f Fl(C)s Fq(.)19 b(W)l(e)c(\014rst)f(assign)g(eac)o(h)h(v)o(ertex)f(of)g Fo(G)g Fq(a)g(uniformly)h(random)0 735 y(colour)k(from)e Fl(f)p Fq(1)p Fo(;)8 b Fq(2)p Fo(;)g(:)g(:)f(:)t(;)h Fl(d)p Fq(\001)p Fo(=)p Fq(2)p Fl(eg)p Fq(.)28 b(If)18 b(t)o(w)o(o)f(adjacen)o(t)h(v)o (ertices)g(ha)o(v)o(e)g(the)h(same)f(colour,)g(w)o(e)g(uncolour)h(them.)0 789 y(The)c(resulting)i(partial)e(colouring)h(yields)h Fl(C)s Fq(.)50 843 y(The)e(\014rst)f(thing)h(to)f(sho)o(w)g(is)h(that)f Fl(C)j Fq(is)f(not)e(to)q(o)g(small,)h(whic)o(h)g(is)h(rather)e(easy)l(.)19 b(Then)c(w)o(e)g(m)o(ust)f(study)l(,)h(for)0 897 y(v)o(ertex)i Fo(v)r Fq(,)g(the)h(random)e(v)m(ariable)j Fo(Z)647 904 y Fm(v)685 897 y Fq(whic)o(h)f(coun)o(ts)f(the)h(n)o(um)o(b)q(er)f(of)g(pairs)h(of)f(v)o (ertices)h(in)g Fo(N)1691 904 y Fm(v)1728 897 y Fq(whic)o(h)g(ha)o(v)o(e)0 951 y(the)d(same)f(colour)h(in)g Fl(C)s Fq(.)k(It)c(can)g(b)q(e)g(sho)o(wn)f (that)g(since)i Fo(G)e Fq(is)h(sparse,)f(the)h(exp)q(ectation)g(of)f Fo(Z)1625 958 y Fm(v)1660 951 y Fq(is)h(greater)f(than)0 1005 y Fo(")p Fq(\001)p Fo(=e)103 988 y Fn(4)123 1005 y Fq(.)50 1059 y(No)o(w)f(that)g(w)o(e)g(ha)o(v)o(e)g(pro)o(v)o(ed)g(that)g(man)o(y)g (v)o(ertices)h(in)g Fo(N)1033 1066 y Fm(v)1067 1059 y Fq(are)f(coloured,)h(w) o(e)g(m)o(ust)f(sho)o(w)g(that)f Fo(Z)1749 1066 y Fm(v)1783 1059 y Fq(do)q(es)i(not)0 1113 y(di\013er)h(to)q(o)f(m)o(uc)o(h)h(from)f(its) h(exp)q(ected)h(v)m(alue.)21 b(Once)16 b(this)g(is)f(done,)g(w)o(e)f(use)i (the)f(Lo)q(cal)g(Lemma)g(to)f(pro)o(v)o(e)h(that)0 1167 y Fi(every)20 b Fq(v)o(ertex)d(will)h(ha)o(v)o(e)e(suc)o(h)h(a)f(prop)q(ert)o (y)l(,)g(th)o(us)h(pro)o(ving)f(the)h(prop)q(ert)o(y)f(on)g Fl(C)s Fq(.)24 b(By)17 b(a)f(tec)o(hnical)i(argumen)o(t)0 1220 y(replacing)f Fo(Z)226 1227 y Fm(v)262 1220 y Fq(with)g(a)e(more)h(amenable)g (quan)o(tit)o(y)l(,)g(Azuma's)f(Inequalit)o(y)j(is)e(used)g(to)g(pro)o(v)o(e) f(the)h(assumption)0 1274 y(on)e Fo(Z)93 1281 y Fm(v)113 1274 y Fq(.)19 b(Roughly)c(sp)q(eaking,)f(the)g(idea)h(is)f(that)f(a)g(colouring)h (of)g Fo(v)h Fq(should)f(not)g(in\015uence)h(the)f(colouring)h(of)e(the)0 1328 y(other)i(parts)f(of)h Fl(C)s Fq(,)f(since)j Fo(G)e Fq(is)g(sparse.)863 1416 y Fd(References)0 1489 y Fc([1])k(Alon)f(\(Noga\))f(and)h(Sp)q(encer)h (\(Jo)q(el)e(H.\).)g({)g Fb(The)g(pr)n(ob)n(abilistic)d(metho)n(d)p Fc(.)i({)h(John)h(Wiley)h(&)e(Sons)h(Inc.,)g(New)f(Y)m(ork,)h Fa(1992)p Fc(,)60 1534 y Fb(Wiley-Interscie)o(nc)m(e)11 b(Series)h(in)h (Discr)n(ete)f(Mathematics)g(and)g(Optimization)p Fc(,)e(xvi+254p.)0 1580 y([2])19 b(Dem)o(b)q(o)12 b(\(Amir\))g(and)g(Zeitouni)i(\(Ofer\).)d({)h Fb(L)n(ar)n(ge)g(deviation)o(s)e(te)n(chniques)f(and)i(applic)n(ation)o(s)p Fc(.)d({)k(Jones)g(and)g(Bartlett)h(Publish-)60 1626 y(ers,)f(Boston,)i(MA,)e Fa(1993)q Fc(,)h(xiv+346p.)0 1671 y([3])19 b(Karp)e(\(Ric)o(hard)h(M.\).)e({) h(Reducibili)q(t)o(y)j(among)d(com)o(binatorial)j(problems.)e(In)f Fb(Complexity)e(of)i(Computer)f(Computations)p Fc(.)60 1717 y(pp.)f(85{103.)g({)g(New)g(Y)m(ork,)g Fa(1972)q Fc(.)f(Pro)q(ceedings)j(of)e (a)g(Symp)q(osium)i(held)f(at)f(IBM)g(Thomas)g(J.)g(W)m(atson)g(Researc)o(h)h (Cen)o(ter,)60 1763 y(Y)m(orkto)o(wn)d(Heigh)o(ts,)g(N.Y.,)f(1972.)0 1808 y([4])19 b(Mollo)o(y)c(\(M.\))d(and)i(Reed)f(\(B.\).)g({)g(Graph)g (colouring)j(via)e(the)f(probabilisti)q(c)j(metho)q(d.)d({)g(April)i Fa(1997)p Fc(.)e(Preprin)o(t.)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF