Ruja problémája - Semeredi

A Rouge–Szemeredi vagy (6,3)-probléma egy olyan gráf éleinek maximális számát kérdezi, amelyekben bármely él egyetlen háromszöghez tartozik. Ezzel egyenértékűen a probléma azt kérdezi, hogy egy kiegyensúlyozott kétrészes gráfban hány élek maximális száma bontható fel egy lineáris számú generált egyezésre , vagy hogy hány hármas lehet a pontokból úgy kiválasztani, hogy minden hat pont tartalmazzon legfeljebb két hármas. A probléma Z. Rougy Imréről és Szemeredy Endréről kapta a nevét , akik elsőként bizonyították be, hogy a válasz kevesebb, mint egy lassan növekvő (de még ismeretlen) tényező [1] . $n$ $n^{2}$

A megfogalmazások közötti egyenértékűség

A következő kérdésekre aszimptotikusan ekvivalens válaszok vannak – legfeljebb egy állandó tényezővel különböznek egymástól [1] :

Hány élek maximális száma lehetséges egy csúcsgráfban, amelyben bármely él egyetlen háromszöghez tartozik? [2] Az ezzel a tulajdonsággal rendelkező grafikonokat lokálisan lineáris gráfoknak [3] vagy lokálisan illeszkedő gráfoknak [4] nevezzük . $n$
Hány élek maximálisan lehetségesek egy olyan kétrészes gráfban , amelynek részei mindkét oldalán csúcsok vannak, és amelyek élei generált részgráfokra oszthatók, amelyek mindegyike egy illeszkedő [1] ? $n$ $n$
Hány ponthármas közül lehet a legtöbbet kiválasztani úgy, hogy bármely hat pontban legfeljebb kettő legyen a kiválasztott hármasokból? [5] A Rouge-Szemeredi probléma ezekre az egyenértékű kérdésekre keresi a választ. $n$

Ha egy kétrészes gráf generált illesztési problémáját egyetlen háromszög feladatra szeretné redukálni, adjon hozzá gráfcsúcsokat, egyet minden generált illesztéshez, és adjon hozzá éleket a csúcsokból és a kétrészes gráfból egy csúcshoz ebben a harmadik halmazban, amikor egy a kétrészes gráf a generált illesztéshez tartozik . Ennek eredményeként egy kiegyensúlyozott háromrészes gráfot kapunk, amelynek csúcsai a háromszögek egyediségi tulajdonságával rendelkeznek. A másik irányban bármely háromszög egyediségi tulajdonságú gráf lecsökkenthető kiegyensúlyozott háromoldalú gráfra, ha a csúcsrészeket véletlenszerűen osztja el három egyenlő halmaz között, és megőrzi a megosztási eloszlást meghatározó háromszögeket. Ez a háromszögek és az élek állandó arányát eredményezi. A háromszög egyediség tulajdonságú kiegyensúlyozott háromrészes gráfot particionált kétrészes gráfrá alakíthatjuk úgy, hogy eltávolítjuk annak három részhalmazának egyikét, így generált egyezést hozunk létre az egyes eltávolított csúcsok szomszédjain. $n$ $u$ $v$ $w$ $UV$ $w$ $3n$

Ahhoz, hogy egy élenként egyedi háromszögű gráfot hármasok rendszerévé alakítsunk, a gráf háromszögeit hármasnak vesszük. Hat pont nem tartalmazhat három háromszöget anélkül, hogy a három háromszög közül kettő ne osztozna egy élen, vagy hogy mindhárom háromszög ne alkotna egy negyedik háromszöget, amelynek mindegyikével közös élek. A másik irányba, ha egy hármas rendszert gráfmá szeretne konvertálni, először szüntesse meg azokat a négypontos halmazokat, amelyek két hármast tartalmaznak. Ez a négy pont nem lehet jelen más hármasokban, és ezért nem adhat hozzá lineáris számú hármasnál többet. Most létrehozunk egy gráfot, amely összeköti a többi hármashoz tartozó bármely pontpárt.

Alsó korlát

A Rouge-Szemeredi-probléma majdnem másodfokú korlátja származtatható Felix Behrend eredményéből, amely szerint a páratlan prímszám modulo formájú számoknak nagy Salem-Spencer halmazai vannak, háromtagú aritmetikai progresszió nélküli méretű részhalmazok [6] ] . A Behrend-féle eredmény felhasználható olyan háromrészes gráfok készítésére, amelyekben minden szakasznak van egy csúcsa, a gráf éleket tartalmaz, és minden él egyetlen háromszöghöz tartozik. Ekkor e konstrukció szerint az élek száma is [5] . $p$ $A$ ${\displaystyle |A|=p/e^{O({\sqrt {\log p))))$ $p$ $3|A|p$ $n=3p$ ${\displaystyle n^{2}/e^{O({\sqrt {\log n))))$

Ahhoz, hogy egy ilyen típusú gráfot készítsünk Berend aritmetikai progresszióktól mentes részhalmazából , megszámozzuk az egyes megosztások csúcsait -tól -ig, és modulo alakú háromszögeket építünk a -tól -ig terjedő intervallumokhoz és minden számhoz , amelyhez tartozik . Például a és -val egy kiegyensúlyozott háromrészes gráfot kapunk 9 csúcsgal és 18 éllel, az ábrán látható módon. A háromszögek összevonásával kialakított gráfnak megvan az a kívánt tulajdonsága, hogy minden él pontosan egy háromszöghez tartozik. Ha ez nem így lenne, akkor lenne egy háromszög , ahol , és tartozik hozzá , ami megsérti azt a feltételezést, hogy a [5] -ben nincs számtani progresszió . $A$ $0$ $p-1$ ${\megjelenítési stílus (x,x+a,x+2a)}$ $p$ $x$ $0$ $p-1$ $a$ $A$ $p=3$ $A=\{\pm 1\}$ ${\megjelenítési stílus (x,x+a,x+a+b)}$ $a$ $b$ $c=(a+b)/2$ $A$ ${\megjelenítési stílus (a,c,b)}$ $A$

Felső korlát

A Szemedi-féle szabályossági lemmával igazolható, hogy a Rouzi-Szemeredi probléma bármely megoldásának legfeljebb élei vagy háromszögei vannak [5] . A Jacob Fox Count Deletion Lemma erősebb változata azt jelenti, hogy a megoldás mérete nem haladja meg a . Itt és az "o kicsi" jelölés képviselői és a , és jelentése iterált logaritmus . Fox bebizonyította, hogy bármely csúcsokkal és háromszögekkel rendelkező gráfban találhat háromszög nélküli részgráfot, ha a legtöbb élt eltávolítja [7] . A háromszög egyediség tulajdonságú gráfban (természetesen) vannak háromszögek, így az eredmény -val érkezik . De ezen a grafikonon minden éleltávolítás csak egy háromszöget távolít el, így az összes háromszög eltávolításához el kell távolítani a háromszögek számával egyenlő éleket. $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$

Történelem

A probléma Z. Rougy Imréről és Szemeredy Endréről kapta a nevét, akik egy 1978-as publikációban [5] a ponthármasok megfogalmazásában vizsgálták a problémát . A problémát azonban korábban W. J. Brown, Erdős Pal és Szos T. Vera tanulmányozta két publikációban 1973-ban, amelyekben bebizonyították, hogy a triplák maximális száma [8] lehet , és azt sejtették, hogy ez valójában egyenlő [9 ] . Ruzsa és Szemedy (egyenlőtlen) szinte másodfokú felső és alsó korlátot adott a problémára, jelentősen javítva Brown, Erdős és Sosa alsó korlátját és sejtésük bizonyítását [5] . $\Omega (n^{3/2})$ $o(n^{2})$

Alkalmazások

A nagy generált illesztésekre bontható sűrű gráfok létezését arra használták, hogy hatékony teszteket készítsenek egy Boole-függvény lineáris-e, ami a PCP-tétel kulcsfontosságú összetevője a számítási komplexitáselméletben [10] . A tulajdonság-ellenőrző algoritmusok elméletében a Rouzi-Szemeredi probléma jól ismert eredményeivel mutatták be, hogy lehetséges-e ellenőrizni, hogy egy gráf tartalmaz-e adott részgráfot (egyoldalú hibával a lekérdezések számában polinom a hibaparaméterben) akkor és csak akkor, mikor van egy bipartit gráf [11] . $H$ $H$

A gráfillesztések streaming algoritmusainak elméletében (például a hirdetők és a hirdetési helyek párosítása esetén) az egyeztetési lefedettség minősége (ritka részgráfok, amelyek megközelítőleg megőrzik az egyezések méretét a csúcsok összes részhalmazában) szorosan összefügg a kétrészes gráfok sűrűségével. amelyek generált egyezésekre bonthatók. Ez a konstrukció a Ruzi-Semeredi probléma egy módosított formáját használja, amelyben a generált illesztések száma sokkal kevesebb lehet, mint a csúcsok száma, de minden generált illesztésnek le kell fednie a gráf csúcsainak nagy részét. A feladatnak ebben a verziójában lehetőség van nem állandó számú, lineáris méretű, generált illesztéssel rendelkező gráfok létrehozására, és ez az eredmény majdnem pontos korlátokhoz vezet a streaming illesztési algoritmusok közelítési együtthatójára [12] [13] [14 ] [15] .

A Rouzi-Szemeredi-probléma szubkadratikus felső korlátját is felhasználtuk a kupakhalmazok méretére vonatkozó korlát meghatározására [16] , mielőtt a for forma erősebb korlátait bizonyították volna erre a problémára [17] . Ezenkívül ez biztosítja a legismertebb felső határt az állványok csomagolásához [18] . $o(3^{n})$ ${\displaystyle c^{n))$ $c<3$

Jegyzetek

↑ 1 2 3 Komlós J., Simonovits M. Kombinatorika, Erdős Pál nyolcvan éves, 2. évf. 2 (Keszthely, 1993). - Budapest: Bolyai János math. Soc., 1996. - T. 2. - S. 295-352. - (Bolyai Szoc. Math. Stud.).
↑ Clark LH, Entringer RC, McCanna JE, Székely LA Extreme problems for local properties of graphs // The Australasian Journal of Combinatorics. - 1991. - T. 4 . – S. 25–31 .
↑ Dalibor Fronček. Lokálisan lineáris gráfok // Mathematica Slovaca. - 1989. - T. 39 , sz. 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. Három háromszöget hordozó hatpontos hármas rendszerek // Kombinatorika (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. - Észak-Holland, 1978. - T. 18. - S. 939-945. - (Colloq. Math. Soc. Bolyai János).
↑ Behrend FA Olyan egész számok halmazairól, amelyek nem tartalmaznak három tagot az aritmetikai progresszióban // Proceedings of the National Academy of Sciences . - T. 32 , sz. 12 . – S. 331–332 . - doi : 10.1073/pnas.32.12.331 .
↑ Jacob Fox. A gráfeltávolítási lemma új bizonyítéka // Annals of Mathematics . - 2011. - T. 174 , sz. 1 . – S. 561–579 . - doi : 10.4007/annals.2011.174.1.17 .
↑ Sós VT , Erdős P. , Brown WG A háromszögletes gömbök létezéséről 3-gráfokban, és a kapcsolódó problémákról // Periodica Mathematica Hungarica. - 1973. - T. 3 , sz. 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 the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971). - Akadémiai Kiadó, 1973. - S. 53-63 .
↑ Johan Håstad, Avi Wigderson. Linearitás és PCP gráftesztek egyszerű elemzése // Random Structures & Algorithms. - 2003. - T. 22 , sz. 2 . – S. 139–160 . - doi : 10.1002/rsa.10068 .
↑ Noga Alon . Részgráfok tesztelése nagy grafikonokon // Random Structures & Algorithms. - 2002. - T. 21 , sz. 3-4 . – S. 359–370 . - doi : 10.1002/rsa.10056 .
↑ Ashish Goel, Michael Kapralov, Sanjeev Khanna. A diszkrét algoritmusokról szóló huszadik éves ACM-SIAM szimpózium anyaga. - ACM, 2012. - S. 468-485.
↑ Michael Kapralov. Proceedings of the Twenty-4th Annual ACM-SIAM Symposium on Discrete Algorithms. - SIAM, 2013. - S. 1679-1697. - doi : 10.1137/1.9781611973105.121 .
↑ Christian Konrad. Maximum matching in turnstile streams // Algorithms - ESA 2015. - Heidelberg: Springer, 2015. - T. 9294. - P. 840–852. - (Előadási jegyzetek a Comput. Sci.-ben). - doi : 10.1007/978-3-662-48350-3_70 .
↑ Jacob Fox, Hao Huang, Benny Sudakov. Lineáris méretek indukált illesztéseire bontható gráfokon // Bulletin of the London Mathematical Society . - 2017. - T. 49 , sz. 1 . – 45–57 . - doi : 10.1112/blms.12005 . - arXiv : 1512.07852 .
↑ Frankl P., Graham RL, Rödl V. Az Abel-csoportok háromtagú aritmetikai progresszió nélküli részhalmazairól // Journal of Combinatorial Theory . - 1987. - T. 45 , sz. 1 . – S. 157–161 . - doi : 10.1016/0097-3165(87)90053-7 .
↑ Jordan Ellenberg, Dion Gijswijt. A háromtagú aritmetikai progresszió nélküli nagy részhalmazokon // Annals of Mathematics . - 2017. - T. 185 , sz. 1 . – S. 339–343 . doi : 10.4007 / annals.2017.185.1.8 . - arXiv : 1605.09223 . ${\displaystyle \mathbb {F} _{q}^{n))$
↑ Gowers WT, Long J. Egy -növekvő -sorok sorozatának hossza. - 2016. - arXiv : 1609.08688 . $s$ $r$