Szemeredis regularitetslemma är ett lemma från allmän grafteori , som säger att hörnen på vilken tillräckligt stor graf som helst kan delas in i ett ändligt antal grupper så att nästan alla tvådelade grafer som förbinder hörn från två olika grupper har kanter fördelade nästan jämnt mellan hörnen. I det här fallet kan det minsta erforderliga antalet grupper i vilka uppsättningen av grafens hörn måste delas upp vara godtyckligt stort, men antalet grupper i partitionen är alltid avgränsat ovanifrån.
På ett informellt sätt hävdar lemma närvaron av ett stort antal stora pseudo-slumpmässiga strukturer i absolut vilken graf som helst av tillräckligt stor storlek.
Lemmat bevisades av Endre Szemeredy 1975. [1] [2]
Låt en tvådelad graf ges vars kanter förbinder hörn från mängden med hörn från mängden .
För vi betecknar med tätheten av fördelningen av kanter mellan dessa uppsättningar, det vill säga,
.
En tvådelad graf kallas -uniform om för någon som uppfyller villkoren ojämlikheten |
Det finns flera definitioner som är likvärdiga med detta (motsvarande i betydelsen att det finns ett monotont beroende i en definition från i en annan när de två definitionerna är likvärdiga), men de använder alla en kvantitet och någon form av kvantitativ jämförelse av dess värden för olika par .
Uppenbarligen är de fullständiga och tomma tvådelade graferna -regelbundna för alla . Det bör noteras att detta generellt sett inte är sant för en godtycklig tvådelad graf som är regelbunden i vanlig mening (som ett motexempel kan vi till exempel betrakta föreningen av flera reguljära grafer som inte skär varandra i mängden av hörn).
-uniforma grafer för en given kallas ibland också pseudo-slumpmässiga , eftersom de liknar slumpmässigt genererade när det gäller den enhetliga fördelningen av kanter mellan hörn.
Szemeredis regelbundenhetslemma [3] [4] För varje , finns det sådana att för varje graf med ett antal hörn finns det en uppdelning i delar som är så lika stora som möjligt i storlek , så att för par av dessa delar den tvådelade grafen av kanter som ligger mellan dem är -regelbunden. |
Szemeredis lemma lägger inga restriktioner på kanter mellan hörn från samma partitionsuppsättning.
Utsagan av lemma är icke-trivial endast för grafer med ett tillräckligt stort antal kanter. Om , då kommer någon av dess tvådelade subgrafer på delar med dimensioner också att vara glesa (dess densitet kommer inte att överstiga ) - därför kommer villkoret för densitetsskillnaden alltid att vara uppfyllt. [5]
Det bör också noteras att omnämnandet av samma variabel i två olika egenskaper - regularitetsindex och andelen -regelbundna tvådelade subgrafer - inte skapar något ytterligare samband mellan dessa egenskaper. En sådan formulering skulle också följa av en svagare formulering, där det till exempel skulle krävas att kanter fördelas regelbundet endast mellan par av set, där för (det vill säga även för ). I det här fallet, för att uppnå den ursprungliga formuleringen, skulle det räcka med att överväga , eftersom -regelbundenhet i grafen innebär -regelbundenhet vid .
Partitioneringen görs av en girig algoritm.
Först väljs en godtycklig uppdelning av hörn i uppsättningar , där:
Vidare, vid varje iteration av algoritmen, genereras en ny partition på ett visst sätt från den befintliga partitionen med mindre storlekar av delar och ett stort antal av dem. Den är byggd som en underavdelning av den ursprungliga partitionen, men sedan normaliseras den genom små omarrangemang så att storlekarna på alla (utom kanske en) delar är lika.
En sådan transformation fortsätter tills den resulterande partitionen i uppsättningar innehåller åtminstone par av uppsättningar vars tvådelade grafer är oregelbundna . Övergången från en partition till nästa sker på ett sådant sätt att det är möjligt att bevisa att algoritmen stannar exakt efter ett ändligt och begränsat av ett konstant (beroende på och ) antal steg. Dessutom är antalet resulterande uppsättningar i partitionen vid varje specifik iteration av algoritmen också begränsat, så det maximala antalet uppsättningar som kan bildas vid den sista iterationen kommer att vara det önskade värdet . [3]
Övergång från delning till underindelningLåt den aktuella partitionen inte uppfylla villkoren för lemma, det vill säga det finns par för vilka den tvådelade grafen mellan dem inte är -regelbunden. Låt oss beteckna detta tillstånd som .
Om , så finns det några speciella "problem" underuppsättningar som bryter mot -regelbundenhet för den tvådelade grafen som förbinder dessa komponenter. Det vill säga för dem:
Det verkar vara en rimlig idé att bli av med dessa problematiska delmängder genom att helt enkelt separera dem i en separat komponent, bilda en fyrdubbling istället för ett par av komponenter . En och samma komponent kan dock komma i konflikt med flera andra komponenter samtidigt, så uppdelningen bör inte göras en efter en, utan av flera problemuppsättningar samtidigt.
För att formalisera denna process, för varje enskild komponent , beaktas alla "problem" undergrupper som uppstår i den:
och σ-algebran som bildas på (det vill säga den är uppdelad i sådana delar att två valfria hörn, varav den ena tillhör någon och den andra inte tillhör den, hamnar i olika delar av underavdelningen).
Eftersom det för en individ inte finns några fler problematiska delmängder (och följaktligen inga fler element av σ-algebra konstruerade på dem), som ett resultat, bildas inga fler nya från en komponent .
Om du delar upp varje komponent på detta sätt får du en ny underavdelning .
Därefter måste du anpassa storleken på komponenterna (av vilka det inte finns fler än ). För att göra detta kan var och en av dess komponenter delas upp i nya komponenter av storleken (och, möjligen, en återstående komponent av en mindre storlek - "resten"), och alla hörn från "resterna" kan godtyckligt kombineras till nya komponenter av samma storlek och eventuellt en mindre komponentstorlek.
Den resulterande partitionen kommer att vara resultatet av en iteration av algoritmen.
Beviset på att algoritmen stannar efter ett ändligt antal steg utförs genom introduktionen av en potentiell funktion - ett numeriskt värde som beror på den aktuella partitionen - och spåra dess förändring vid ändring av iterationer av algoritmen.
"Potential" kan definieras till exempel enligt följande:
Denna funktion har ett antal viktiga egenskaper:
Detta följer av ojämlikheten , vilket är sant för , som medför ojämlikheten
Det räcker med att visa att fackföreningen minskar med högst (ytterligare uppdelning minskar inte , enligt annan fastighet).
När komponenterna kombineras försvinner vissa termer från summan och några nya dyker upp. Eftersom alla termer är positiva räcker det att ta hänsyn till de som försvinner. Summan av sådana termer är lätt att uppskatta:
Eftersom, när man erhåller en ny partition, enligt algoritmen, byggs inte mer än hörn om i underavdelningen, och eftersom för tillräckligt stor för någon konstant följer det av egenskaperna hos den potentiella funktionen att algoritmen kommer att stoppa efter steg.
I det första arbetet med detta ämne använde Szemeredi en något annorlunda potentiell funktion [1] :
Trots skillnaderna delar båda dessa funktioner idén om att beräkna genomsnittet av kvadratdensiteterna.
Som följer av beskrivningen av algoritmen uttrycks den övre uppskattningen för antalet komponenter i partitionen vid den -te iterationen av algoritmen av den rekursiva relationen
Antalet iterationer som algoritmen kommer att arbeta igenom uppskattas till .
Därför kan det totala antalet komponenter endast uppskattas genom att ett torn höjer sig till höjdens makt .
Det typiska matematiska beviset för Szemeredis lemma bryr sig inte om algoritmens beräkningskomplexitet .
Men en grupp på fem matematiker undersökte i en separat uppsats den algoritmiska aspekten av att hitta den önskade partitionen - i synnerhet beskrev de en algoritm som gör det möjligt att hitta en partition av en -vertexgraf i tid för fast och . Körtiden för deras algoritm begränsas av tiden för multiplikation av två matriser bestående av nollor och ettor. Algoritmen kan också parallelliseras och exekveras i tid på ett polynomiskt beroende på antalet processorer. [6]
År 1997 visade William Gowers att uppskattningen av storleken på antalet komponenter i den nödvändiga partitionen inte kan förbättras mer än upp till höjdexponenttornet . Han visade nämligen att det alltid finns en graf, vars uppdelning i ett mindre antal delar inte uppfyller villkoren för lemma.
Han ansåg en ännu mer allmän uppfattning om -regelbundenhet, där en delmängd av delar av en tvådelad graf , vars densitetsavvikelse är begränsad av definitionen, är begränsade istället för , och bevisade också att det finns ett motexempel för det.
Gowers använde en probabilistisk metod för att hitta ett motexempel , så hans bevis är inte konstruktivt . Tidningen övervägde viktade grafer med vikter från intervallet . För sådana grafer kan vi överväga en helt liknande formulering av lemma, där densiteten kommer att betraktas som summan av kanternas vikter istället för deras antal. Genom att konstruera ett motexempel i form av en viktad graf, visade Gowers också att en slumpmässig graf genererad av Bernoulli-schemat med kantsannolikheter som motsvarar vikterna i denna viktade graf kommer med hög sannolikhet att vara ett motexempel för det vanliga lemma (desutom, med hög sannolikhet kommer tätheterna inte att avvika kraftigt från liknande densiteter i en viktad graf förutsatt att och är tillräckligt stora). [7]
Gowers designEn viktad graf, som fungerar som ett motexempel till lemma med den vanliga definitionen av -regelbundenhet, är uppbyggd som en kombination med olika vikter av flera specifikt arrangerade stora grafer. När man konstruerar varje nästa graf från denna uppsättning, kombineras hörnen till större och större grupper av samma storlek så att hörn från två olika grupper antingen är anslutna till varandra med en komplett tvådelad graf eller inte alls anslutna (nya grupper är alltid en förening av de tidigare).
Låt hörnen delas in i grupper av samma storlek. Kombinera dessa grupper i block
,där (antag att det är ett heltal).
För varje par av olika block väljer vi en uppdelning av grupper från i två delar och en uppdelning av grupper från i två delar. Lägg till alla kanter på kompletta tvådelade grafer och .
Om partitioner väljs på ett sådant sätt att någon , som tillhör samma , inte har fler block där det finns hörn intill dem båda, då med rätt val blir den resulterande konstruktionen Gowers-konstruktionen. Men detta är konstruktionen av bara en graf - för att bygga nästa graf sätts block i stället för grupper och hela processen börjar om igen tills alla hörn är kombinerade till en grupp.
Den resulterande kedjan av grafer kombineras till en viktad graf enligt formeln (grafer där de kombinerade grupperna av hörn är mycket stora har störst vikt).
Motexemplet för -regelbundenhet är konstruerat på ett liknande sätt, men med några skillnader:
År 2007 generaliserade William Gowers regelbundenhetslemma till hypergrafer och använde generaliseringen för att bevisa Szemerédys flerdimensionella teorem. [åtta]
Det finns också en analog till Szemeredis lemma för glesa grafer (i den vanliga formuleringen är lemma trivialt för sådana grafer, eftersom varje partition uppfyller de nödvändiga villkoren). [9]
Den mest kända tillämpningen av regularitetslemma är för det kombinatoriska beviset för Szemeredis sats och dess generaliseringar (till exempel hörnsatsen ). [5] Emellertid har lemmat och dess idéer ett antal tillämpningar inom allmän grafteori också [10] - Szemeredys första artikel om detta lemma citeras i mer än 500 artiklar om olika ämnen. [ett]
Också av särskilt intresse är Triangle Removal Lemma , som härrör från regularitetslemma och används i samband med beviset för Szemeredis sats.
![]() |
---|