Problema lui Ruja - Semeredi

Problema Rouge–Szemeredi sau (6,3) întreabă despre numărul maxim de muchii dintr-un grafic în care orice muchie aparține unui singur triunghi. În mod echivalent, problema se întreabă despre numărul maxim de muchii dintr-un graf bipartit echilibrat ale cărui muchii pot fi descompuse într-un număr liniar de potriviri generate , sau numărul maxim de triple care pot fi selectate din puncte astfel încât fiecare șase puncte să conțină cel mult două triple. Problema poartă numele lui Imre Z. Rougy și Endre Szemeredy , care au fost primii care au demonstrat că răspunsul este mai puțin decât un factor care crește încet (dar încă necunoscut) [1] . $n$ $n^{2}$

Echivalența dintre formulări

Următoarele întrebări au răspunsuri care sunt echivalente asimptotic - ele diferă cu cel mult un factor constant între ele [1] :

Care este numărul maxim posibil de muchii într-un grafic de vârfuri în care orice muchie aparține unui singur triunghi? [2] Graficele cu această proprietate sunt numite grafice liniare local [3] sau grafice care se potrivesc local [4] . $n$
Care este numărul maxim posibil de muchii într-un graf bipartit cu vârfuri pe fiecare parte a părții sale, ale căror muchii pot fi împărțite în subgrafe generate , fiecare dintre acestea fiind o potrivire [1] ? $n$ $n$
Care este cel mai mare număr de triple de puncte care pot fi alese dintre punctele date astfel încât orice șase puncte să conțină cel mult două dintre triplele selectate? [5] Problema Rouge-Szemeredi caută un răspuns la aceste întrebări echivalente. $n$

Pentru a reduce problema de potrivire generată pentru un graf bipartit la o problemă cu un singur triunghi, adăugați un set de vârfuri de grafic, câte unul pentru fiecare potrivire generată și adăugați muchii de la vârfuri și din graficul bipartit la un vârf din acest al treilea set atunci când o muchie de graficul bipartit aparține potrivirii generate . Ca rezultat, obținem un graf tripartit echilibrat cu vârfuri cu proprietatea unicității triunghiurilor. În cealaltă direcție, orice grafic cu proprietatea de unicitate a triunghiului poate fi redus la un grafic tripartit echilibrat prin distribuirea aleatorie a cotelor de vârf pe trei seturi egale și păstrând triunghiurile care definesc distribuția cotei. Acest lucru are ca rezultat un raport constant de triunghiuri și muchii. Un graf tripartit echilibrat cu proprietatea de unicitate a triunghiului poate fi transformat într-un graf bipartit partiționat prin eliminarea unuia dintre cele trei subseturi ale sale de vârfuri, creând o potrivire generată pe vecinii fiecăruia dintre vârfurile eliminate. $n$ $u$ $v$ $w$ $UV$ $w$ $3n$

Pentru a transforma un grafic cu un triunghi unic pe muchie într-un sistem de triple, luăm triunghiurile graficului drept triple. Niciun șase puncte nu pot include trei triunghiuri fără ca niciunul dintre cele trei triunghiuri să împartă o margine sau toate cele trei triunghiuri să formeze un al patrulea triunghi care să împartă muchii cu fiecare dintre ele. În cealaltă direcție, pentru a converti un sistem triplu într-un grafic, eliminați mai întâi orice seturi de patru puncte care conțin două triple. Aceste patru puncte nu pot fi prezente în alte triple și, prin urmare, nu pot adăuga mai mult de un număr liniar de triple. Acum formăm un grafic care conectează orice pereche de puncte care aparțin oricăruia dintre tripletele rămase.

Limită inferioară

O limită aproape pătratică pentru problema Rouge-Szemeredi poate fi derivată din rezultatul lui Felix Behrend, conform căruia numerele modulo un număr prim impar au mulțimi Salem-Spencer mari , submulțimi de dimensiune fără progresii aritmetice de trei termeni [6] ] . Rezultatul lui Behrend poate fi folosit pentru a construi grafice tripartite în care fiecare segment are un vârf, graficul conține muchii și fiecare muchie aparține unui singur triunghi. Apoi, conform acestei construcții, numărul muchiilor este și [5] . $p$ $A$ $|A|=p/e^{O({\sqrt {\log p))}$ $p$ $3|A|p$ $n=3p$ $n^{2}/e^{O({\sqrt {\log n)}}$

Pentru a construi un grafic de acest tip din submulțimea lui Berend fără progresii aritmetice , numerotăm vârfurile din fiecare parte de la până și construim triunghiuri de forma modulo pentru fiecare dintre intervalul de la până și fiecărui număr îi aparține . De exemplu, cu și ca rezultat obținem un grafic tripartit echilibrat cu 9 vârfuri și 18 muchii, prezentat în figură. Graficul format prin combinarea acestor triunghiuri are proprietatea dorită că fiecare muchie aparține exact unui triunghi. Dacă nu ar fi așa, ar exista un triunghi unde , și aparțin lui , care încalcă ipoteza că nu există progresii aritmetice în [5] . $A$ $0$ $p-1$ $(x,x+a,x+2a)$ $p$ $X$ $0$ $p-1$ $A$ $A$ $p=3$ $A=\{\pm 1\)$ $(x,x+a,x+a+b)$ $A$ $b$ $c=(a+b)/2$ $A$ $(a,c,b)$ $A$

Limită superioară

Lema de regularitate a lui Szemeredi poate fi folosită pentru a demonstra că orice soluție la problema Rouzi-Szemeredi are cel mult muchii sau triunghiuri [5] . O versiune mai puternică a Lemei de ștergere a numărului Jacob Fox implică faptul că dimensiunea soluției nu depășește . Aici și sunt reprezentanți ai notației „o mic” și , și înseamnă logaritm iterat . Fox a demonstrat că în orice graf cu vârfuri și triunghiuri, pentru unii se poate găsi un subgraf fără triunghiuri eliminând cel mult muchii [7] . Într-un grafic cu proprietatea de unicitate a triunghiului, există (în mod natural) triunghiuri, deci rezultatul vine cu . Dar în acest grafic, fiecare îndepărtare a muchiei elimină doar un triunghi, astfel încât numărul de muchii care trebuie eliminate pentru a elimina toate triunghiurile este egal cu numărul de triunghiuri. $o(n^{2})$ $n^{2}/e^{\Omega (\log ^{*}n))$ $o$ $\Omega$ $\Omega$ $\log^*$ $n$ $O(n^{3-\delta })$ $\delta>0$ $n^{2}/e^{\Omega (\log ^{*}n))$ $O(n^{2})$ $\delta=1$

Istorie

Problema este numită după Imre Z. Rougy și Endre Szemeredy , care au studiat problema în formularea triplelor de puncte într-o publicație din 1978 [5] . Cu toate acestea, problema a fost studiată anterior de W. J. Brown, Pal Erdős și Vera T. Szos în două publicații din 1973, în care au demonstrat că numărul maxim de triple poate fi [8] , și au presupus că este de fapt egal cu [9 ] . Ruzsa și Szemeredy au dat (inegale) limite superioare și inferioare aproape pătratice pentru problemă, îmbunătățind semnificativ limita inferioară a lui Brown, Erdős și Sosa și demonstrarea conjecturii lor [5] . $\Omega (n^{3/2})$ $o(n^{2})$

Aplicații

Existența graficelor dense care pot fi descompuse în potriviri mari generate a fost folosită pentru a construi teste eficiente pentru a stabili dacă o funcție booleană este liniară, o componentă cheie a teoremei PCP în teoria complexității computaționale [10] . În teoria algoritmilor de verificare a proprietăților , s-au folosit rezultate binecunoscute privind problema Rouzi-Szemeredi pentru a arăta că este posibil să se verifice dacă un grafic conține un subgraf dat (cu o eroare unilaterală în numărul de interogări polinom în parametrul de eroare) dacă și numai dacă, când este un graf bipartit [11] . $H$ $H$

În teoria algoritmilor de streaming pentru potrivirile graficelor (de exemplu, pentru potrivirea agenților de publicitate cu spațiile publicitare), calitatea acoperirii potrivirii (subgrafe rare care păstrează aproximativ dimensiunea potrivirilor în toate subseturile de vârfuri) este strâns legată de densitatea graficelor bipartite. care pot fi descompuse în potriviri generate. Această construcție folosește o formă modificată a problemei Ruzi-Semeredi, în care numărul de potriviri generate poate fi mult mai mic decât numărul de vârfuri, dar fiecare potrivire generată trebuie să acopere majoritatea nodurilor graficului. În această versiune a problemei, este posibil să se construiască grafice cu un număr non-constant de potriviri generate de dimensiune liniară, iar acest rezultat conduce la limite aproape exacte ale coeficientului de aproximare pentru algoritmii de potrivire în flux [12] [13] [14 ]. ] [15] .

Limita superioară subcadratică a problemei Rouzi-Szemeredi a fost, de asemenea, utilizată pentru a obține o limită a mărimii setului de cap [16] înainte ca limite mai puternice ale formei for să fie dovedite pentru această problemă [17] . De asemenea, oferă cea mai cunoscută limită superioară pentru ambalarea trepiedelor [18] . $o(3^{n})$ $c^{n)$ $c<3$

Note

↑ 1 2 3 Komlós J., Simonovits M. Combinatorics, Paul Erdős are optzeci de ani, Vol. 2 (Keszthely, 1993). - Budapesta: Janos Bolyai Math. Soc., 1996. - T. 2. - S. 295-352. - (Bolyai Soc. Math. Stud.).
↑ Clark LH, Entringer RC, McCanna JE, Székely LA Probleme extreme pentru proprietățile locale ale graficelor // The Australasian Journal of Combinatorics. - 1991. - T. 4 . — S. 25–31 .
↑ Dalibor Fronček. Grafice liniare local // Mathematica Slovaca. - 1989. - T. 39 , nr. 1 . — P. 3–6 .
↑ Larrión F., Pizaña MA, Villarroel-Flores R. Small locally nK 2 graphs // Ars Combinatoria. - 2011. - T. 102 . — S. 385–391 .
↑ 1 2 3 4 5 6 Ruzsa IZ, Szemerédi E. Sisteme triple fără șase puncte purtând trei triunghiuri // Combinatorică (Proc. Fifth Hungarian Coloq., Keszthely, 1976), voi. II. - Olanda de Nord, 1978. - T. 18. - S. 939-945. - (Coloc. Matematică. Soc. Janos Bolyai).
↑ Behrend FA Despre seturi de numere întregi care nu conțin trei termeni în progresie aritmetică // Proceedings of the National Academy of Sciences . - T. 32 , nr. 12 . — S. 331–332 . - doi : 10.1073/pnas.32.12.331 .
↑ Jacob Fox. O nouă dovadă a lemei de eliminare a graficelor // Analele matematicii . - 2011. - T. 174 , nr. 1 . — S. 561–579 . - doi : 10.4007/annals.2011.174.1.17 .
↑ Sós VT , Erdős P. , Brown WG Despre existența sferelor triangulate în 3-grafe și probleme aferente // Periodica Mathematica Hungarica. - 1973. - T. 3 , nr. 3-4 . — S. 221–228 . - doi : 10.1007/BF02018585 .
↑ Brown WG, Erdős P. , Sós VT Some extremal problems on r -graphs // New directions in theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971). - Presa Academică, 1973. - S. 53-63 .
↑ Johan Håstad, Avi Wigderson. Analiză simplă a testelor grafice pentru liniaritate și PCP // Structuri aleatoare și algoritmi. - 2003. - T. 22 , nr. 2 . — S. 139–160 . - doi : 10.1002/rsa.10068 .
↑ Noga Alon . Testarea subgrafelor în grafice mari // Structuri aleatorii și algoritmi. - 2002. - T. 21 , nr. 3-4 . — S. 359–370 . - doi : 10.1002/rsa.10056 .
↑ Ashish Goel, Michael Kapralov, Sanjeev Khanna. Actele celui de-al douăzeci și treilea simpozion anual ACM-SIAM despre algoritmi discreti. - ACM, 2012. - S. 468-485.
↑ Michael Kapralov. Actele celui de-al douăzeci și patrulea simpozion anual ACM-SIAM despre algoritmi discreti. - SIAM, 2013. - S. 1679-1697. - doi : 10.1137/1.9781611973105.121 .
↑ Christian Konrad. Potrivire maximă în fluxuri turnichet // Algoritmi - ESA 2015. - Heidelberg: Springer, 2015. - T. 9294. - P. 840–852. - (Lecture Notes in Comput. Sci.). - doi : 10.1007/978-3-662-48350-3_70 .
↑ Jacob Fox, Hao Huang, Benny Sudakov. Pe grafice descompuse în potriviri induse de dimensiuni liniare // Buletinul Societății de Matematică din Londra . - 2017. - T. 49 , nr. 1 . — p. 45–57 . - doi : 10.1112/blms.12005 . - arXiv : 1512.07852 .
↑ Frankl P., Graham RL, Rödl V. On subsets of abelian groups with no 3-term aritmetic progression // Journal of Combinatorial Theory . - 1987. - T. 45 , nr. 1 . — S. 157–161 . - doi : 10.1016/0097-3165(87)90053-7 .
↑ Jordan Ellenberg, Dion Gijswijt. Pe subseturi mari de fără progresie aritmetică pe trei termeni // Analele matematicii . - 2017. - T. 185 , nr. 1 . — S. 339–343 . doi : 10.4007 / anals.2017.185.1.8 . - arXiv : 1605.09223 . $\mathbb {F} _{q}^{n)$
↑ Gowers WT, Long J. Lungimea unei secvențe în creștere de -tupluri. - 2016. - arXiv : 1609.08688 . $s$ $r$