Lemma för borttagning av grafer

I grafteorin anger grafborttagningslemmat att när en graf innehåller få kopior av en given subgraf , kan alla kopior elimineras genom att ta bort ett litet antal kanter . Det speciella fallet där subgrafen är en triangel kallas triangelborttagningslemma .

Grafborttagningslemma kan användas för att bevisa Roths sats om 3-terms aritmetiska progressioner, och en generalisering av det, hypergrafborttagningslemma , kan användas för att bevisa Szemerédis sats . Den har också tillämpningar för egenskapstestning .

Formulering

Låt $H$ vara en graf med $h$ hörn. Grafborttagningslemmat anger att det för alla $\epsilon >0$ finns en konstant $\delta =\delta (\epsilon ,H)>0$ såsom att för alla $n$ -vertexgraf $G$ med färre än $\delta n^{h}$ subgrafer som är isomorfa till $H$ , är det möjligt att eliminera alla kopior av $H$ genom att som mest ta bort $\epsilon n^{2}$ kanter från $G$ .

Ett alternativt sätt att ange detta är att säga att för alla $n$ -vertexgraf $G$ med $o(n^{h})$ subgrafer som är isomorfa till ${ \displaystyle H}$ , det är möjligt att eliminera alla kopior av $H$ genom att ta bort $o(n^{2})$ kanter från $G$ . Här $o$ användningen av lite o-notation .

I fallet när $H$ är en triangel kallas resulterande lemma för triangelborttagningslemma .

Historia

Den ursprungliga motiveringen för studien av triangelborttagningslemma var Ruzsa–Szemerédi-problemet . Den initiala formuleringen på grund av Imre Z. Ruzsa och Szemerédi från 1978 var något svagare än det triangelborttagningslemma som används nuförtiden och kan grovt uttryckas enligt följande: varje lokalt linjär graf på $n$ hörn innehåller ${\ displaystyle o(n^{2})}$ kanter. Detta uttalande kan snabbt härledas från ett modernt triangelborttagningslemma. Ruzsa och Szemerédi gav också ett alternativt bevis på Roths teorem om aritmetiska progressioner som en enkel följd.

1986, under deras arbete med generaliseringar av Ruzsa–Szemerédi-problemet till godtyckliga $r$ -uniforma grafer, gav Erdős , Frankl och Rödl ett uttalande för allmänna grafer mycket nära det moderna grafborttagningslemma: om graf ${\ displaystyle H_{2}}$ är en homomorf bild av $H_{2}$ , sedan valfri $H_{1}$ - fri graf $G$ på $n$ hörn kan göras $H_{2}$ -fria genom att ta bort $o(n^{2})$ kanter.

Den moderna formuleringen av grafborttagningslemma uppgavs först av Füredi 1994. Beviset generaliserade tidigare tillvägagångssätt av Ruzsa och Szemerédi och Erdős, Frankl och Rödl, och använde också Szemerédi regularity lemma .

Lemma för grafräkning

En nyckelkomponent i lemmat för bevis för borttagning av grafer är grafräkningslemma om att räkna subgrafer i system med vanliga par. Lemma för grafräkning är också mycket användbart i sig. Enligt Füredi används det "i de flesta tillämpningar av regularitetslemma".

Heuristiskt argument

Låt $H$ vara en graf på $h$ hörn, vars vertexuppsättning är $V=\{1,2,\ldots ,h\ }$ och kantuppsättningen är $E$ . Låt $X_{1},X_{2},\ldots ,X_{h}$ vara uppsättningar av hörn i någon graf $G$ så att för alla $ij\in E$ par $(X_{i},X_{j})$ är $\epsilon$ - regelbundet (i betydelsen regelbundenhet lemma). Låt också $d_{ij}$ vara densiteten mellan mängderna $X_{i}$ och $X_{j}$ . Intuitivt bör vanligt par $(X,Y)$ med densitet $d$ bete sig som en slumpmässig Erdős–Rényi -liknande graf, där varje par av hörn $(x,y)\in (X\times Y)$ väljs för att vara en kant oberoende med sannolikheten d { $displaystyle d}$ . Detta antyder att antalet kopior av $H$ på hörn $x_{1},x_{2},\ldots ,x_{h}$ så att $x_{i}\in X_{i}$ bör vara nära det förväntade antalet från Erdős–Rényi-modellen:

$$\prod _{ij\in E(H)}d_{ij}\prod _{i\in V(H)}|X_{i}|$$

där $E(H)$ och $V(H)$ är kantmängden och vertexmängden för $H$ .

Exakt uttalande

Den enkla formaliseringen av ovanstående heuristiska påstående är som följer. Låt $H$ vara en graf på $h$ hörn, vars vertexuppsättning är $V=\{1,2,\ldots ,h\ }$ och kantuppsättningen är $E$ . Låt $\delta >0$ vara godtycklig. Sedan finns det $\epsilon >0$ så att för alla $X_{1},X_{2},\ldots ,X_{h}$ enligt ovan , som uppfyller $d_{ij}>\delta$ för alla $ij\in E$ , antalet grafhomomorfismer från $H$ till $G$ så att vertex $i\in V(H)$ mappas till $X_{i}$ är inte mindre än

$$(1-\delta )\prod _{ij\in E}(d_{ij}-\delta )\prod _{i\in V}|X_{i}|$$

Spräng Lemma

Man kan till och med hitta subgrafer med avgränsade grader av blow-ups av $H$ i en liknande miljö. Följande påstående förekommer i litteraturen under namnet på spränglemmat och bevisades först av Komlós , Sárközy och Szemerédi. Exakt påstående här är en något förenklad version på grund av Komlós, som kallade det också som nyckellemmat, eftersom det används i många regelbundenhetsbaserade bevis.

Låt $H_{1}$ vara en godtycklig graf och $t\in \mathbb {Z} _{+}$ . Konstruera $H(t)$ genom att ersätta varje vertex $i$ i $H$ med en oberoende uppsättning $V_{i}$ av storleken $t$ och ersätter varje kant $ij$ av $H$ med en komplett tvådelad graf på $(V_{i},V_{j})$ . Låt $\epsilon ,\delta >0$ vara godtyckliga realer, $N$ vara ett potentiellt heltal och låt $H_{2}$ vara en subgraf till $H(t)$ med $h$ hörn och med maximal grad $\Delta$ . Definiera $\epsilon _{0}=\delta ^{\Delta }/(2+\Delta )$ . Låt slutligen $G$ vara en graf och $X_{1},X_{2},\ldots ,X_{h}$ vara disjunkta uppsättningar av hörn av $G$ så att närhelst $ij\in E(H_{2})$ så $(X_{i},X_{ j})$ är ett $\epsilon$ -regelbundet par med densitet minst $\epsilon +\delta$ . Sedan om $\epsilon \leq \epsilon _{0}$ och $1-t\leq N\epsilon _{0}$ , antalet injektiva grafhomomorfismer från $H_{2}$ till $G$ är minst $(\epsilon _{0}N)^{h}$ .

Faktum är att man bara kan begränsa sig till att räkna homomorfismer så att varje vertex $k\in [h]$ av $H_{2}$ så att $k \in V_{i}$ mappas till en vertex i $X_{i}$ .

Bevis

Vi kommer att tillhandahålla bevis för räknelemmat i fallet när $H$ är en triangel ( triangel räkningslemma ) . Beviset för det allmänna fallet, liksom beviset för spränglemmat, är mycket lika och kräver inte olika tekniker.

Ta $\epsilon =\delta /2$ . Låt $X_{1}'\subset X_{1}$ vara mängden av de hörn i $X_{1}$ som har minst $(d_{12}-\epsilon )|X_{2}|$ grannar i $X_{2}$ och åtminstone $(d_{13}-\epsilon )|X_{3}|$ grannar i $X_{3}$ . Observera att om det fanns fler än $\epsilon |X_{1}|$ hörn i $X_{1}$ med mindre än $(d_{12}-\epsilon )|X_{2}|$ grannar i $X_{2}$ , då skulle dessa hörn tillsammans med hela $X_{2}$ bevittna $\epsilon$ -oregelbundenhet i paret $(X_{1},X_{2})$ . Att upprepa detta argument för $X_{3}$ visar att vi måste ha $|X_{1}'|>(1-2\epsilon )|X_{1}|$ . Ta nu godtyckliga $x\in X_{1}'$ och definiera $X_{2}'$ och $X_{3}'$ som grannar till $x$ i $X_{2}$ respektive $X_{3}$ . Per definition $|X_{2}'|\geq (d_{12}-\epsilon )|X_{2}|\geq \epsilon |X_{2}|$ och $|X_{3}'|\geq \epsilon |X_{3}|$ så genom regelbundenhet av $(X_{2},X_{3})$ får vi existens av minst

$$(d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13 }-\epsilon )|X_{2}||X_{3}|$$

trianglar som innehåller $x$ . Eftersom $x$ valdes godtyckligt från mängden $X_{1}'$ av storleken minst $(1-2\epsilon )|X_{1}|$ , vi får totalt minst minst

$$(1-2\epsilon )(d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (d_{12}-\epsilon )(d_{23}- \epsilon )(d_{13}-\epsilon )|X_{1}||X_{2}||X_{3}|$$

vilket avslutar beviset som $\epsilon =\delta /2$ .

Bevis

Bevis på triangelborttagningslemmat

För att bevisa triangelborttagningslemma, överväg en $\epsilon /4$ -vanlig partition $V_{1}\cup \cdots \cup V_{M}$ av vertexuppsättning av $G$ . Detta finns genom Szemerédi regelbundenhet lemma. Tanken är att ta bort alla kanter mellan oregelbundna par, lågdensitetspar och små delar, och bevisa att om åtminstone en triangel fortfarande finns kvar, så återstår många trianglar. Mer specifikt, ta bort alla kanter mellan delarna $V_{i}$ och $V_{j}$ om

• $(V_{i},V_{j})$ är inte $\epsilon /4$ -regular
• densiteten $d(V_{i},V_{j})$ är mindre än $\epsilon /2$ , eller
• antingen $V_{i}$ eller $V_{j}$ har som mest $(\epsilon /4M)n$ hörn.

Denna procedur tar bort högst $\epsilon n^{2}$ kanter. Om det finns en triangel med hörn i $V_{i},V_{j},V_{k}$ efter att dessa kanter har tagits bort, så säger triangelräknelemmat att det finns vid minst

$$\left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\ epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}\cdot n^{3}$$

tredubblar i $V_{i}\ gånger V_{j}\ gånger V_{k}$ som bildar en triangel. Således kan vi ta

$$\delta <{\frac {1}{6}}\left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\ höger)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}.$$

Bevis på grafborttagningslemma

Beviset för fallet för allmän $H$ är analogt med triangelfallet och använder grafräkningslemma istället för triangelräkningslemma.

Inducerad grafborttagning Lemma

En naturlig generalisering av Graph Removal Lemma är att överväga inducerade subgrafer . Vid egenskapstestning är det ofta användbart att överväga hur långt en graf är från att induceras H-fri. En graf $G$ anses innehålla en inducerad subgraf $H$ om det finns en injektiv karta $f:V(H)\rightarrow V (G)$ så att $(f(u),f(v))$ är en kant av $G$ om och endast om $(u,v)$ är en kant av $H$ . Observera att icke-kanter också beaktas. $G$ induceras $H$ -fri om det inte finns någon inducerad subgraf $G$ . Vi definierar $G$ som $\epsilon$ -långt ifrån att induceras $H$ -fri om vi inte kan lägga till eller ta bort $\epsilon n^{2}$ kanter för att göra $G$ inducerad $H$ -fri.

Formulering

En version av Graph Removal för inducerade subgrafer bevisades av Alon , Fischer, Krivelevich och Szegedy 2000. Den anger att för varje graf $H$ med $h$ hörn och $\ epsilon >0$ , det finns en konstant $\delta >0$ så att om en $n$ -vertexgraf $G$ har färre än $\delta n ^{h}$ inducerade subgrafer som är isomorfa till $H$ , då är det möjligt att eliminera alla inducerade kopior av $H$ genom att lägga till eller ta bort färre än $\epsilon n^{2 }$ kanter.

Problemet kan omformuleras enligt följande: Givet en röd-blå färgning $H'$ av hela grafen $K_{h}$ (Analogt med grafen $H$ på samma $h$ hörn där icke-kanter är blå, kanter är röda), och en konstant $\epsilon >0$ , då finns det en konstant $\delta >0$ så att för alla röd-blå färger av $K_{n}$ har färre än $\delta n^{h}$ subgrafer som är isomorfa till $H'$ , då är det möjligt för att eliminera alla kopior av $H$ genom att ändra färgerna på färre än $\epsilon n^{2}$ kanter. Lägg märke till att vår tidigare "rengöringsprocess", där vi tar bort alla kanter mellan oregelbundna par, lågdensitetspar och små delar, bara innebär att kanter tas bort. Att ta bort kanter motsvarar endast att ändra kantfärger från rött till blått. Det finns dock situationer i det inducerade fallet där det optimala redigeringsavståndet också innebär att kantfärgerna ändras från blått till rött. Följaktligen är Regularity Lemma otillräckligt för att bevisa Induced Graph Removal Lemma. Beviset på Lemma för inducerad grafborttagning måste dra fördel av det starka regelbundenhetslemma .

Bevis

Stark Regelbundenhet Lemma

Det starka regularitetslemma är en förstärkt version av Szemerédis Regularitetslemma. För varje oändlig sekvens av konstanter ${\displaystyle \epsilon _{0}\geq \epsilon _{1}\geq ...>0} ,$ det finns ett heltal $M$ så att för vilken graf ${\displaystyle G} som helst$ , vi kan erhålla två (likvärdiga) partitioner ${\mathcal {P}}$ och ${\mathcal {Q}}$ så att följande egenskaper är uppfyllda:

• ${\mathcal {Q}}$ förfinar ${\mathcal {P}}$ , det vill säga varje del av ${\mathcal {P}}$ är föreningen av någon samling av delar i ${\mathcal {Q}}$ .
• ${\mathcal {P}}$ är $\epsilon _{0}$ -regular och ${\mathcal {Q}}$ är $\epsilon _{|{\mathcal {P}}|}$ -regelbunden.
• $q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}$
• $|{\mathcal {Q}}|\leq M$

Funktionen $q$ är definierad som energifunktionen som definieras i Szemerédi regularity lemma . I huvudsak kan vi hitta ett par partitioner ${\mathcal {P}},{\mathcal {Q}}$ där ${\mathcal {Q}}$ är extremt regelbunden jämfört med ${\mathcal {P}}$ , och samtidigt ${\mathcal {P}},{\mathcal {Q}}$ är nära varandra. (Denna egenskap är fångad i det tredje skicket)

Följd av Strong Regularity Lemma

Följande följd av det starka regularitetslemma används i beviset för inducerad grafborttagningslemma. För varje oändlig sekvens av konstanter ${\displaystyle \epsilon _{0}\geq \epsilon _{1}\geq ...>0} ,$ det finns $\delta >0$ så att det finns en partition ${\mathcal {P}}={V_{1},...,V_{k}}$ och delmängder $W_{i}\subset V_{i}$ för varje $i$ där följande egenskaper är uppfyllda:

• $|W_{i}|>\delta n$
• $(W_{i},W_{j})$ är $\epsilon _{|{\mathcal {P}}|}$ -regelbundet för varje par $i,j$
• $|d(W_{i},W_{j})-d(V_{i},V_{j})|\leq \epsilon _{0}$ för alla utom $\epsilon _{0}|{\mathcal {P}}|^{2}$ par $i,j$

Huvudidén med beviset på detta resultat är att börja med två partitioner ${\mathcal {P}}$ och ${\mathcal {Q}}$ som uppfyller Strong Regularity Lemma där ${\displaystyle q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}^{3}/$ } Sedan för varje del $V_{i}\in {\mathcal {P}}$ väljer vi likformigt slumpmässigt någon del $W_{i}\subset V_{i }$ som är en del i ${\mathcal {Q}}$ . Det förväntade antalet oregelbundna par $W_{i}$$\displaystyle (W_{i},W_{j})}$ är mindre än 1. Det finns alltså en viss samling av så att varje par är $\epsilon _{|{\mathcal {P}}|}$ -vanlig!

Den viktiga aspekten av denna följd är att varje par av $W_{i},W_{j}$ är $\epsilon _{|{\mathcal {P}}|}$ -vanlig! Detta gör att vi kan ta hänsyn till kanter och icke-kanter när vi utför vårt rengöringsargument.

Bevis på skiss av det inducerade grafborttagningslemma

Med dessa resultat kan vi bevisa Lemma för inducerad grafborttagning. Ta valfri graf $G$ med $n$ hörn som har mindre än $\delta n^{v(H)}$ kopior av $H$ . Tanken är att börja med en samling vertexuppsättningar $W_{i}$ som uppfyller villkoren för Corollary of the Strong Regularity Lemma . Vi kan sedan utföra en "rengöringsprocess" där vi tar bort alla kanter mellan par av delar $(W_{i},W_{j})$ med låg densitet, och vi kan lägga till alla kanter mellan par av delar $(W_{i},W_{j})$ med hög densitet. Vi väljer densitetskraven så att vi har lagt till/raderat högst $\epsilon n^{2}$ kanter.

Om den nya grafen inte har några kopior av $H$ så är vi klara. Antag att den nya grafen har en kopia av $H$ . Antag att vertexen $v_{i}\in v(H)$ är inbäddad i $W_{f(i)}$ . Om det sedan finns en kant som förbinder $v_{i},v_{j}$ i $H$ , då $W_{i},W_{j }$ har inte låg densitet. (Kanter mellan $W_{i},W_{j}$ togs inte bort i rengöringsprocessen) På liknande sätt, om det inte finns en kant som ansluter $v_{i} ,v_{j}$ i $H$ , då har $W_{i},W_{j}$ inte hög densitet. (Kanter mellan $W_{i},W_{j}$ lades inte till i rengöringsprocessen)

Sålunda, genom ett liknande räkneargument som beviset för triangelräknelemmat, det vill säga grafräkningslemma , kan vi visa att $G$ har mer än $\delta n^{ v(H)}$ kopior av $H$ .

Generaliseringar

Lemmat för borttagning av grafer utökades senare till riktade grafer och hypergrafer .

Kvantitativa gränser

Användning av regularitetslemma i beviset för grafborttagningslemma tvingar $\delta$ att vara extremt liten, avgränsad av tornfunktionen för höjdpolynomet i $\epsilon ^{-1}$ som är ${\displaystyle \delta =1/{\text{torn}}(\epsilon ^{-O(1)})} ($ här ${\ text{torn}}(k)$ är tornet av två med höjden ${\displaystyle k} )$ . Tornfunktion av höjd $\epsilon ^{-O(1)}$ är nödvändig i alla regularitetsbevis, vilket antyds av resultat från Gowers på nedre gränser i regularitetslemma. Men 2011 Fox ett nytt bevis på grafborttagningslemma som inte använder regularitetslemma, vilket förbättrade gränsen till $\delta =1/{\text {torn}}(5h^{2}\log \epsilon ^{-1})$ (här är $h$ antalet hörn av borttagen graf $H$ ). Hans bevis använder dock regelbundenhetsrelaterade idéer som energiökning , men med en annan uppfattning om energi, relaterad till entropi . Detta bevis kan också omformuleras med Frieze-Kannan svag regelbundenhet lemma som noterats av Conlon och Fox. I specialfallet med bipartit $H$ visades det att $\delta =\epsilon ^{O(1)}$ är tillräckligt.

Det finns ett stort gap mellan övre och nedre gränser för $\delta$ i det allmänna fallet. Det nuvarande bästa resultatet sant för alla grafer $H$ beror på Alon och anger att det för varje icke-bipartit $H$ finns konstant $c>0$ så att $\delta <(\epsilon /c)^{c\log(c/\epsilon )}$ är nödvändigt för att grafborttagningslemma ska hålla medan för bipartite $H$ den optimala $\delta$ har polynomberoende av ${\displaystyle \epsilon } ,$ som matchar den nedre gränsen. Konstruktion för icke-bipartsfall är en konsekvens av Behrends konstruktion av stora Salem-Spencer-set. I själva verket, eftersom triangelborttagningslemma antyder Roths teorem, kan förekomsten av en stor Salem-Spencer-mängd översättas till en övre gräns för $\delta$ i triangelborttagningslemma. Denna metod kan utnyttjas för godtycklig icke-bipartit $H$ för att ge ovannämnda gräns.

Ansökningar

Additiv kombinatorik

• Ruzsa och Szemerédi formulerade triangelborttagningslemma för att ge subkvadratiska övre gränser för Ruzsa-Szemerédi-problemet för storleken på grafer där varje kant tillhör en unik triangel . Detta leder till ett bevis för Roths teorem.
• Lemmat för borttagning av triangeln kan också användas för att bevisa hörnsatsen , som säger att varje delmängd av $[n]^{2}$ som inte innehåller någon axellinjeformad likbent rätvinklig triangel har storlek $o(n^{2})$ .
• Lemmat för borttagning av hypergraf kan användas för att bevisa Szemerédis teorem om förekomsten av långa aritmetiska progressioner i täta delmängder av heltal.

Grafteori

• Grafräknings-/borttagningslemma kan användas för att ge ett snabbt och transparent bevis för Erdős–Stone-satsen med utgångspunkt från Turáns sats och utöka resultatet till Simonovits stabilitet : för alla grafer $H$ och alla $\epsilon > 0$ det finns $\delta$ så att varje $H$ -fri graf på $n$ hörn med minst $\left(1-{\frac {1}{\chi (H)-1}}\right){\binom {n}{2}}-\delta n^{2}$ kanter kan omvandlas till komplett $(\chi (H)-1)$ -partit Turán graf $T_{n,\chi (H )-1}$ genom att lägga till och/eller ta bort högst $\epsilon n^{2}$ kanter (här är $\chi (H)$ det kromatiska talet för ${ \displaystyle H}$ ). Även om båda resultaten hade bevisats tidigare med hjälp av mer elementära tekniker (Erdős–Stone-satsen bevisades 1966 av Erdős och Stone medan Simonovits stabilitet visades samma år av olika författare), ger regelbundenhetsbeviset olika synpunkter och belyser samband med andra moderna bevis.
• Lemma för borttagning av grafer tillsammans med Erdős–Stone-satsen kan användas för att visa att antalet icke-isomorfa $H$ -fria grafer på $n$ hörn är lika med
  $$2^{(\pi (H)+o(1)){\binom {n}{2}}}$$
  där $\pi (H)=1-{\frac {1}{\chi (H)-1}}$ är Turán-densiteten för ${ \displaystyle H}$ .

Fastighetsprövning

• Lemmat för borttagning av grafer har applikationer för egenskapstestning , eftersom det innebär att för varje graf, antingen är grafen nära en $H$ -fri graf, eller så kommer slumpmässigt urval lätt att hitta en kopia av $H$ i grafen. Ett resultat är att för varje fast $\epsilon >0$ finns det en konstant tidsalgoritm som returnerar med hög sannolikhet oavsett om en given $n$ -vertexgraf $G$ är eller inte $\epsilon$ -långt ifrån att vara $H$ -fri. Här $\epsilon$ -långt ifrån att vara $H$ -fri att minst $\epsilon n^{2}$ kanter måste tas bort för att eliminera alla kopior av ${ \displaystyle H}$ i $G$ .
• Lemmat för inducerad grafborttagning formulerades av Alon, Fischer, Krivelevich och Szegedy för att karakterisera testbara grafegenskaper.

Se även

• Räknar lemma