; TeX output 2006.11.06:1553 nu덍html: html:lnhtml: html:6j_src:79L_pHGL.texg G cmmi12Lg cmmi12p!Dt G G cmr17metrics7tontheHeisenqbserggroupand 7the7tGosemans-Linialconjecturelύ H;XQ cmr12JamesR.Lee2!K cmsy8%AssafNaor2y0E src:80L_pHGL.tex3"V
cmbx10Abstractt*`K`y
cmr10W*eUUprovethatthefunction
b>
cmmi10d:
msbm10R^ٓR cmr73S
!",
cmsy108R^3C![0;1)givenbyK%`d` u
cmex10(x;y[;zp);(t;u;v)`Y%=^
#`hpb qDz(t8 x)2S+(u y[ٲ)2|sbiޟ 2p>1+8(v zw+2xu 2y[t)2|s`iH鍒 ٴRZ cmr51 ٴRx W g P2 +8(t x)2S+(u y[ٲ)2|s^E1Ex W g P2K:Sȍ`src:86L_pHGL.texisametriconR^3.suchthat(R^3|s;zPp zP fe 4rd4q)isisometrictoasubsetofHilbGertspace,yet(R^3|s;d)doGes `notadmitabi-LipschitzembGeddingintoL1|s.-Thisyieldsanewsimplecounterexampletothe`GoGemans-LinialmlconjectureontheintegralitymlgapofthesemideniterelaxationoftheSparsest`Cutgproblem.%ThemetricabGovegisdoubling,kandhencehasapaddedstochasticdecomposition`at!everyscale..W*ealsostudytheL 0er cmmi7pversionofthisproblem,Tandobtainacounterexample`toBanaturalgeneralizationofaclassicaltheoremofBretagnolle,FuDacunha-CastelleandKrivine`(ofZ html:98N ff cmbx121LIntros3ductionqsrc:109L_pHGL.texK`y
3
cmr10Let9b>
3
cmmi10G
=(V ;1E )bMeagraph,witha> ':
3
cmti10cpapacityC ȁ(e)
:!",
3
cmsy100assoMciatedtoev!eryedgee2E .Assumethat
w!e}aregivenkpairsofvertices(sz|{Y cmr81;1tz1);:::;(sȮ2 cmmi8k#;tȮk)
2V$Vqand}Dz1;:::l;DȮk.91.