Spränglemma

Uppblåsningslemmat , bevisat av János Komlós , Gábor N. Sárközy och Endre Szemerédi 1997, är ett viktigt resultat inom extremalgrafteorin , särskilt inom ramen för regularitetsmetoden . Den anger att de reguljära paren i uttalandet av Szemerédis regelbundenhetslemma beter sig som kompletta tvådelade grafer i samband med inbäddning av spännande grafer av begränsad grad .

Definitioner och uttalande

För att formellt ange sprängningslemmat måste vi först definiera begreppet ett superregelbundet par .

Supervanliga par

Ett par $(A,B)$ av delmängder av vertexmängden kallas $(\varepsilon ,\delta )$ -superregular om för varje $X\subset A$ och $Y\subset B$ tillfredsställande

$|X|>\varepsilon |A|$ och $|Y|>\varepsilon |B|$

vi har

$e(X,Y)>\delta |X||Y|$

och dessutom,

$\deg(a)>\delta |B|$ för alla $a\in A$ och $\deg(b)>\delta |A|$ för alla $b\in B$ .

Här anger $e(X,Y)$ antalet par $(x,y)$ med $x\in X$ och $y\in Y$ så att $\{x,y\}$ är en kant.

Uttalande av Blow-up Lemma

Givet en graf $R$ av ordningen $r$ och positiva parametrar $\delta ,\Delta$ , finns det ett positivt $\varepsilon =\varepsilon (\delta ,\Delta ,r)$ så att följande gäller. Låt $n_{1},n_{2},\dots ,n_{r}$ vara godtyckliga positiva heltal och låt oss ersätta hörnen $v_{1},v_{2},\dots ,v_{r}$ av $R$ med parvis disjunkta uppsättningar $V_{1 },V_{2},\dots ,V_{r}$ av storlekar $n_{1},n_{2},\dots ,n_{r}$ (blåser upp). Vi konstruerar två grafer på samma vertexuppsättning $V=\bigcup V_{i}$ . Den första grafen $\mathbf {R}$ erhålls genom att ersätta varje kant $\{v_{i},v_{j}\}$ av $R$ med den fullständiga tvådelade grafen mellan motsvarande vertexuppsättningar $V_{i}$ och $V_{j}$ . En glesare graf G konstrueras genom att ersätta varje kant $\{v_{i},v_{j}\}$ med en $(\varepsilon ,\delta )$ -superreguljärt par mellan $V_{i}$ och $V_{j}$ . Om en graf $H$ med $\Delta (H)\leq \Delta$ är inbäddningsbar i $\mathbf {R}$ så är den redan inbäddbar i G.

Bevis skiss

Beviset för uppblåsningslemmat är baserat på att använda en randomiserad girig algoritm (RGA) för att bädda in hörn av $H$ i $G$ sekventiellt. Argumentet fortsätter sedan genom att begränsa felfrekvensen för algoritmen så att den är mindre än 1 (och faktiskt $o(1)$ ) för ett lämpligt val av parametrar. Det betyder att det finns en chans som inte är noll för att algoritmen ska lyckas, så en inbäddning måste finnas.

Att försöka bädda in alla hörn av ${\displaystyle H} direkt$ på detta sätt fungerar inte eftersom algoritmen kan fastna när endast ett litet antal hörn är kvar. Istället lägger vi åt sidan en liten del av vertexuppsättningen, kallad buffertpunkt , och försöker bädda in resten av hörnen. Buffertpunkten bäddas sedan in genom att använda Halls äktenskapsteorem för att hitta en perfekt matchning mellan buffertpunkten och de återstående hörnen av $G$ .

Notation

Vi lånar all notation som introducerats i tidigare avsnitt. Låt $n=|V(G)|=\summa n_{i}$ . Eftersom $H$ kan bäddas in i $\mathbf {R}$ , kan vi skriva $V(H)=X=\bigcup _{i\leq r}X_{i}$ med $|X_{i}|=|V_{i}|$ för alla $i$ . För en vertex $x\in X_{i}$ , låt $V_{x}$ beteckna $V_{i}$ . För $x\in X_{i},y\in X_{j}$ ,

$d_{xy}={\frac {e(V_{i},V_{j})}{|V_{i}||V_{j}|}}$

anger tätheten av kanter mellan motsvarande vertexuppsättningar av $G$ . $\phi :V(G)\to V(H)$ är inbäddningen som vi vill konstruera. $T$ är den sista tiden efter vilken algoritmen avslutas.

Översikt över algoritmen

Fas 0: Initiering

1. Välj girigt uppsättningen av buffertpunkten $B$ från hörnen på $H$ som en maximal uppsättning hörnavstånd minst $4$ från varandra
2. Ordna de återstående hörnen (de i $H\setminus B$ ) i en lista $L$ , placera grannarna till $B$ först.
3. Deklarera en kö $q$ med för närvarande prioriterade hörn, som initialt är tom.
4. Deklarera en array av uppsättningar $F_{z}$ indexerade av hörnen på $H$ , som representerar mängden av alla "fria fläckar" av $z$ , det vill säga mängden av obesatta hörn i $G$ som vertex $z$ kan mappas till utan att bryta mot något av närliggande villkor från de redan inbäddade grannarna till $z$ i $H$ . $F_{z}$ initieras till $V_{z}$ .

Fas 1: Randomiserad girig inbäddning

1. Välj en vertex $x$ från uppsättningen av återstående hörn enligt följande:
   1. Om kön $q$ med prioriterade hörn inte är tom, välj sedan vertex från $q$
   2. Annars väljer du ett hörn från listan $L$ över återstående hörn
2. Välj bilden $\phi (x)$ i $G$ för vertex $x$ slumpmässigt från uppsättningen "bra" val, där ett val är bra om inget av de nya fria uppsättningarna $F_{z}(t)$ skiljer sig för mycket i storlek från det förväntade värdet.
3. Uppdatera de fria uppsättningarna $F_{z}(t)$ , och placera hörn vars fria uppsättningar har blivit för små med avseende på storleken i den senaste uppdateringen i uppsättningen av prioriterade hörn $q$
4. Avbryt om kön $q$ innehåller en tillräckligt stor del av någon av uppsättningarna $X_{i}$
5. Om det finns icke-bufferthörn kvar att bädda in i antingen $L$ eller $q$ , uppdatera tiden $t$ och gå tillbaka till steg 1; annars gå vidare till fas 2.

Fas 2: Kőnig-Hall-matchning för återstående hörn

Betrakta uppsättningen av hörn som återstår att bädda in, vilket är exakt $B$ , och uppsättningen av fria fläckar $\bigcup _{b\in B}F_{b }(T)$ . Bilda en tvådelad graf mellan dessa två uppsättningar, sammanfoga varje $b\in B$ till $F_{b}(T)$ , och hitta en perfekt matchning i denna tvådelade graf. Bädda in enligt denna matchning.

Bevis på riktighet

Korrekthetsbeviset är tekniskt och ganska involverat, så vi utelämnar detaljerna. Grundargumentet går ut på följande sätt:

Steg 1: de flesta hörn är bra, och tillräckligt många hörn är fria

Bevisa samtidigt genom induktion på $t$ att om $x$ är vertexet inbäddat vid tidpunkten $t$ , då

1. endast en liten del av valen i $F_{x}(t)$ är dåliga
2. alla fria uppsättningar $F_{z}(t+1)$ är ganska stora för oinbäddade hörn $z$

Steg 2: "huvudlemmat"

Betrakta $1\leq i\leq r,Y\subseteq X_{i}$ och $A\subseteq V_{i}$ så att $|A|$ är inte för liten. Betrakta händelsen $E_{A,Y}$ där

1. inga hörn är inbäddade i $A$ under den första fasen
2. för varje $y\in Y$ finns det en tid $t_{y}$ så att bråkdelen av fria hörn av $y$ i $A$ vid tidpunkten $t$ var liten.

Sedan bevisar vi att sannolikheten för att $E_{A,Y}$ händer är låg.

Steg 3: fas 1 lyckas med stor sannolikhet

Det enda sättet att den första fasen kan misslyckas är om den avbryts, eftersom vi i det första steget vet att det alltid finns ett tillräckligt urval av bra hörn. Programmet avbryts först när kön är för lång. Argumentet fortsätter sedan genom att unionsgränsa över alla fellägen, och notera att för varje särskilt val av $1\leq i\leq r$ , ${\displaystyle Y\subseteq X_{i},|Y|\geq \delta _{Q}|X_{i}|} och A = V i {\displaystyle A=V_{$ i ${$ \ $Y }$ representerar en delmängd av kön som misslyckades, trippeln $(i,Y,A)$ uppfyller villkoren för "huvudlemmat", och har därför en låg sannolikhet att inträffa.

Steg 4: ingen kö i inledande fas

Kom ihåg att listan sattes upp så att grannar till hörn i bufferten bäddas in först. Tiden tills alla dessa hörn blir inbäddade kallas den initiala fasen . Bevisa genom induktion på $t$ att inga hörn läggs till i kön under den inledande fasen. Det följer att alla grannar till buffertpunkten läggs till före resten av hörnen.

Steg 5: buffertpunkten har tillräckligt med fria fläckar

För alla $x\in B$ och $v\in V_{x}$ , kan vi hitta en tillräckligt stor nedre gräns för sannolikheten att ${\displaystyle \phi (N_{H}(x))\subseteq N_{G}(v)} ,$ villkorat av antagandet att $v$ var ledig före någon av hörnen i $N_{H}(x)$ inbäddades.

Steg 6: fas 2 lyckas med stor sannolikhet

Enligt Halls äktenskapsteorem misslyckas fas 2 om och endast om Halls tillstånd kränks. För att detta ska hända måste det finnas några $1\leq i\leq r$ och $S\subseteq X_{i}$ så att $|\bigcup _{z\in S}F_{z}(T)|<|S|$ . $|S|$ kan inte vara för liten på grund av antalet fria uppsättningar (steg 1). Om $|S|$ är för stor, då med hög sannolikhet $\bigcup _{z\in S}F_{z}(T)= V_{i}(T)$ , så sannolikheten för misslyckande i ett sådant fall skulle vara låg. Om $|S|$ är varken för liten eller för stor, och notera då att $A:=V_{i}(T)\ setminus \bigcup _{z\in S}F_{z}(T)$ är en stor uppsättning oanvända hörn, vi kan använda huvudlemmat och unionsbundna felsannolikheten.

Ansökningar

Uppblåsningslemmat har ett antal tillämpningar för att bädda in täta grafer.

Pósa-Seymour gissningar

1962 antog Lajos Pósa att varje $n$ -vertexgraf med minsta grad på minst ${\frac {2n}{3}}$ innehåller kvadraten på en Hamiltonsk cykel , vilket generaliserar Dirac ' s teorem . Gissningen utökades ytterligare av Paul Seymour 1974 till följande:

Varje graf på $n$ hörn med minsta grad minst ${\frac {kn}{k+1}}$ innehåller ${\displaystyle k} -$ :te potensen av en Hamiltonian cykel.

Uppblåsningslemmat användes av Komlós, Sárközy och Szemerédi för att bevisa gissningen för alla tillräckligt stora värden på $n$ (för ett fast ${\displaystyle k} )$ 1998.

Alon-Yusters förmodan

År 1995 övervägde Noga Alon och Raphael Yuster generaliseringen av den välkända Hajnal–Szemerédi-satsen till godtyckliga $H$ - faktorer (istället för bara kompletta grafer), och bevisade följande påstående:

För varje fast graf $H$ med $h$ hörn, valfri graf G med n hörn och med minsta grad $d\geq {\ frac {\chi (H)-1}{\chi (H)}} n$ innehåller $(1-o(1))n/h$ vertex disjunkta kopior av H.

De antog också att resultatet bara gäller med ett konstant (istället för linjärt) fel:

För varje heltal $h$ finns det en konstant $c(h)$ så att för varje graf $H$ med $h$ hörn, alla grafer ${\ displaystyle G}$ med $n$ hörn och med minsta grad $d\geq {\frac {\chi (H)-1}{\chi ( H)}}n$ innehåller minst $n/hc(h)$ vertex disjunkta kopior av $H$ .

Denna gissning bevisades av Komlós, Sárközy och Szemerédi 2001 med hjälp av blow-up-lemmat.

Historia och varianter

Uppblåsningslemmat, som först publicerades 1997 av Komlós, Sárközy och Szemerédi, uppstod som en förfining av befintliga bevistekniker med hjälp av regularitetsmetoden för att bädda in spännande grafer, som i beviset för Bollobás gissningar om spännande träd, arbete på Pósa-Seymour gissningar om den minsta graden som krävs för att innehålla den k:te grafpotentialen för en Hamiltonsk cykel , och beviset för Alon-Yusters gissning om den minsta graden som behövs för att en graf ska ha en perfekt H- faktor . Bevisen för alla dessa satser förlitade sig på att använda en randomiserad girig algoritm för att bädda in majoriteten av hörn, och sedan använda ett Kőnig-Hall-liknande argument för att hitta en inbäddning för de återstående hörnen. Det första beviset på spränglemmat använde också ett liknande argument. Senare under 1997 publicerade dock samma författare ett annat dokument som fann en förbättring av den randomiserade algoritmen för att göra den deterministisk.

Peter Keevash fann en generalisering av uppblåsningslemmat till hypergrafer 2010.

Stefan Glock och Felix Joos upptäckte en variant av uppblåsningslemmat för regnbågsgrafer 2018.

Under 2019 hittade Peter Allen, Julia Böttcher, Hiep Hàn, Yoshiharu Kohayakawa och Yury Person glesa analoger av uppblåsningslemmat för att bädda in avgränsade gradgrafer i slumpmässiga och pseudoslumpmässiga grafer