Problemet med Ruja - Semeredi

Rouge-Szemeredi eller (6,3)-problemet spørger om det maksimale antal kanter i en graf, hvor enhver kant hører til en enkelt trekant. Tilsvarende spørger problemet om det maksimale antal kanter i en balanceret todelt graf, hvis kanter kan dekomponeres til et lineært antal genererede matchninger , eller det maksimale antal tripler, der kan vælges fra punkter, således at hvert sjette punkt indeholder højst to tredobler. Problemet er opkaldt efter Imre Z. Rougy og Endre Szemeredy , som var de første til at bevise, at svaret er mindre end en langsomt voksende (men endnu ukendt) faktor [1] . $n$ $n^{2}$

Ækvivalens mellem formuleringer

Følgende spørgsmål har svar, der er asymptotisk ækvivalente - de adskiller sig ikke mere end en konstant faktor fra hinanden [1] :

Hvad er det maksimalt mulige antal kanter i en toppunktsgraf, hvor enhver kant tilhører en enkelt trekant? [2] Grafer med denne egenskab kaldes lokalt lineære grafer [3] eller lokalt matchende grafer [4] . $n$
Hvad er det maksimalt mulige antal kanter i en todelt graf med spidser på hver side af dens del, hvis kanter kan opdeles i genererede undergrafer , som hver er en matchende [1] ? $n$ $n$
Hvad er det største antal tripler af point, der kan vælges fra de givne point, således at alle seks point højst indeholder to af de valgte tripler? [5] Rouge-Szemeredi-problemet søger et svar på disse tilsvarende spørgsmål. $n$

For at reducere det genererede matchningsproblem for en todelt graf til et enkelt trekantproblem skal du tilføje et sæt grafhjørner, en for hver genereret matchning, og tilføje kanter fra hjørnerne og den todelte graf til et toppunkt i dette tredje sæt, når en kant på den todelte graf hører til den genererede matchning . Som et resultat opnår vi en afbalanceret tredelt graf med hjørner med trekantens unikke egenskab. I den anden retning kan enhver graf med egenskaben trekantens unikhed reduceres til en afbalanceret tredelt graf ved at fordele toppunkter over tre lige store sæt tilfældigt og bevare de trekanter, der definerer andelsfordelingen. Dette resulterer i et konstant forhold mellem trekanter og kanter. En afbalanceret tredelt graf med egenskaben trekantet unikhed kan transformeres til en opdelt todelt graf ved at fjerne en af dens tre undersæt af toppunkter, hvilket skaber en genereret matchning på naboerne til hver af de fjernede toppunkter. $n$ $u$ $v$ $w$ $UV$ $w$ $3n$

For at transformere en graf med en unik trekant pr. kant til et system af tripler, tager vi trekanterne på grafen som tripler. Ingen seks punkter kan omfatte tre trekanter, uden at to af de tre trekanter deler en kant, eller at alle tre trekanter danner en fjerde trekant, der deler kanter med hver af dem. I den anden retning, for at konvertere et tredobbelt system til en graf, skal du først fjerne ethvert sæt af fire punkter, der indeholder to tripler. Disse fire punkter kan ikke være til stede i andre tripler, og kan derfor ikke tilføje mere end et lineært antal tripler. Nu danner vi en graf, der forbinder ethvert par af punkter, der hører til en af de resterende tripletter.

Nedre grænse

En næsten andengradsgrænse for Rouge-Szemeredi-problemet kan udledes af resultatet af Felix Behrend, ifølge hvilket tal modulo et ulige primtal har store Salem-Spencer-sæt , delmængder af størrelse uden tre-term aritmetiske progressioner [6 ] . Behrends resultat kan bruges til at konstruere tredelte grafer, hvor hvert segment har et toppunkt, grafen indeholder kanter, og hver kant tilhører en enkelt trekant. Så er antallet af kanter ifølge denne konstruktion også [5] . $s$ $EN$ ${\displaystyle |A|=p/e^{O({\sqrt {\log p))))$ $s$ $3|A|p$ $n=3p$ ${\displaystyle n^{2}/e^{O({\sqrt {\log n)))))$

For at konstruere en graf af denne type ud fra Berends delmængde fri for aritmetiske progressioner , nummererer vi hjørnerne i hver andel fra til og bygger trekanter af formen modulo for hvert af intervallet fra til og hvert tal hører til . For eksempel får vi med og som et resultat en afbalanceret tredelt graf med 9 hjørner og 18 kanter, vist i figuren. Grafen dannet ved at kombinere disse trekanter har den ønskede egenskab, at hver kant tilhører præcis én trekant. Hvis dette ikke var tilfældet, ville der være en trekant , hvor , og tilhører , hvilket bryder med antagelsen om, at der ikke er nogen aritmetiske progressioner i [5] . $EN$ $0$ $p-1$ $(x,x+a,x+2a)$ $s$ $x$ $0$ $p-1$ $-en$ $EN$ $p=3$ $A=\{\pm 1\}$ $(x,x+a,x+a+b)$ $-en$ $b$ $c=(a+b)/2$ $EN$ $(a,c,b)$ $EN$

Øvre grænse

Szemeredis regularitetslemma kan bruges til at bevise, at enhver løsning på Rouzi-Szemeredi-problemet højst har kanter eller trekanter [5] . En stærkere version af Jacob Fox Count Deletion Lemma indebærer, at størrelsen af løsningen ikke overstiger . Her og er repræsentanter for notationen "o lille" og , og betyder itereret logaritme . Fox beviste, at i enhver graf med hjørner og trekanter, for nogle kan man finde en undergraf uden trekanter ved at fjerne højst kanter [7] . I en graf med egenskaben triangle uniqueness er der (naturligtvis) trekanter, så resultatet kommer med . Men i denne graf fjerner hver kantfjernelse kun én trekant, så antallet af kanter, der skal fjernes for at eliminere alle trekanter, er lig med antallet af trekanter. $o(n^{2})$ ${\displaystyle n^{2}/e^{\Omega (\log ^{*}n)))$ $o$ $\Omega$ $\Omega$ $\log^*$ $n$ $O(n^{3-\delta })$ $\delta>0$ ${\displaystyle n^{2}/e^{\Omega (\log ^{*}n)))$ $O(n^{2})$ $\delta=1$

Historie

Problemet er opkaldt efter Imre Z. Rougy og Endre Szemeredy , som studerede problemet i formuleringen af tredobbelt point i en publikation fra 1978 [5] . Problemet blev imidlertid tidligere undersøgt af W. J. Brown, Pal Erdős og Vera T. Szos i to publikationer i 1973, hvor de beviste, at det maksimale antal tripler kan være [8] , og formodede, at det faktisk er lig med [9] ] . Ruzsa og Szemeredy gav (ulige) næsten kvadratiske øvre og nedre grænser for problemet, hvilket væsentligt forbedrede den nedre grænse for Brown, Erdős og Sosa og beviset for deres formodning [5] . $\Omega (n^{3/2})$ $o(n^{2})$

Ansøgninger

Eksistensen af tætte grafer, der kan dekomponeres til store genererede matchninger, er blevet brugt til at konstruere effektive tests for, om en boolsk funktion er lineær, en nøglekomponent i PCP-sætningen i beregningskompleksitetsteori [10] . I teorien om egenskabskontrolalgoritmer , blev velkendte resultater om Rouzi-Szemeredi-problemet brugt til at vise, at det er muligt at kontrollere, om en graf indeholder en given undergraf (med en ensidig fejl i antallet af forespørgsler polynomium i fejlparameteren) hvis og kun hvis, hvornår er en todelt graf [11] . $H$ $H$

I teorien om streamingalgoritmer til grafmatching (f.eks. til at matche annoncører til annoncepladser), er kvaliteten af matchende dækning (sparsomme undergrafer, der omtrent bevarer størrelsen af matchninger i alle undergrupper af toppunkter) tæt forbundet med tætheden af todelte grafer der kan dekomponeres til genererede matchninger. Denne konstruktion bruger en modificeret form af Ruzi-Semeredi-problemet, hvor antallet af genererede matchninger kan være meget mindre end antallet af toppunkter, men hver genereret matching skal dække de fleste af grafens toppunkter. I denne version af problemet er det muligt at konstruere grafer med et ikke-konstant antal genererede matchninger af lineær størrelse, og dette resultat fører til næsten nøjagtige grænser for tilnærmelseskoefficienten for streaming matching algoritmer [12] [13] [14 ] [15] .

Den subkadratiske øvre grænse for Rouzi-Szemeredi-problemet blev også brugt til at opnå en grænse for størrelsen af hættesættene [16], før stærkere grænser for formen for blev bevist for dette problem [17] . Det giver også den bedst kendte øvre grænse for pakning af stativer [18] . $o(3^{n})$ ${\displaystyle c^{n))$ $c<3$

Noter

↑ 1 2 3 Komlós J., Simonovits M. Combinatorics, Paul Erdős er firs, Vol. 2 (Keszthely, 1993). - Budapest: Janos Bolyai Math. Soc., 1996. - T. 2. - S. 295-352. - (Bolyai Soc. Math. Stud.).
↑ Clark LH, Entringer RC, McCanna JE, Székely LA Ekstreme problemer for lokale egenskaber ved grafer // The Australasian Journal of Combinatorics. - 1991. - T. 4 . — S. 25–31 .
↑ Dalibor Fronček. Lokalt lineære grafer // Mathematica Slovaca. - 1989. - T. 39 , no. 1 . — S. 3–6 .
↑ Larrión F., Pizaña MA, Villarroel-Flores R. Små lokalt nK 2 grafer // Ars Combinatoria. - 2011. - T. 102 . — S. 385–391 .
↑ 1 2 3 4 5 6 Ruzsa IZ, Szemerédi E. Tredobbelte systemer uden seks punkter, der bærer tre trekanter // Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. - Nord-Holland, 1978. - T. 18. - S. 939-945. - (Colloq. Math. Soc. Janos Bolyai).
↑ Behrend FA Om sæt af heltal, der ikke indeholder tre led i aritmetisk progression // Proceedings of the National Academy of Sciences . - T. 32 , no. 12 . — S. 331–332 . - doi : 10.1073/pnas.32.12.331 .
↑ Jacob Fox. Et nyt bevis på graffjernelseslemmaet // Annals of Mathematics . - 2011. - T. 174 , no. 1 . — S. 561–579 . - doi : 10.4007/annals.2011.174.1.17 .
↑ Sós VT , Erdős P. , Brown WG Om eksistensen af triangulerede kugler i 3-grafer og relaterede problemer // Periodica Mathematica Hungarica. - 1973. - T. 3 , no. 3-4 . — S. 221–228 . - doi : 10.1007/BF02018585 .
↑ Brown WG, Erdős P. , Sós VT Nogle ekstreme problemer på r- grafer // Nye retninger i teorien om grafer (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971). - Academic Press, 1973. - S. 53-63 .
↑ Johan Håstad, Avi Wigderson. Enkel analyse af graftests for linearitet og PCP // Random Structures & Algoritms. - 2003. - T. 22 , no. 2 . — S. 139–160 . - doi : 10.1002/rsa.10068 .
↑ Noga Alon . Test af undergrafer i store grafer // Random Structures & Algoritms. - 2002. - T. 21 , no. 3-4 . — S. 359–370 . - doi : 10.1002/rsa.10056 .
↑ Ashish Goel, Michael Kapralov, Sanjeev Khanna. Proceedings af det 23. årlige ACM-SIAM-symposium om diskrete algoritmer. - ACM, 2012. - S. 468-485.
↑ Michael Kapralov. Proceedings af det 24. årlige ACM-SIAM-symposium om diskrete algoritmer. - SIAM, 2013. - S. 1679-1697. - doi : 10.1137/1.9781611973105.121 .
↑ Christian Konrad. Maksimal matchning i drejekorsstrømme // Algoritmer - ESA 2015. - Heidelberg: Springer, 2015. - T. 9294. - S. 840–852. - (Lecture Notes in Comput. Sci.). - doi : 10.1007/978-3-662-48350-3_70 .
↑ Jacob Fox, Hao Huang, Benny Sudakov. På grafer, der kan nedbrydes til inducerede matchninger af lineære størrelser // Bulletin of the London Mathematical Society . - 2017. - T. 49 , no. 1 . — s. 45–57 . - doi : 10.1112/blms.12005 . - arXiv : 1512.07852 .
↑ Frankl P., Graham RL, Rödl V. Om undergrupper af abelske grupper uden 3-term aritmetisk progression // Journal of Combinatorial Theory . - 1987. - T. 45 , no. 1 . — S. 157–161 . - doi : 10.1016/0097-3165(87)90053-7 .
↑ Jordan Ellenberg, Dion Gijswijt. På store delmængder af uden tre-term aritmetisk progression // Annals of Mathematics . - 2017. - T. 185 , no. 1 . — S. 339–343 . doi : 10.4007 / annals.2017.185.1.8 . - arXiv : 1605.09223 . ${\displaystyle \mathbb {F} _{q}^{n))$
↑ Gowers WT, Long J. Længden af en -tiltagende sekvens af -tupler. - 2016. - arXiv : 1609.08688 . $s$ $r$