Problém Ruja - Semeredi

Problém Rouge–Szemeredi neboli (6,3) se ptá na maximální počet hran v grafu, ve kterém jakákoli hrana patří do jednoho trojúhelníku. Ekvivalentně se problém ptá na maximální počet hran ve vyváženém bipartitním grafu, jehož hrany lze rozložit na lineární počet generovaných shod , nebo na maximální počet trojic, které lze vybrat z bodů tak, že každých šest bodů obsahuje maximálně dvě trojky. Problém je pojmenován po Imre Z. Rougym a Endre Szemeredym , kteří jako první dokázali, že odpověď je menší než pomalu rostoucí (ale zatím neznámý) faktor [1] . $n$ $n^{2}$

Ekvivalence mezi formulacemi

Následující otázky mají odpovědi, které jsou asymptoticky ekvivalentní - neliší se od sebe více než konstantním faktorem [1] :

Jaký je maximální možný počet hran ve vrcholovém grafu, ve kterém jakákoli hrana patří do jednoho trojúhelníku? [2] Grafy s touto vlastností se nazývají lokálně lineární grafy [3] nebo lokálně odpovídající grafy [4] . $n$
Jaký je maximální možný počet hran v bipartitním grafu s vrcholy na každé straně jeho části, jehož hrany lze rozdělit na vygenerované podgrafy , z nichž každý je shodný [1] ? $n$ $n$
Jaký největší počet trojic bodů lze z daných bodů vybrat tak, aby libovolných šest bodů obsahovalo nejvýše dvě z vybraných trojic? [5] Problém Rouge-Szemeredi hledá odpověď na tyto ekvivalentní otázky. $n$

Chcete-li zredukovat vygenerovaný problém shody pro bipartitní graf na problém s jedním trojúhelníkem, přidejte sadu vrcholů grafu, jeden pro každou vygenerovanou shodu, a přidejte hrany z vrcholů a bipartitního grafu k vrcholu v této třetí sadě, když hrana bipartitní graf patří k vygenerovanému párování . Výsledkem je vyvážený tripartitní graf s vrcholy s vlastností jedinečnosti trojúhelníků. V opačném směru lze libovolný graf s vlastností trojúhelníkové jedinečnosti zredukovat na vyvážený tripartitní graf rozdělením podílů vrcholů na tři stejné množiny náhodně a zachováním trojúhelníků, které definují rozdělení podílů. Výsledkem je konstantní poměr trojúhelníků a hran. Vyvážený tripartitní graf s vlastností jedinečnosti trojúhelníku lze převést na dělený bipartitní graf odstraněním jedné z jeho tří podmnožin vrcholů, čímž se vytvoří vygenerovaná shoda na sousedech každého z odstraněných vrcholů. $n$ $u$ $proti$ $w$ $UV$ $w$ $3n$

Abychom převedli graf s jedinečným trojúhelníkem na hranu na systém trojic, vezmeme trojúhelníky grafu jako trojice. Žádných šest bodů nemůže obsahovat tři trojúhelníky, aniž by dva ze tří trojúhelníků sdílely hranu, nebo všechny tři trojúhelníky tvořily čtvrtý trojúhelník, který sdílí hrany s každým z nich. V opačném směru, chcete-li převést trojný systém na graf, nejprve odstraňte všechny sady čtyř bodů, které obsahují dvě trojice. Tyto čtyři body nemohou být přítomny v jiných trojicích, a proto nemohou přidat více než lineární počet trojic. Nyní vytvoříme graf spojující libovolnou dvojici bodů, které patří některé ze zbývajících trojic.

Dolní hranice

Téměř kvadratickou hranici pro Rouge-Szemerediho problém lze odvodit z výsledku Felixe Behrenda, podle kterého čísla modulo a liché prvočíslo mají velké Salem-Spencerovy množiny , podmnožiny velikosti bez tříčlenných aritmetických posloupností [6 ] . Behrendův výsledek lze použít ke konstrukci tripartitních grafů, ve kterých má každý segment vrchol, graf obsahuje hrany a každá hrana patří do jednoho trojúhelníku. Pak podle této konstrukce je počet hran také [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))))$

Abychom vytvořili graf tohoto typu z Berendovy podmnožiny bez aritmetických posloupností , očíslujeme vrcholy v každém podílu od do a sestavíme trojúhelníky ve tvaru modulo pro každý interval od do a každé číslo patří do . Například s a jako výsledek dostaneme vyvážený tripartitní graf s 9 vrcholy a 18 hranami, jak je znázorněno na obrázku. Graf vytvořený kombinací těchto trojúhelníků má požadovanou vlastnost, že každá hrana patří právě jednomu trojúhelníku. Pokud by tomu tak nebylo, existoval by trojúhelník , kde , a patří do , což porušuje předpoklad, že v [5] nejsou žádné aritmetické posloupnosti . $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$

Horní vazba

Szemerediho lemma pravidelnosti lze použít k prokázání, že jakékoli řešení Rouzi-Szemerediho problému má nanejvýš hran nebo trojúhelníků [5] . Silnější verze Jacob Fox Count Deletion Lemma znamená, že velikost řešení nepřesahuje . Zde a jsou zástupci zápisu "o small" a , a znamená iterovaný logaritmus . Fox dokázal, že v každém grafu s vrcholy a trojúhelníky lze pro někoho najít podgraf bez trojúhelníků odstraněním většiny hran [7] . V grafu s vlastností jedinečnosti trojúhelníku jsou (přirozeně) trojúhelníky, takže výsledek přichází s . Ale v tomto grafu každé odstranění hrany odstraní pouze jeden trojúhelník, takže počet hran, které je třeba odstranit, aby se odstranily všechny trojúhelníky, se rovná počtu trojúhelníků. $o(n^{2})$ ${\displaystyle n^{2}/e^{\Omega (\log ^{*}n)))$ $Ó$ $\Omega$ $\Omega$ $\log^*$ $n$ $O(n^{3-\delta })$ $\delta>0$ ${\displaystyle n^{2}/e^{\Omega (\log ^{*}n)))$ $O(n^{2})$ $\delta=1$

Historie

Problém je pojmenován po Imre Z. Rougym a Endre Szemeredym , kteří problém ve formulaci trojic bodů studovali v publikaci z roku 1978 [5] . Problémem se však již dříve zabývali W. J. Brown, Pal Erdős a Vera T. Szos ve dvou publikacích v roce 1973, v nichž dokázali, že maximální počet trojic může být [8] , a domnívali se, že se ve skutečnosti rovná [9 ] . Ruzsa a Szemeredy dali (nestejné) téměř kvadratické horní a dolní mez problému, čímž výrazně zlepšili spodní mez Browna, Erdőse a Sosy a důkaz jejich domněnky [5] . $\Omega (n^{3/2})$ $o(n^{2})$

Aplikace

Existence hustých grafů, které lze rozložit na velké generované shody, byla použita ke konstrukci účinných testů, zda je booleovská funkce lineární, což je klíčová součást PCP teorému v teorii výpočetní složitosti [10] . V teorii algoritmů pro kontrolu vlastností byly použity známé výsledky Rouzi-Szemerediho problému, které ukázaly, že je možné zkontrolovat, zda graf obsahuje daný podgraf (s jednostrannou chybou v počtu dotazů polynom v chybovém parametru) tehdy a jen tehdy, kdy je bipartitní graf [11] . $H$ $H$

V teorii streamovacích algoritmů pro párování grafů (např. pro párování inzerentů s reklamními bloky) kvalita pokrytí párování (řídké podgrafy, které přibližně zachovávají velikost párování ve všech podskupinách vrcholů) úzce souvisí s hustotou bipartitních grafů. které lze rozložit na generované shody. Tato konstrukce využívá upravenou formu Ruzi-Semerediho problému, ve kterém počet vygenerovaných shod může být mnohem menší než počet vrcholů, ale každá vygenerovaná shoda musí pokrýt většinu vrcholů grafu. V této verzi problému je možné konstruovat grafy s nekonstantním počtem generovaných párování lineární velikosti a tento výsledek vede k téměř přesným hranicím aproximačního koeficientu pro streamingové párovací algoritmy [12] [13] [14 ] [15] .

Subkadratická horní mez Rouziho-Szemerediho problému byla také použita k získání hranice velikosti množin čepic [16] , než byly pro tento problém prokázány silnější meze tvaru pro [17] . Poskytuje také nejznámější horní mez pro balení stativů [18] . $o(3^{n})$ ${\displaystyle c^{n))$ $c<3$

Poznámky

↑ 1 2 3 Komlós J., Simonovits M. Combinatorics, Paul Erdős je osmdesát, sv. 2 (Keszthely, 1993). - Budapešť: Janos Bolyai Math. Soc., 1996. - T. 2. - S. 295–352. - (Bolyai Soc. Math. Stud.).
↑ Clark LH, Entringer RC, McCanna JE, Székely LA Extrémní problémy pro lokální vlastnosti grafů // The Australasian Journal of Combinatorics. - 1991. - T. 4 . — S. 25–31 .
↑ Dalibor Fronček. Lokálně lineární grafy // Mathematica Slovaca. - 1989. - T. 39 , no. 1 . — S. 3–6 .
↑ Larrión F., Pizaña MA, Villarroel-Flores R. Malé lokálně nK 2 grafy // Ars Combinatoria. - 2011. - T. 102 . — S. 385–391 .
↑ 1 2 3 4 5 6 Ruzsa IZ, Szemerédi E. Trojité systémy bez šesti bodů nesoucích tři trojúhelníky // Kombinatorika (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. - North-Holland, 1978. - T. 18. - S. 939-945. - (Kol. matematika. Soc. Janos Bolyai).
↑ Behrend FA O souborech celých čísel, které neobsahují žádné tři členy v aritmetickém postupu // Sborník Národní akademie věd . - T. 32 , č.p. 12 . — S. 331–332 . - doi : 10.1073/pnas.32.12.331 .
↑ Jacob Fox. Nový důkaz lemmatu odstranění grafu // Annals of Mathematics . - 2011. - T. 174 , č.p. 1 . — S. 561–579 . - doi : 10.4007/annals.2011.174.1.17 .
↑ Sós VT , Erdős P. , Brown WG O existenci triangulovaných koulí ve 3-grafech a souvisejících problémech // Periodica Mathematica Hungarica. - 1973. - T. 3 , no. 3-4 . — S. 221–228 . - doi : 10.1007/BF02018585 .
↑ Brown WG, Erdős P. , Sós VT Některé extremální problémy na r -grafech // Nové směry v teorii grafů (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971). - Academic Press, 1973. - S. 53-63 .
↑ Johan Håstad, Avi Wigderson. Jednoduchá analýza grafových testů pro linearitu a PCP // Random Structures & Algorithms. - 2003. - T. 22 , no. 2 . — S. 139–160 . - doi : 10.1002/rsa.10068 .
↑ Noga Alon . Testování podgrafů ve velkých grafech // Náhodné struktury a algoritmy. - 2002. - T. 21 , no. 3-4 . — S. 359–370 . - doi : 10.1002/rsa.10056 .
↑ Ashish Goel, Michael Kapralov, Sanjeev Khanna. Sborník příspěvků z 23. výročního sympozia ACM-SIAM o diskrétních algoritmech. - ACM, 2012. - S. 468-485.
↑ Michael Kapralov. Sborník příspěvků z 24. výročního sympozia ACM-SIAM o diskrétních algoritmech. - SIAM, 2013. - S. 1679-1697. - doi : 10.1137/1.9781611973105.121 .
↑ Christian Konrad. Maximální párování v turniketových proudech // Algorithms - ESA 2015. - Heidelberg: Springer, 2015. - T. 9294. - S. 840–852. - (Poznámky z přednášky v počítačové vědě). - doi : 10.1007/978-3-662-48350-3_70 .
↑ Jacob Fox, Hao Huang, Benny Sudakov. Na grafech rozložitelných na indukované shody lineárních velikostí // Bulletin of the London Mathematical Society . - 2017. - T. 49 , č. 1 . — s. 45–57 . - doi : 10.1112/blms.12005 . - arXiv : 1512.07852 .
↑ Frankl P., Graham RL, Rödl V. O podmnožinách abelovských grup bez 3členné aritmetické progrese // Journal of Combinatorial Theory . - 1987. - T. 45 , no. 1 . — S. 157–161 . - doi : 10.1016/0097-3165(87)90053-7 .
↑ Jordan Ellenberg, Dion Gijswijt. Na velkých podmnožinách bez tříčlenné aritmetické progrese // Annals of Mathematics . - 2017. - T. 185 , č.p. 1 . — S. 339–343 . doi : 10.4007 / anals.2017.185.1.8 . - arXiv : 1605.09223 . ${\displaystyle \mathbb {F} _{q}^{n))$
↑ Gowers WT, Long J. Délka - rostoucí sekvence -tic. - 2016. - arXiv : 1609.08688 . $s$ $r$