Abstrakt. De viktigaste resultaten av detta dokument är regelbundenhet och räkna lemmas för 3-uniform hypergraphs. En kombination av dessa två resultat ger ett nytt bevis på en teorem av Frankl och Rödl, varav Szemerédis sats för aritmetiska progressioner av längd 4 är en anmärkningsvärd konsekvens. Frankl och Rödl bevisar också regelbundenhet och räknar lemmas, men bevisen här, och även uttalandena, är betydligt annorlunda. I denna rapport ingår också ett bevis på Szemerédis regelbundenhet lemma, några grundläggande fakta om kvasirandomness för grafer och hypergrafer, och detaljerade förklaringar av motivationen för de definitioner som används. Punkt 1 ska ersättas med följande: Inledning. Ett av de viktigaste verktygen i extrem grafteori är Szemerédis regelbundenhet lemma. Eftersom en graf G med vertex som V, regelbundenheten lemma ger en partition av V i uppsättningar V 1,. .., V K, sådan att för nästan varje par (i, j) den inducerade bipartite graf G(V i, V j ) (det vill säga begränsningen av G till uppsättningen av kanter xy sådan att x  till V i och y  till V j ) beter sig som en typisk slumpmässig graf av samma densitet. Detta resultat har varit ett så viktigt verktyg i grafteorin och har så många tillämpningar att det är mycket naturligt att försöka hitta en generalisering som kommer att hjälpa till med extrema problem för hypergrafer. Det finns faktiskt en ansökan som, även på egen hand, ger tillräcklig motivation för ett projekt av detta slag. År 1976 upptäckte Ruzsa och Szemerédi ett enkelt sätt att härleda Roths teorem (Szemerédis sats för progression av längd 3) från regelbundenheten lemma [RS], och under många år har Vojta Rödl, med flera medarbetare, haft ett mycket lovande program för att få ett nytt bevis på det fullständiga Szemerédi teorem genom att generalisera argumentet Ruzssa-Szemerédi. För att göra detta behöver man inte bara en regelbunden lemma utan också en så kallad "räknande lemma", som säger, mycket grovt, att en tillräckligt kvasirandom hypergraph kommer att innehålla små subhypergrafer med ungefär rätt frekvens. (Detta sätt att uttrycka det, även om det kommer att göra nu, är i själva verket så grov att vara positivt vilseledande -se §5 för en förklaring av varför.) Under 2002 genomförde Frankl och Rödl detta program för 3-uniforma hypergrafer, vilket gav ett nytt bevis på Szemerédis teorem vid progression av längd fyra [FR2]. Tio år tidigare hade de visat sig vara en regelbunden lemma för k-uniforma hypergrafer [FR1], men det var mycket svårare att få en lämplig räknande lemma att följa med. Huvudsyftet med detta dokument är att förklara de idéer som ligger bakom ett dokument av författaren [G3], vars huvudsakliga framsteg är att fastställa en räknande lemma för k-uniform hypergraphs, men också en regelbunden lemma som inte är helt samma som Frankl och Rödl. Dessa två resultat innebär inte bara Szemerédis teorem i full allmänhet, utan också, vilket redan har observerats av Solymosi [S2], dess flerdimensionella version. Detta resultat hade tidigare endast erhållits genom Furstenbergs ergodiska teorimetod [FK]. För att förklara hur dessa resultat bevisas kommer vi att koncentrera oss på fallet med 3-uniforma hypergrafer, eftersom generaliseringen till k-uniforma hypergrafer, även om de är notationellt mer komplicerade, inte är annorlunda på ett väsentligt sätt. De viktigaste resultaten av detta dokument är därför inte nya, men poängen är att definitionerna och bevisen skiljer sig från Frankl och Rödl och är mer generaliserade. Den viktigaste nyheten i detta dokument förekommer därför på teknisk nivå. Men eftersom detta är ett område där det är lätt att bli överväldigad av tekniska svårigheter, är tekniska förenklingar av mer än rent tekniskt intresse. Med detta sagt, Nagle, Rödl och Schacht har också nyligen generaliserat Frankl-Rödl strategi för k-uniform hypergraphs [NRS], i arbete oberoende av det arbete som diskuteras här. I den sista delen av detta dokument förklarar vi vad den största skillnaden är mellan Frankl-Rödl-metoden och den som ges här. Metoderna i detta dokument har sina rötter i en del av det analytiska beviset på Szemerédis teorem som ges av författaren i [G1,2]. Ett annat syfte med tidningen är att förklara detta samband. Vi kommer då och då att anta en nickande bekantskap med idéerna i [G1] (som inte används här på något formellt sätt, men som kastar ljus över några av våra argument): annars är denna uppsats fristående. Läsaren uppmanas att inte skjutas upp av papperets längd. De viktigaste resultaten - räkning och regelbundenhet lemmas för 3-uniform hypergraphs - behandlas i §6 respektive §8. Resten av artikeln består av diskussion, motiverande exempel och välkända bakgrundsresultat i grafteori. Även sektionerna med de viktigaste resultaten innehåller en hel del diskussion, snarare än att skrivas så tätt som möjligt. Om du letar efter ett kort bevis på Szemerédis teorem för progression av längd fyra, då den "sanna" längden av detta papper är kortare än för andra papper som fastställer samma resultat. Nästan alla bevis är enkla tillämpningar av den andra perioden metod, annars känd som Cauchy-Schwarz ojämlikhet. Till att börja med är här en kort skiss av en variant av Ruzsas och Szemerédis argument som var utgångspunkten för Rödls program. Deras första steg var att bevisa följande enkla uttalande om grafer. 2 Teorem 1.1. För varje konstant c > 0 finns en konstant a > 0 med följande egenskap. Om G är någon graf med n hörn som innehåller som mest en 3 trianglar, då är det möjligt att ta bort som mest cn 2 kanter från G för att göra det triangelfritt. Sketch-bevis. För alla med erfarenhet av regelbundenheten lemma, är detta ett enkelt och standard argument (men det var naturligtvis en allvarlig prestation av Ruzsa och Szemerédi att märka att denna typ av resultat var både lätt och betydande). Först, tillämpa regelbundenheten lemma för att få en c/4-regelbunden partition av G i vertex uppsättningar V 1,. .., V K av nästan lika storlek. Ta bort alla kanter som tillhör par (V i, V j ) som misslyckas med att vara c/4-regelbunden eller som har densitet som mest c/2. Resultatet är en delgraf G av G sådan att varje kant tillhör ett par (V i, V j ) som är c/4 regelbunden och har densitet minst c/2, och antalet kanter vi har tagit bort från G för att uppnå detta är mindre än cn 2. Det återstår att visa att G är triangelfri. Men om xyz är en triangel i G då måste vi ha x  till V i, y  till V j och z  till V k med paren (V i, V j ), (V j, V k ) och (V i, V k ) alla c/4 regelbunden och av densitet minst c/2. Det är inte svårt att härleda från detta att antalet trianglar i G är minst c 3 N 3 /256K 3. Eftersom K endast beror på c bevisas resultatet.
Den probabilistiska konstruktionen av exemplen i Theorem 4 är välkänd i studien av kvasirandomness för hypergrafer, se t.ex. diskussionen i Ref avsnitt 5].
Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
{'venue': 'Comb. Probab. Comput.', 'journal': 'Comb. Probab. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}