Behållarmetod

Metoden för (hypergraf) behållare är ett kraftfullt verktyg som kan hjälpa till att karakterisera den typiska strukturen och/eller svara på extrema frågor om familjer av diskreta objekt med en föreskriven uppsättning lokala begränsningar. Sådana frågor uppstår naturligt i extremal grafteori , additiv kombinatorik , diskret geometri , kodningsteori och Ramsey-teori ; de inkluderar några av de mest klassiska problemen inom de tillhörande områdena.

Dessa problem kan uttryckas som frågor av följande form: givet en hypergraf H på finit vertexmängd V med kantmängd E (dvs en samling delmängder av V med vissa storleksbegränsningar), vad kan vi säga om de oberoende uppsättningarna av H ( dvs de delmängder av V som inte innehåller något element av E )? Hypergrafbehållarens lemma tillhandahåller en metod för att hantera sådana frågor.

Historia

Ett av de grundläggande problemen med extremal grafteorin, som dateras till Mantels arbete 1907 och Turán från 1940-talet, ber att karakterisera de grafer som inte innehåller en kopia av något fast förbjudet H som en subgraf. I en annan domän är en av de motiverande frågorna inom additiv kombinatorik att förstå hur stor en uppsättning heltal kan vara utan att innehålla en k -term aritmetisk progression , med övre gränser för denna storlek som ges av Roth ( $k= 3$ ) och Szemerédi (general k ).

Metoden med behållare (i grafer) var ursprungligen banbrytande av Kleitman och Winston 1980, som avgränsade antalet gitter och grafer utan 4-cykler. Behållarliknande lemman utvecklades oberoende av flera matematiker i olika sammanhang, särskilt Sapozhenko, som ursprungligen använde detta tillvägagångssätt 2002-2003 för att räkna upp oberoende uppsättningar i vanliga grafer , summafria mängder i abelska grupper och studera en mängd andra uppräkningar problem

En generalisering av dessa idéer till ett hypergrafbehållarelemma utarbetades oberoende av Saxton och Thomason och Balogh, Morris och Samotij 2015, inspirerad av en mängd tidigare relaterat arbete.

Huvudidé och informellt uttalande

Många problem i kombinatorik kan omarbetas som frågor om oberoende uppsättningar i grafer och hypergrafer. Anta till exempel att vi vill förstå delmängder av heltal 1 till n , som vi betecknar med $[n]$ som saknar en k -term aritmetisk progression. Dessa uppsättningar är exakt de oberoende uppsättningarna i den k -uniforma hypergrafen $H=(\{1,2,\ldots ,n\},E)$ , där E är samlingen av alla k -term aritmetiska progressioner i $\{1,2,\ldots ,n\}$ .

I ovanstående (och många andra) fall finns det vanligtvis två naturliga klasser av problem som ställs kring en hypergraf H :

• Vad är storleken på en maximal oberoende mängd i H ? Hur ser samlingen av oberoende uppsättningar av maximal storlek i H ut?
• Hur kan oberoende uppsättningar ha H ? Hur ser en "typisk" oberoende uppsättning i H ut ?

Dessa problem hänger samman med en enkel observation. Låt $\alpha (H)$ vara storleken på en största oberoende uppsättning av H och anta att $H$ har $i(H)$ oberoende uppsättningar. Sedan,

$2^{\alpha (H)}\leq i(H)\leq \sum _{r=0}^{\alfa (H)}{|V(H)| \väljare},$

där den nedre gränsen följer genom att ta alla delmängder av en maximal oberoende mängd. Dessa gränser är relativt långt borta från varandra om inte $\alpha (H)$ är mycket stor, nära antalet hörn i hypergrafen. Men i många hypergrafer som naturligt uppstår i kombinatoriska problem har vi anledning att tro att den nedre gränsen ligger närmare det sanna värdet; sålunda är det primära målet att förbättra de övre gränserna för i(H) .

Hypergrafbehållarens lemma ger ett kraftfullt tillvägagångssätt för att förstå strukturen och storleken på familjen av oberoende uppsättningar i en hypergraf. I grunden gör hypergrafbehållarmetoden det möjligt för oss att extrahera från en hypergraf, en samling behållare , delmängder av hörn som uppfyller följande egenskaper:

• Det finns inte för många containrar.
• Varje behållare är inte mycket större än den största oberoende uppsättningen.
• Varje behållare har få kanter.
• Varje oberoende uppsättning i hypergrafen är helt inkluderad i någon behållare.

Namnbehållaren anspelar på detta sista villkor. Sådana behållare tillhandahåller ofta ett effektivt tillvägagångssätt för att karakterisera familjen av oberoende uppsättningar (underuppsättningar av behållarna) och för att räkna upp de oberoende uppsättningarna av en hypergraf (genom att helt enkelt beakta alla möjliga underuppsättningar av en container).

Hypergrafbehållarlemmat uppnår ovanstående behållarenedbrytning i två delar. Den konstruerar en deterministisk funktion f . Sedan tillhandahåller den en algoritm som extraherar från varje oberoende mängd I i hypergraf H , en relativt liten samling av hörn ${\displaystyle S\subset I} ,$ kallad ett fingeravtryck, med egenskapen att $S\subset I\subset S\cup f(S)$ . Sedan är behållarna samlingen av uppsättningar $S\cup f(S)$ som uppstår i ovanstående process, och den lilla storleken på fingeravtrycken ger god kontroll över antalet sådana behållaruppsättningar .

Algoritm för grafbehållare

Vi beskriver först en metod för att visa starka övre gränser för antalet oberoende uppsättningar i en graf; denna utläggning anpassad från en undersökning av Samotij om grafbehållarmetoden, som ursprungligen användes av Kleitman-Winston och Sapozhenko.

Notation

Vi använder följande notation i avsnittet nedan.

• $G=(V,E)$ är en graf på $|V|=n$ hörn, där vertexuppsättningen är utrustad med (godtycklig) ordning $\{v_{1},\ldots ,v_{n} \}$ .
• Låt $\ell (G)$ vara samlingen av oberoende uppsättningar av G med storlek $i(G):=|\ell (G)|$ . Låt $i(G,r)$ vara antalet oberoende uppsättningar av storlek r .
• Maxgradsordningen för en vertexdelmängd $A\subset V$ är ordningen av hörnen i A efter deras grad i den inducerade subgrafen G $\displaystyle G[A]}$ .

Kleitman-Winston algoritm

Följande algoritm ger ett litet "fingeravtryck" för varje oberoende uppsättning i en graf och en deterministisk funktion av fingeravtrycket för att konstruera en inte alltför stor delmängd som innehåller hela den oberoende uppsättningen

Fix graf G , oberoende mängd $I\in \ell (G)$ och positivt heltal $q\leq |I|$ .

1. Initiera : låt $A=V(G),S=\emptyset$ .
2. Iterera för $s=1,2,\ldots ,q$ :
   • Konstruera maxgradsordningen för $A,\,(v_{1},\ldots v_{|A|})$
   • Hitta det minimala indexet $j_{s}$ så att $v_{j_{s}}\in I$ (dvs. vertexen i A av största graden i inducerad subgraf G[A ] )
   • Låt ${\displaystyle S\leftarrow S\cup \{v_{j_{s }}\},\,A\leftarrow A\backslash (\{v_{1},\ldots ,v_{j_{s}}\}\cup N(v_{j_{s}}))} ,$ där $N(v)$ är grannskapet till vertex $v$ .
3. Mata ut vektorn $(j_{1},\ldots ,j_{q})$ och vertexmängden $A\cap I$ .

Analys

Genom konstruktion har utdata från ovanstående algoritm egenskapen att $\{v_{ j_{1}},\ldots ,v_{j_{q}}\}\subset I\subset \{v_{j_{1}},\ldots ,v_{j_{q}}\}\cup (A\ cap I)$ , notera att $A\cap I$ är en vertexdelmängd som helt bestäms av $\{j_{1},\ldots ,j_ {q}\}$ och inte annars en funktion av $I$ . För att understryka detta skriver vi $A=A(j_{1},\ldots ,j_{q})$ . Vi observerar också att vi kan rekonstruera mängden $S=\{v_{j_{1}},\ldots, v_{j_{q}}\}=S(j_{1},\ldots j_{q})$ i ovanstående algoritm bara från vektorn $(j_{1} ,\ldots ,j_{q})$ .

Detta tyder på att $S$ kan vara ett bra val av ett fingeravtryck och $S(j_{1},\ldots j_{q})\cup A(j_{1},\ldots ,j_{q})$ ett bra val för en container . Mer exakt kan vi binda antalet oberoende uppsättningar av $G$ av någon storlek $r\geq q$ som en summa över utdatasekvenser $( j_{1},\ldots j_{q})$

$i(G,r)=\sum _{(j_{s})_{s=1}^{q}}i(G[A(j_{1},\ldots j_ {q})],rq)\leq \sum _{(j_{s})}{A(j_{1},\ldots j_{q}) \choose rq}$ ,

där vi kan summera över $r$ för att få en gräns för det totala antalet oberoende uppsättningar av grafen:

$i(G)=\summa _{r=0}^{q-1}{n \choose r}+\summa _{(j_{s})_{s=1}^{q}} i(G[A(j_{1},\ldots j_{q})])\leq \sum _{r=0}^{q-1}{n \välj r}+\summa _{(j_{ s})}2^{|A(j_{1},\ldots j_{q})|}$ .

När vi försöker minimera denna övre gräns vill vi välja $q$ som balanserar/minimerar dessa två termer. Detta resultat illustrerar värdet av att ordna hörn efter maximal grad (för att minimera ${\displaystyle |A(j_{1},\ldots j_{q})|} )$ .

Lemmas

Ojämlikheterna och observationerna ovan kan anges i en mer generell miljö, skild från en explicit summa över vektorer ( $\displaystyle (j_{s})}$ .

Lemma 1: Givet en graf $G$ med $n$ och antag att heltal $q$ och reella tal $R,\beta \in [ 0,1]$ uppfyller $R\geq e^{-\beta q}n$ . Antag att varje inducerad subgraf på åtminstone $R$ hörn har kantdensitet åtminstone $\beta$ . Sedan för varje heltal $r\geq q$ ,

$i(G,r)\leq {n \choose q}{R \choose rq}.$

Lemma 2: Låt $G$ vara en graf på $n$$R,D$ och antag att ett heltal $q$ och reella är valda så att $n\leq R+qD$ . Om alla delmängder $U$ av minst $R$ hörn har minst $D|U|/2$ kanter, då finns det en samling ${\mathcal {F}}$ av delmängder av $q$ hörn ("fingeravtryck") och en deterministisk funktion ${\displaystyle f:{\mathcal {C}}\rightarrow {\mathcal {P}}(V(G)} ,$ så att för varje oberoende mängd $I\subset V(G)$ , det finns $S\in {\mathcal {F}}$ så att $S\subset I \subset f(S)\cup S$ .

Hypergraph container lemma

Informellt berättar hypergrafbehållarens lemma att vi kan tilldela ett litet fingeravtryck $S\subset I$ till varje oberoende uppsättning, så att alla oberoende uppsättningar med samma fingeravtryck tillhör samma större uppsättning, $C=f(S)$ , den associerade behållaren, som har storleken avgränsad från antalet hörn i hypergrafen. Vidare är dessa fingeravtryck små (och därför finns det få behållare), och vi kan övergränsa deras storlek på ett i huvudsak optimalt sätt med hjälp av några enkla egenskaper hos hypergrafen.

Vi minns följande notation associerad med $k$ enhetlig hypergraf ${\mathcal {H}}$ .

• Definiera $\Delta _{l}({\mathcal {H}}):=\max\{d_{H}(A)\mid A\subset V({\mathcal {H}}), |A|=l\}$ för positiva heltal $1\leq l\leq k$ , där $d_{\mathcal {H}}(A)=|\{e\in E({\mathcal {H}})\mid A\subset e\}|$ .
• Låt ${\mathcal {I}}({\mathcal {H}})$ vara samlingen av oberoende uppsättningar av ${\mathcal {H}}$ . $I$ kommer att beteckna någon sådan oberoende uppsättning.

Påstående

Vi anger versionen av detta lemma som finns i ett verk av Balogh, Morris, Samotij och Saxton

Låt ${\mathcal {H}}$ vara en $k$ -uniform hypergraf och anta att för varje $l\in \{1, 2,\ldots ,k\}$ och några $b,r\in \mathbb {N}$ , vi har att $\Delta _{l}(H)\leq \left({\frac {b}{|V(H)|}}\right)^{l-1}{\frac {|E(H) )|}{r}}$ . Sedan finns det en samling ${\mathcal {C}}\subset {\mathcal {P}}(V(H))$ och en funktion $f:{\mathcal {P}}(V(H))\högerpil {\mathcal {C}}$ så att

• för varje $I\in {\mathcal {I}}(H)$ finns det $S\subset I$ med $|S|\leq (k-1)b$ och $I\subset f(S)$ .
• $|C|\leq |V(H)|-\delta r$ för varje $C\in {\mathcal {C}}$ och $\delta =2^{-k(k+1)}$ .

Exempelapplikationer

Vanliga grafer

Övre gräns för antalet oberoende uppsättningar

Vi kommer att visa att det finns en absolut konstant C så att varje $n$ -vertex $d$ -reguljär graf $G$ uppfyller $i(G)\leq 2^{\left(1+C{\sqrt {\frac {\log d}{d}}}\right){\frac {n}{2} }}$ .

Vi kan binda antalet oberoende uppsättningar av varje storlek $r$ genom att använda trivialgränsen ${\displaystyle i(G ,r)\leq {n \choose r}\leq {n \choose n/10}\leq 2^{0.48n}} för r ≤ n / 10 {\displaystyle$ r $}$ . För större $r$ , ta $\beta >10/n,q=\lfloor 1/\beta \rfloor ,R={\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} .$ Med dessa parametrar uppfyller d -regular graf $G$ villkoren för Lemma 1 och därmed,

$i(G,r)\leq {n \choose q}{R \choose rq}\leq {n \choose q}{{\frac {n}{2}}+{\frac {\beta n ^{2}}{2d}} \choose rq}\leq \left({\frac {en}{q}}\right)^{q}{{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}} \choose rq}\leq (e\beta n)^{\lfloor 1/\beta \rfloor }{{\frac {n}{2}}+{\ frac {\beta n^{2}}{2d}} \choose rq}.$

Att summera över alla $0\leq r\leq n$ ger

$i(G)\leq 2^{0.49n}+2^ {{\frac {n}{2}}+{\frac {\beta n^{2}}{2d}}+\lfloor 1/\beta \rfloor \log _{2}(e\beta n)}$ ,

vilket ger önskat resultat när vi kopplar in $\beta ={\sqrt {d\log d}}/n.$

Summafria set

En mängd $A$ av element i en abelisk grupp kallas summafri om det inte finns några $x,y,z\in A$ som uppfyller ${\ displaystil x+y=z}$ . Vi kommer att visa att det finns högst $2^{(1/2+o(1))n}$ summafria delmängder av $[n]:=\{1,2,\ldots ,n\}$ .

Detta kommer att följa av våra ovanstående gränser för antalet oberoende uppsättningar i en vanlig graf. För att se detta måste vi konstruera en hjälpgraf. Vi observerar först att upp till termer av lägre ordning kan vi begränsa vårt fokus till summafria mängder med minst $n^{2/3}$ element mindre än $n/2$ (eftersom antalet delmängder i komplementet till detta är högst $(n/2)^{n^{2/3}}2^ {n/2+1}$ ).

Givet någon delmängd ${\displaystyle S\subset \{1,2,\ldots ,\lceil n/2\rceil -1\}} ,$ definierar vi en hjälpgraf $G_{S}$ med vertexuppsättning $[n]$ och kantmängd $\{\{x,y\}\mid x+s\equiv y{\pmod {n}}{\text{ för vissa }}s\in S\cup (-S )\}$ och observera att vår hjälpgraf är $2|S|$ regelbundet eftersom varje element i S är mindre än $n/2$ . Sedan om $S_{A}$$\displaystyle A\subset [n]}$ de minsta $n^{2/3}$ elementen i delmängd , set $A\backslash S_{A}$ är en oberoende mängd i grafen $G_{S_{A}}$ . Sedan, genom vår tidigare gräns, ser vi att antalet summafria delmängder av $[n]$ är som mest

$(n/2)^{n^{2/3}}2^{n/2+}+{n/2 \choose n^{2/3}}2^{(1+O(n) ^{-1/3}{\sqrt {\log n}})){\frac {n}{2}}}\leq 2^{(1/2+O(n^{-1/3}\ log n))n}.$

Triangelfria grafer

Vi ger en illustration av hur man använder hypergrafbehållarens lemma för att svara på en uppräkningsfråga genom att ge en asymptotiskt snäv övre gräns för antalet triangelfria grafer med $n$ hörn.

Informellt uttalande

Eftersom tvådelade grafer är triangelfria, är antalet triangelfria grafer med $n$ hörn minst $2^{\lfloor n^{2}/4\rfloor }$ , erhållen genom att räkna upp alla möjliga subgrafer i den balanserade kompletta tvådelade grafen $K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$ .

Vi kan konstruera en extra 3 -enhetlig hypergraf H med vertexmängd $V(H)=E(K_{n})$ och kantmängd $E(H)=\{\{e_{1},e_ {2},e_{3}\}\subset E(K_{n})=V(H)\mid e_{1},e_{2},e_{3}{\text{ bildar en triangel}}\ }$ . Denna hypergraf "kodar" trianglar i den meningen att familjen av triangelfria grafer på $n$ hörn är exakt samlingen av oberoende uppsättningar av denna hypergraf, ${\mathcal {I}} (H)$ .

Hypergrafen ovan har en fin gradfördelning: varje kant av $K_{n}$ , och därmed vertex i $V(H)$ ingår i exakt $n -2$ trianglar och varje par av element i $V(H)$ ingår i högst 1 triangel. Genom att tillämpa hypergrafbehållarelemmat (iterativt) kan vi därför visa att det finns en familj av $n^{O(n^{3/2})}$ behållare som var och en innehåller några trianglar som innehåller varje triangelfri graf/oberoende uppsättning av hypergrafen.

Övre gräns för antalet triangelfria grafer

Vi specialiserar först det generiska hypergrafbehållarelemmat till 3-uniforma hypergrafer enligt följande:

Lemma: För varje $c>0$ finns det $\delta >0$ så att följande gäller. Låt $H$ vara en 3-enhetlig hypergraf med medelgrad $d\geq 1/\delta$ och antag att $\Delta _{1}(H)\leq cd,\Delta _{2}(H)\leq c{\sqrt {d}}$ . Då finns det en samling ${\mathcal {C}}\subset {\mathcal {P}}(V(H))$ av högst $|{\mathcal {C}}|\leq {|V(H)| \välj |V(H)|/{\sqrt {d}}}$ behållare så att

• för varje ${\displaystyle I\in {\mathcal {I}}(H)} ,$ finns det $I\subset C\in {\mathcal {C}}$
• $|C|\leq (1-\delta )|V(H)|$ för alla $C\in {\mathcal {C}}$

Att tillämpa detta lemma iterativt kommer att ge följande teorem (som bevisas nedan):

Sats: För alla $\epsilon >0$ finns det $C>0$ så att följande gäller. För varje positivt heltal n finns det en samling ${\mathcal {G}}$ av grafer på n hörn med $|{\mathcal {G}}|\leq n^{Cn^{3/2}}$ så att

• varje $G\in {\mathcal {G}}$ har färre än $\epsilon n^{3}$ trianglar,
• varje triangelfri graf på $n$ hörn finns i vissa $G\in {\mathcal {G}}$ .

Bevis: Betrakta hypergrafen $H$ definierad ovan. Som observerats informellt tidigare, uppfyller hypergrafen $|V(H)|={n \choose 2},\Delta _{2}(H)=1 ,d(v)=n-2$ för varje $v\in V(H)$ . Därför kan vi tillämpa ovanstående Lemma på $H$ med $c=1$ för att hitta en samling ${\mathcal {C}}$ av $n^{O(n^{3/2})}$ delmängder av $E(K_{n})$ (dvs. grafer på $n$ hörn) såsom den där

• varje triangelfri graf är en subgraf av några $C\in {\mathcal {C}}$ ,
• varje $C\in {\mathcal {C}}$ har som mest $(1-\delta ){n \choose 2}$ kanter.

Detta är inte riktigt lika starkt som resultatet vi vill visa, så vi kommer iterativt att tillämpa containerlemma. Anta att vi har någon behållare $C\in {\mathcal {C}}$ med minst $\epsilon n^{3}$ trianglar. Vi kan applicera behållarlemmat på den inducerade subhypergrafen $H[C]$ . Den genomsnittliga graden av $H[C]$ är minst $6\epsilon n$ , eftersom varje triangel i $C$ är en kant i ${ \displaystyle H[C]}$ , och denna inducerade subgraf har som mest ${n \choose 2}$ hörn. Således kan vi tillämpa Lemma med parametern ${\displaystyle c=1/\epsilon } ,$ ta bort $C$ från vår uppsättning behållare, ersätta den med denna uppsättning behållare, behållarna täcker ${\mathcal {I}}(H[C])$ .

Vi kan fortsätta att iterera tills vi har en slutlig samling av behållare ${\mathcal {C}}$ som var och en innehåller färre än $\epsilon n^{3}$ trianglar. Vi observerar att denna samling inte kan vara för stor; alla våra inducerade subgrafer har högst ${n \choose 2}$ hörn och medelgrad minst $6\epsilon n$ , vilket betyder att varje iteration resulterar i högst $n^{O(n^{3/2})}$ nya behållare. Vidare krymper behållarstorleken med en faktor på $1-\delta$ varje gång, så efter ett begränsat (beroende på ${\displaystyle \epsilon } )$ antal iterationer kommer den iterativa processen att avslutas.

Se även

Oberoende mängd (grafteori) Szemerédis sats Szemerédi regularitetslemma