Lemma för borttagning av hypergraf

I grafteorin säger lemmat för borttagning av hypergrafer att när en hypergraf innehåller få kopior av en given sub-hypergraf, så kan alla kopior elimineras genom att ta bort ett litet antal hyperkanter. Det är en generalisering av grafborttagningslemma . Det speciella fallet där grafen är en tetraeder kallas lemma för borttagning av tetraeder. Det bevisades först av Nagle, Rödl, Schacht och Skokan och, oberoende, av Gowers.

Lemmat för borttagning av hypergrafer kan användas för att bevisa resultat som Szemerédis sats och Szemerédis multidimensionella sats.

Påstående

Lemmat för borttagning av hypergraf anger att för alla $\varepsilon ,r,m>0$ finns det $\delta =\delta (\ varepsilon ,r,m)>0$ så att för varje $r$ -uniform hypergraf $H$ med $m$ hörn gäller följande: om $G$ är någon $n$ -vertex $r$ -uniform hypergraf med högst $\delta n^{v(H)}$ subgrafer som är isomorfa till $H$ , då är det möjligt att eliminera alla kopior av $H$ från $G$ genom att som mest ta bort $\varepsilon n^{r}$ hyperkanter från $G$ .

En likvärdig formulering är att för alla grafer $G$ med $o(n^{v(H)})$ kopior av $H$ , kan vi eliminera alla kopior av $H$ från $G$ genom att ta bort $o(n^{r})$ hyperkanter.

Bevis idé om hypergrafborttagningslemma

Den höga idén med beviset liknar den för grafborttagningslemma . Vi bevisar en hypergrafversion av Szemerédis regularitetslemma (dela upp hypergrafer i pseudoslumpmässiga block) och ett räknelemma (uppskatta antalet hypergrafer i ett lämpligt pseudoslumpmässigt block). Den viktigaste svårigheten i beviset är att definiera den korrekta uppfattningen om hypergrafisk regelbundenhet. Det gjordes flera försök att definiera "partition" och "pseudoslumpmässiga (vanliga) block" i en hypergraf, men ingen av dem kan ge ett starkt räkningslemma. Den första korrekta definitionen av Szemerédis regularitetslemma för allmänna hypergrafer ges av Rödl et al.

I Szemerédis regularitetslemma utförs partitionerna på hörn (1-hyperedge) för att reglera kanter (2-hyperedge). Men för $k>2$ , om vi helt enkelt reglerar $k$ -hyperedges med endast 1-hyperedge, kommer vi att förlora information om alla $j$ -hyperedges i mitten där $1<j<k$ , och misslyckas med att hitta ett räknande lemma. Den korrekta versionen måste partitionera $(k-1)$ -hyperedges för att reglera $k$ -hyperedges. För att få mer kontroll över $(k-1)$ -hyperedges, kan vi gå en nivå djupare och partitionera på ( $\displaystyle (k-2)}$ -hyperedges för att reglera dem, etc. I slutändan kommer vi att nå en komplex struktur för att reglera hyperkanter.

Bevisidé för 3-uniforma hypergrafer

Till exempel visar vi en informell 3-hypergrafversion av Szemerédis regularitetslemma, som först gavs av Frankl och Rödl. Betrakta en partition av kanter $E(K_{n})=G_{1}^{(2)}\cup \dots \ kopp G_{l}^{(2)}$ så att det för de flesta trianglar $(i,j,k),$ finns många trianglar ovanpå ${\displaystyle \left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right).} Vi säger$ att $\left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{( 2)}\right)$ är "pseudorandom" i den meningen att för alla subgrafer $A_{i}^{(2)}\subset G_{i}^{ (2)}$ med inte för få trianglar ovanpå $\left(A_{i}^{(2)}, A_{j}^{(2)},A_{k}^{(2)}\höger),$ vi har

\left|d\left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)-d \left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right)\right|\leq \varepsilon ,

där

d(X,Y,Z)

anger andelen

3

-uniform hyperedge i

G^{(3)}

bland alla trianglar ovanpå

(X,Y,Z)

.

Vi definierar sedan en vanlig partition som en partition där de trippel av delar som inte är reguljära högst utgör en $\varepsilon$ bråkdel av alla trippel av delar i partitionen.

Utöver detta behöver vi ytterligare regularisera $G_{1}^{(2)},\dots ,G_{l}^{(2)}$ via en partition av vertexuppsättningen. Som ett resultat har vi den totala data för hypergrafregelbundenhet enligt följande:

en partition av $E(K_{n})$ i grafer så att $G^{(3)}$ sitter pseudoslumpmässigt överst;
en partition av $V(G)$ så att graferna i (1) är extremt pseudoslumpmässiga (på ett sätt som liknar Szemerédis regularitetslemma ).

Efter att ha bevisat hypergrafreguljäritetslemma kan vi bevisa ett hypergrafräkningslemma. Resten av beviset fortsätter på samma sätt som det i grafborttagningslemmat .

Bevis för Szemerédis sats

Låt $r_{k}(N)$ vara storleken på den största delmängden av $\{1,\ldots ,N\}$ som inte innehåller en längd $k$ aritmetisk progression. Szemerédis sats säger att $r_{k}(N)=o(N)$ för vilken konstant ${\displaystyle k} som helst$ . Den höga idén med beviset är att vi konstruerar en hypergraf från en delmängd utan någon längd $k$ aritmetisk progression, och sedan använder vi grafborttagningslemma för att visa att denna graf inte kan ha för många hyperkanter, vilket i sin tur visar att den ursprungliga delmängden får inte vara för stor.

Låt $A\subset \{1,\ldots ,N\}$ vara en delmängd som inte innehåller någon längd $k$ aritmetisk progression. Låt $M=k^{2}N+1$ vara ett tillräckligt stort heltal. Vi kan tänka oss $A$ som en delmängd av $\mathbb {Z} /M\mathbb {Z}$ . Tydligen, om $A$ inte har längd $k$ aritmetisk progression i $\mathbb {Z}$ , har den inte heller längd $k$ aritmetisk progression i $\mathbb {Z} /M\mathbb {Z}$ .

Vi kommer att konstruera en $k$ -partite $(k-1)$ -uniform hypergraf $G$ från $A$ med delar ${\displaystyle V_{1},V_{2},\ldots ,V_{k}} ,$ som alla är $M$ element vertexuppsättningar indexerade av $\mathbb {Z} /M\mathbb {Z}$ . För varje ${\displaystyle 1\leq i\leq k} lägger$ $(v_{j}\ i V_{j})_{j\in [k]\setminus \{i\}}$ till en hyperedge bland hörn om och endast om $\sum _{j\neq i}(ji)v_{j}\in A.$ Låt $H$ vara hela $k$ -partiten $(k-1)$ -enhetlig hypergraf. Om $G$ innehåller en isomorf kopia av $H$ med hörn $v_{1},\ldots ,v_{k}$ så är $\alpha _{i}=\summa _{j\neq i}(ji)v_{j}\in A$ för valfri ${\ displaystyle 1\leq i\leq j}$ . Observera dock att $\alpha _{i}$ är en längd $k$ aritmetisk progression med gemensam skillnad $\alpha _{ i+1}-\alpha _{i}=-\summa _{j}v_{j}$ . Eftersom $A$ inte har någon längd $k$ aritmetisk progression, måste det vara så att $\alpha _{1}=\cdots =\alpha _{k }$ , så $\sum _{j}v_{j}=0$ .

Således, för varje hyperedge $(v_{j}\in V_{j})_{j\in [k]\setminus \{i\ }}$ , kan vi hitta en unik kopia av $H$ som denna kant ligger i genom att hitta $v_{i}=-\summa _{j\neq i}v_{j}$ . Antalet kopior av $H$ i $G$ är lika med ${\frac {1}{k }}e(G)=O(N^{k-1})=o(N^{k})$ . Därför, genom lemma för borttagning av hypergraf, kan vi ta bort $o(N^{k-1})$ kanter för att eliminera alla kopior av $H$ i $G$ . Eftersom varje hyperkant av $G$ finns i en unik kopia av $H$ , för att eliminera alla kopior av $H$ i $G$ , måste vi ta bort åtminstone $e(G)/k$ kanter. Således, $e(G)=o(N^{k-1})$ .

Antalet hyperkanter i $G$ är ${\displaystyle kM^{k-2}|A|=o(N^{k-1})} ,$ vilket drar slutsatsen att $|A|=o(N)$ .

Denna metod ger vanligtvis inte en bra kvantitativ gräns, eftersom de dolda konstanterna i lemma för borttagning av hypergrafer involverar den omvända Ackermann-funktionen. För en bättre kvantitativ gräns, bevisade Gowers att $|A|\leq {\frac {N}{(\log \log N)^{c_{k}}}}$ för någon konstant ${\ displaystyle c_{k}}$ beroende på $k$ . Det är den bästa gränsen för $k\geq 5$ hittills.

Ansökningar

Lemmat för borttagning av hypergrafer används för att bevisa den flerdimensionella Szemerédi-satsen av J. Solymosi. Påståendet är att vilken som helst för varje ändlig delmängd $S$ av ${\displaystyle \mathbb {Z} ^{r}} ,$ vilken som helst $\delta >0$ och vilken som helst $n$ tillräckligt stor, varje delmängd av $[n]^{r}$ av storleken minst $\delta n^{r}$ innehåller en delmängd av formen $a\cdot S+d$ , det vill säga en utvidgad och översatt kopia av $S$ . Hörnsatsen är ett specialfall när $S=\{(0,0),(0,1),(1,0)\}$ .
Det används också för att bevisa polynomet Szemerédi-satsen, Szemerédi-satsen med det finita fältet och den finita abelska gruppen Szemerédi-satsen.

Se även