ButlletídelaSocietatCatalanadeMatemàtiques Vol.28,núm.1,2013.Pàg.87–115. DOI:10.2436/20.2002.01.48 Endre Szemerédi, Premi Abel 2012 GáborLugosiiOriolSerra Resum: Aquestarticlepresentaunabreudescripciódelescontribucionsmatemàti- quesmésdestacadesd’EndreSzemerédi,PremiAbel2012. Paraules clau:teoremadeSzemerédi,lemaderegularitat,teoriaextremaldegrafs, teoriadeRamsey,algorismesd’ordenació. ClassificacióMSC2010:01A65,05-02,11-02. 1 Introducció Elpassat21demarçde2012,elpresidentdel’AcadèmiaNoruegadeCiènciesi Lletres,NilsChristianStenseth,vaanunciarelguanyadordel’edició2012del PremiAbel,consideratcomlamàximadistinciócientíficaenmatemàtiquesi queestàdotatambunmiliódedòlars.Elguardóvaseratorgatalmatemàtic hongarèsEndreSzemerédi,membredelRényiAlfrédMatematikaiKutatóintézet (InstitutdeMatemàtiquesAlfrédRényi)deBudapestiprofessoralaUniversitat deRutgers,NovaJersey,EstatsUnits. Lacitaciódelpremidiu: Per les seves contribucions fonamentals a la matemàtica discreta i a les ciènciesdelacomputacióienreconeixementdel’impacteprofundidurador d’aquestescontribucionsalateoriaadditivadenombresialateoriaergòdica. UndelsresultatsméscelebratsdeSzemerédiéselteoremaqueportaelseu nom,sobrel’existènciadeprogressionsaritmètiquesenconjuntsd’entersde densitatpositiva.LacontribuciófonamentaldeSzemerédi,però,consisteixmés aviatenunamaneraoriginalipeculiardepensarlesmatemàtiques.Aixíhova posardemanifestelmembredelcomitèdelPremiAbel,TerenceTao[59],en rebrelamedallaFieldsl’any2006amblesparaulessegüents: Aquestarticleésunaversióactualitzadadelquevaaparèixerencastellà,ambelmateixtítol,a LaGacetadelaRealSociedadMatemáticaEspañola,vol.15(2012),núm.3,pàg.537–559. 88 GáborLugosiiOriolSerra EndreSzemerédi1 UnteoremafamósdeSzemerédiafirmaquequalsevolconjuntd’entersamb densitatpositivacontéprogressionsaritmètiquesarbitràriamentllargues.Hi ha diverses demostracions d’aquest teorema profund, però totes elles estan basadesenunadicotomiafonamentalentreestructuraialeatorietat,cosaque portaaladescomposiciódequalsevolobjecteenunacomponentestructuradai unacomponentaleatòria. Convertiraquestprincipigenèricenuninstrumenteficaç,delqualespuguin derivarresultatsprecisosambsentitmatemàtic,ésunadelescontribucions cabdals de Szemerédi. El valor d’aquesta contribució per a la història de les matemàtiques i les ciències de la computació és el que ha estat objecte de màximreconeixement,afegintelseunomalallistadelsonzedestacadíssims matemàticsquehanrebutelPremiAbelfinsavui. Endre Szemerédi és autor de més de dos-cents articles, la majoria dels qualshantingutunimpacteprofundenlainvestigaciómatemàticadelsdarrers cinquantaanys,ielseuritmedetreballsegueix,alssetanta-dosanys,enplena activitat. L’objectiud’aquestarticleésaproparellectoraalgunesdelescontribucions méssignificativesd’EndreSzemerédi,iestàorganitzatcomsegueix. Comencemalasecció2ambelteoremadeSzemerédi quejahemmencionat. LademostraciódeSzemerédid’aquestteoremasegueixsentconsideradacom undelsexercicisméssofisticatsderaonamentcombinatoridelahistòriade les matemàtiques. En aquesta demostració hi ha el germen de l’anomenat 1FotografiagentilmentcedidaperFrancescCreixell,iqueapareixeràenelprojectefotogràfic Abstractminds. EndreSzemerédi,PremiAbel2012 89 lema de regularitat de Szemerédi, que està considerat com una de les seves contribucionsmésimportants.Ellemaderegularitats’haconsolidatcomun potentinstrumentd’anàlisiambnombrosesaplicacions,ihaestatanalitzatdes demoltdiversesperspectives,algunesdelesqualsestractenalasecció3. Unadelesconseqüènciesdellemaderegularitatésl’anomenatlemad’elimi- nació,queproporcionademostracionsméssimplesdelteoremadeSzemerédi, unadelesqualss’incloualasecció4. Ellemaderegularitats’enunciahabitualmentenelllenguatgedelateoriade grafs,iésenaquestcontextenelqualestrobenalgunesdelessevesaplicacions mésnaturals.Lasecció5recullalgunesdelescontribucionsdeSzemerédien aquestaàrea.UnadelespassionsmatemàtiquesdeSzemerédi,querevelala influènciadelseumestreiamicPálErdo˝s,éslateoriacombinatòriadenombres. Alasecció6esdescriuenalgunesdelescontribucionsdeSzemerédienaquesta àreamésenllàdelteoremaqueportaelseunom.Enrelacióambunad’aquestes contribucionsmencionemtambéundelsresultatsméscèlebresdeSzemerédia lageometriadiscreta,elteoremadeSzemerédi-Trotter. A continuació, la secció 7 tracta una de les contribucions més significa- tives de Szemerédi a la teoria de Ramsey: la determinació dels nombres de RamseyR(3,n).DelesdiversescontribucionsdeSzemerédialainformàtica teòricatractaremalasecció8lasevaaportacióalproblemadelsalgorismes d’ordenació,quevacontribuiralnaixementdelsprincipisdedesaleatorització . d’algorismesprobabilísticsiamètodesdeparallelitzaciód’algorismes. Acabarem aquest recorregut amb una aproximació biogràfica i humana a Szemerédi,iamblesrelacionsqueeldarrerguardonatambelPremiAbelha mantingutambelnostrepaís. 2 Progressions aritmètiques Als anys vint del segle XX Göttingen era un dels centres de la investigació matemàticaeuropea,iatreiamoltsdelsmatemàticsquevanmarcarlahistòria delaprimerameitatdelsegle.Undelsvisitantsal’estiudel1928vasereljove VanderWaerden,quealeshoresvatenirconeixementd’unproblemad’enunciat . simple que estava desafiant els esforços dels matemàtics més illustres que hihaviaaGöttingen.Estractavadeprovarquequalsevolparticiódelsenters en un nombre finit de parts en conté una amb progressions aritmètiques arbitràriament llargues. Van der Waerden va aconseguir una prova d’aquest . resultatqueesconeixavuiambelteoremaqueportaelseunom.L’excellent articled’IgnasiMundet[42],publicatenaquestButlletí,estàdedicataaquest resultatialseufecunddesenvolupamentfinsalsnostresdies. ElteoremadeVanderWaerdenésundelsresultatsbàsicsdel’anomenada teoria de Ramsey aritmètica. Aquesta denominació es fa en relació amb el teoremadeRamsey,l’enunciatdelqualespotresumirdeformaimprecisadient quequalsevolparticiófinitad’unaestructuraprougran(oinfinita)contéenuna delespartsunasubestructuradonada.Elteoremaoriginalquedónanomala teoriavaserprovatperun(altre)matemàticpeculiar,FrankPlumptonRamsey, 90 GáborLugosiiOriolSerra el1930(vegeuperexemple[9]peraunahistòriadelateoriadeRamseyidel personatgequelavainiciar).PálErdo˝siGyörgySzekeresvanprovarpocdesprés un resultat equivalent el 1935 i, de fet, el desenvolupament de la teoria de RamseyvaserimpulsatsobretotperErdo˝s.NoésestranyqueErdo˝s,interessat fonamentalment en la teoria de nombres, relacionés el teorema de Van der Waerdenamblavellaqüestiósobrel’existènciadeprogressionsaritmètiques denombresprimers. Com havia fet amb altres problemes aritmètics, Erd˝os va enfocar aquest problemacentrant-semésenpropietatsqualitativesgeneralsqueenlespro- pietatsaritmètiquesdelsconjuntsdenombressobreelsqualsesplantejaven lespreguntes,fossinquadrats,potènciesonombresprimers.Comunprimer pas, Erd˝os i Turán van conjecturar el 1936 que l’existència d’una progressió aritmètica de llargada k en un conjunt d’enters està assegurada simplement perraonsdedensitat:qualsevolconjuntd’entersambdensitatpositivahade contenirunaprogressióaritmèticadellargadak.Aquílamesuradedensitat d’unconjuntAd’entersés |A∩[1,n]| limsup , n→∞ n és a dir, el límit superior de la proporció d’enters a A dins d’intervals de la forma[1,n].Aquestvalors’anomena,tècnicament,ladensitatsuperior deA.El teoremadeVanderWaerdenésunaconseqüènciad’aquestaconjectura,jaque enunaparticiófinitadelsenters,almenysunadelespartshadetenirdensitat positiva. Vintanysdesprésd’haverestatformulada,KlausRothvaobtenirelprimer resultatpositiudelaconjecturad’Erdo˝s-Turánperaprogressionsdellargada3. Roth va fer servir una versió del mètode del cercle de Hardy i Littlewood, combinat amb una idea que també faria servir més endavant Szemerédi: el resultat és trivialment cert per a conjunts de densitat gran, pròxima a 1. Es tractad’analitzaraleshoresladensitatmàximaenlaqualpodriahaver-hiuncon- traexemplealaconjecturaiarribaraunacontradiccióveientqueelpossible contraexemplehauriadetenirunadensitatestrictamentmésgransobrealguna progressióaritmètica.L’úsdel’anàlisideFourierlimitava,enaquellmoment, l’aplicaciódelmètodeaprogressionsdellargadamésgranque3. Szemerédivaestendreprimer,el1969,elteoremadeRothaprogressions aritmètiquesdellargada4fentservirmètodescombinatoris.Sisanysméstard, el1975,enunasessióplenadegomagomalColloquedeThéoriedeGraphes et Combinatoire a Marsella, i amb un títol críptic, On certain sets of integers, EndreSzemerédivapresentarlademostraciódelaconjecturad’Erd˝os-Turán peraprogressionsdellargadakarbitrària,queesconeixavuicomateorema deSzemerédi. Teorema1(teoremadeSzemerédi). Qualsevolconjuntd’entersambdensitat superiorpositivacontéinfinitesprogressionsaritmètiquesdellargadakpera cadanombrenaturalk. EndreSzemerédi,PremiAbel2012 91 Erd˝osacostumavaaoferirrecompensespelsproblemesqueproposava,i elpreuquehidonavasuggerialadificultatdelproblema.Peralaconjectura d’Erdo˝s-Turánhaviaofertlarespectablequantitatde1.000$.Arribatelmoment, lessevesdificultatsfinancereslivanpermetrepagarnoméslameitatdel’import que havia promès. Tot i això, aquest va ser l’import més gran que Erd˝os va haverdepagarmaiperlasoluciód’algundelsseusproblemes. La demostració de Szemerédi del teorema que porta el seu nom segueix sentconsideradaunaobramestraderaonamentcombinatori.Eldiagramaque acompanyal’articleonespresentalademostració[53]iqueesreprodueixala figura1,dónaunaideadelacomplexitatdelraonament. Figura1:Diagramaqueexpressaelfluxdelademostració,inclòsa[53, pàg.202]perguiarellector. Undelselementsdelademostracióqueesvaconvertirdesprésenunaeina bàsicaendiversosàmbits,incloentlateoriadegrafs,lateoriadecomputació,la teoriadenombresolageometriadiscreta,ésellemaderegularitatdeSzemerédi. A la secció 3 es descriu l’enunciat i algunes aplicacions d’aquest lema i a la secció 4 s’indica la seva aplicació per obtenir una demostració directa del teoremadeRothperaprogressionsdellargada3. LacomplexitatdelademostracióoriginaldelteoremadeSzemerédivaser probablementundelsestímulsquevananimaraltresmatemàticsaexplorar 92 GáborLugosiiOriolSerra demostracions alternatives del teorema. De manera sorprenent, Hillel Furs- tenberg[22]vaobtenirpocdesprés,el1977,unademostraciódelteoremade Szemerédibasadaenlateoriaergòdica.ElteoremaderecurrènciadeFursten- bergdiuque,donatunespaideprobabilitat(X,B,µ)iunenterpositiuk,pera cadaoperadorinvertibleT queconservalamesuraicadaconjuntAdemesura positivahihainfinitsnombresnaturalsnperalsquals µ(A∩TnA∩T2nA∩···∩T(k−1)nA)>0. Furstenbergvaprovarqueaquestenunciatéslògicamentequivalentalteorema deSzemerédiatravésdelqueavuis’anomenaelprincipidetransferènciade Furstenberg, que introdueix una topologia en el conjunt de nombres enters i associa a cada conjunt d’enters de densitat positiva un conjunt de mesura positivaenuncertespaideprobabilitat. Aquesta aproximació al teorema de Szemerédi va resultar extremament fructíferaivapermetreobtenirextensionsdelteoremaque,finsmoltméstard, novanteniraltrademostracióquelaqueproporcionavalateoriaergòdica.Per exemple,FurstenbergiKatznelson[23]vanobtenirlaversiómultidimensional delteoremadeSzemerédi: Teorema2(teoremadeSzemerédid-dimensional). Siguin v ,...,v ∈ Nd 1 k kvectorsd-dimensionalsdecoordenadesenteres.PeracadaconjuntAdedensitat superiordeBanachpositivaaNd hihainfinitesparelles(a,r)∈Nd×Ntalsque elselementsa+rv ,...,a+rv estantotsdinsdelconjuntA. 1 k El teorema de Szemerédi es redueix al cas d = 1 i v = i−1, i = 1,...,k. i L’impuls que va donar el teorema de Szemerédi a aquesta connexió amb la teoriaergòdicaestàreflectittambéenlacitaciódelPremiAbel. El 2001 Gowers [25] va obtenir una tercera demostració del teorema de Szemerédiatravésdel’anàlisideFourier,ivaestendreaixíelcamíiniciatper Roth cinquanta anys abans. Amb aquesta finalitat Gowers va introduir eines innovadoresenl’anàlisideFourierclàssic,comlesqueavuis’anomenennormes deGowers,combinadesambnoveseinescombinatòries,comunaversiórefinada del teorema de Balog i Szemerédi (una altra vegada Szemerédi en acció) que es coneix avui com a teorema de Balog-Gowers-Szemerédi. L’avantatge de la demostraciódeGowersésqueproporcionaelsmillorsresultatsquantitatius sobrelamenordensitatquegaranteixl’existènciadeprogressionsaritmètiques d’unacertallargada.Erd˝osdenotavaperr (n)lamidamàximad’unconjunt k d’entersal’interval[1,n]quenocontéprogressionsaritmètiquesdellargadak. ElteoremadeSzemerédiespotenunciarcom r (n)=o(n) (n→∞) k peraqualsevolenterpositiuk.LademostraciódeGowersdóna n r (n)< , c(k)=2−2k+9, k (loglogn)c(k) EndreSzemerédi,PremiAbel2012 93 que, per a k arbitrari, és la millor fita que es coneix. Per a apreciar el valor d’aquestresultatquantitatiu,calrecordarquelesfitesinvolucradesalademos- traciódelteoremadeVanderWaerdencreixendemaneraastronòmicaambk. Defet,Gowers[24]vaprovarqueaquestcreixementésinevitable,totiquela fitaanteriorredueixl’expressióoriginalendiversosordresdemagnitud. Com era habitual en Erd˝os, un cop provat el teorema de Szemerédi va plantejarelreptesegüentenlamateixadirecció: Conjectura3(Erdo˝s). Siguia <a <··· unasuccessiód’enterstalquela 1 2 sèriedelsseusinversos (cid:88) 1 a i i ésdivergent.Aleshoreslasuccesiócontéprogressionsaritmètiquesarbitrària- mentllargues. Aquestésencaraunproblemaobert,lasolucióafirmativadelqualresoldria laqüestiódel’existènciadeprogressionsaritmètiquesarbtràriamentllargues enlasuccessiódenombresprimers,jaquelasèriedelsinversosdeprimersés divergent.Totiladificultatd’aquestproblema,combinantunaaltravegadales einesproporcionadesperSzemerédiambaltresingredients,GreeniTao[29]van provarel2005elquehaesdevingutelcèlebreteoremadeGreen-Tao:qualsevol subconjuntdedensitatpositivadinselsnombresprimerscontéprogressions aritmètiquesarbitràriamentllargues.Podeutrobarunadescripciódelsingre- . dients del teorema de Green-Tao a l’excellent article de Martin Klazar [33] quevapublicaraquestButlletípocdesprésdefer-sepúblicaquestresultat excepcional. HihaencaraunaquartademostraciódelteoremadeSzemerédidenaturalesa puramentcombinatòriairelacionadaambelseulemaderegularitat.Lesdues seccionssegüentsexpliquenl’enunciatdellemaderegularitat,algunesdeles sevesconseqüènciesilasevarelacióambelteoremadeSzemerédi. 3 El lema de regularitat Ellemaderegularitat deSzemerédi,unadelessevescontribucionsmésimpac- tants,haresultatuninstrumentdemúltiplesaplicacionsendiversesàreesde lesmatemàtiques.Elconjuntdetècniquesassociadesaaquestaeinaconstitueix elques’anomenaavuielmètodederegularitat deSzemerédi.Comellmateix explica,elmètodederegularitatnoésnomésunaeinaespecífica,sinótotauna filosofia per a estudiar problemes discrets amb un nombre gran d’elements. Lafilosofiaesresumeixenlafrase«Enqualsevolcaoshihaunordre»,eltítolde laconferènciaqueEndreSzemerédivadonaral’Institutd’EstudisCatalans(IEC) eljunyde2012.AcontinuacióexpliquemelsignificatqueSzemerédidónaa aquestafrase. 94 GáborLugosiiOriolSerra (cid:3) 27 de juny de 2012 18:30h a la Sala Joan i Pere Coromines Institut d’Estudis Catalans La Societat Catalana de Matemàtiques i el Centre de Recerca Matemàtica es senten molt honorats d’anunciar la conferencia del Fotografia: László Mudra (origo.hu) Professor Endre Szemerédi Premi Abel 2012 De l’Institut de Matemàtiques Alfréd Rény (Acadèmia Hongaresa de Ciències, Budapest) i el Departament d’Informàtica de Rutgers (Universitat Estatal de New Jersey) In Every Chaos There is an Order Summary: The chaos and order will be defined relative to the problems. (1) Arithmetic progressions. This part is connected to a problem of Erdos and Turan from the 1930’s: related to the van der Waerden theorem, they asked if the density version of that result also holds: Is it true that an infinite sequence of integers of positive (lower) density contains arbitrary long arithmetic progressions? The first result in this direction was due to K.F. Roth, who proved that any sequence of integers of positive (lower) density contains a three-term arithmetic progression. We are going to give a short history of the generalization of Roth’s result and give some ideas about the “easiest” proof of Roth’s result. (2) Long Arithmetic progression in subset sums. We are going to give exact bound for the size of longest arithmetic progression in subset sums. In addition, we describe the structure of the subset sums, and give applications in number theory and probability theory. (3) Embedding sparse graphs into large graphs. We are going to describe and illustrate a method to embed relatively sparse graphs into large graphs. This eill include the case of Po’sa’s conjecture, El Zahar’s conjecture, and tree embedding under different conditions. Among others, we shall give several generalizations of the central Dirac Theorem, both for graphs and hypergraphs. The methods are elementary. (cid:3) Figura2:CartellquevaanunciarlaconferènciadeSzemerédial’IECdel 27dejunyde2012. Originalmentellemaderegularitats’expressaenelllenguatgedelateoria degrafs,undelselementsméssimplesdel’universmatemàticjuntamentamb elsconjuntsielsnombres.Recordemqueungraf éssimplementunconjunt de parells d’elements d’un conjunt donat, que expressa una relació binària entreaquestselements.Seguintl’imaginarihabitual,elselementsdelconjunt dereferènciaV s’anomenenvèrtexs ielconjuntE deparells,arestes.Així,un grafésunparellG=(V,E).SiGténvèrtexs,aleshoreselseunombred’arestes (cid:16) (cid:17) éscomamàxim n . 2 El lema de regularitat diu que qualsevol graf prou gran es pot aproximar perungrafquetéunapartestructuradaiunapartaleatòriaenunsentitque espotferprecís. Comencemperconsiderarungrafbipartit;ésadir,ungrafqueadmetuna partició del conjunt de vèrtexs en dues parts, V = A∪B, i en el qual totes les arestes tenen exactament un vèrtex en cadascuna d’aquestes dues parts. Suposem que, per construir el conjunt d’arestes de G = (A∪B,E), escollim cadascun dels parells (a,b) ∈ A×B amb probabilitat p independentment delsaltres.Elnombreesperatd’arestesaG ésp|A|·|B|iladensitatesperada d’arestesdelgrafés |E(G)| p= . |A|·|B| EndreSzemerédi,PremiAbel2012 95 Amés,peraqualsevolparelldesubconjuntsX ⊂AiY ⊂B,ladensitatesperada d’arestesalsubgrafinduïtperaquestssubconjuntséstambé e(X,Y) p= , |X|·|Y| one(X,Y)denotaelnombred’arestesdeG ambunvèrtexaX iunaY. Considerem ara un graf arbitrari G i dos subconjunts disjunts de vèr- texsA,B ⊂V.Ladensitat delparelldesubconjuntsaG esdefineixcom e(A,B) d(A,B)= . |A|·|B| Peraunnombrereal(cid:15)>0fixatdiemqueelparell(A,B)és(cid:15)-regular si ∀X ⊂A, ∀Y ⊂B :|X|≥(cid:15)|A|, |Y|≥(cid:15)|B|, sesatisfà |d(A,B)−d(X,Y)|≤(cid:15). És a dir, la densitat de qualsevol parell (X,Y) de subconjunts prou grans (podríemdirdedensitatpositiva)deAiB difereixmenysque(cid:15)deladensitat del parell (A,B). Els grafs bipartits aleatoris que hem definit abans tenen certamentlapropietatdeser(cid:15)-regularsambaltaprobabilitat.Aixípodemdir queunparell(cid:15)-regularescomportaaproximadamentcomungrafaleatori. L’avantatgedelmodeldelsgrafsaleatorisquehemdefinitéslasimplicitatde lasevaanàlisi,almenysperamoltsdelsproblemesnaturalsenteoriadegrafs. Lesarestesapareixendeformaindependentambprobabilitatfixada,unmodel queenteoriadeprobabilitatesconeixmoltafons.Aquestavantatgeesmanté enelsparells(cid:15)-regularsambungraud’aproximaciódefinitpelparàmetre(cid:15). Ellemaderegularitatdiuque,fixat(cid:15)>0,qualsevol grafprougranadmet unaparticióenunnombrefinitdeparts,lamajoriadelesqualsformenparells (cid:15)-regulars.Mésespecíficament: Teorema4(lemaderegularitat,Szemerédi[54]). Per a cada (cid:15) > 0 i cada número natural m existeixen M = M((cid:15),m) i N = N((cid:15),m) amb la propietat següent. QualsevolgrafG ambn≥N vèrtexsadmetunaparticióV =V ∪···∪V 1 k delconjuntdevèrtexsenunnombrekdepartsquesatisfà m≤k≤M, ambpartsdemidesgairebéiguals |V −V |≤1, i,j =1,...,k, i j talsquetotselsparells(V ,V ),llevatde(cid:15)k2,són(cid:15)-regulars. i j 96 GáborLugosiiOriolSerra Ellemaderegularitatcapturadeformaprecisaunapropietatuniversaldels grafs que permet desenvolupar eines d’anàlisis de gran eficàcia. L’elegància delasevaformulació,enlaquall’aproximacióesdescriuentermesd’unúnic paràmetre(cid:15),ésunexercicidecreativitatqueesreconeixenlamenciódelPremi Abel. Espotdonarunsentitmésprecísallemaderegularitatinterpretant-loen termesdel’aproximabilitatd’ungrafarbitrariperungrafaleatori.Considerem laclasseRdegrafsaleatorisR(v,k,{p , 1≤i<j ≤k})quetenenconjuntde ij vèrtexsV =V ∪···∪V ,uniódisjuntadekconjuntsdemida|V |=v,amb 1 k i arestesescollidesdeformaindependentambprobabilitatp peralsparellsde ij V ×V .Ellemaderegularitatdiuquequalsevolgrafprougranespotaproximar i j ambunnivelldeprecisióarbitrari(donatper(cid:15))perungrafdelaclasseR. Unaprimeraobservacióésquesi{G , n≥1}ésunasuccessiódegrafstals n queG ténvèrtexsio(n2)arestes(perexempleunaquantitatlineald’arestes), n ellemaderegularitatdiusimplementqueelsgrafsdelasuccessiópodenser aproximatspergrafsnuls,ésadir,sensearestes.Enaltresparaules,ellema deregularitatnomésresultaútilperafamíliesdegrafsdensos,ésadir,amb cn2 arestes, una proporció positiva de totes les possibles. El lema també té unenunciattrivialsilespartstenenmida1,jaquealeshorestotselsparells sóntrivialment(cid:15)-regulars(lafamíliadeconjuntsdemidaalmenys(cid:15)|V |queda i reduïdaaV ).Peraixòl’enunciatlimitasuperiormentelnombredeparts. i Lasegonaobservacióésque,entermesquantitatius,elsvalorsdelescons- tantsM iN quegaranteixl’enunciatsónrelativamentpobres.Aixònoésnomés degutaldissenydelademostració,sinóque,comvaprovarGowers[24],lafita ques’obtéperaM ésinevitablementalta,unatorredelaforma222... d’alçada proporcionala(cid:15)−5.Aquestéselpreuquecalpagarperaobtenirunenunciat tanuniversal. Aquestesobservacions,però,noeliminenl’eficàciadellema.Lasevauniver- salitat es manifesta no només en les aplicacions sinó en les connexions que s’estableixenambaltresàreesdelamatemàtica. LovásziSzegedy[40]handesenvolupatunprogramaambiciósenelqualel lemaderegularitatsesituaenlaperspectivadel’anàlisi,idonentresinterpre- tacionsanalítiquesdellemaderegularitat. Desd’aquestaperspectivaesconsideral’espaiW defuncionsmesurables acotadesW: [0,1]2 →R.Peraunapartició{S ,...,S }de[0,1],lesfuncions 1 m de W constants en els rectangles S ×S són funcions esgraonades. Un graf i j s’identificademaneranaturalamblesfuncionsesgraonadesqueprenenvalors a{0,1}associadesaparticionsenlesqualstotselsintervalsS tenenlamateixa i llargada.Esdefineixaleshoreslanorma (cid:12)(cid:90) (cid:12) (cid:12) (cid:12) (cid:107)W(cid:107)(cid:50) = sup (cid:12) W(x,y)dxdy(cid:12) (cid:12) (cid:12) S,T⊂[0,1] S×T aW.Ellemaderegularitat(defetunaversiódèbildellema)espotexpressar aleshoresdelamanerasegüent: