Rujan ongelma - Semeredi

Rouge–Szemeredi eli (6,3)-tehtävä kysyy graafin reunojen maksimimäärää, jossa mikä tahansa reuna kuuluu yhteen kolmioon. Vastaavasti tehtävässä kysytään reunojen maksimimäärää tasapainotetussa kaksiosaisessa graafissa, jonka reunat voidaan jakaa lineaariseksi määräksi luotuja vastaavuuksia , tai maksimimäärää kolmoiskappaleita, jotka voidaan valita pisteistä siten, että joka kuudes piste sisältää korkeintaan kaksi kolminkertaista. Ongelma on nimetty Imre Z. Rougyn ja Endre Szemedyn mukaan, jotka ensimmäisinä osoittivat, että vastaus on pienempi kuin hitaasti kasvava (mutta toistaiseksi tuntematon) tekijä [1] . $n$ $n^{2}$

Formulaatioiden välinen vastaavuus

Seuraaviin kysymyksiin on asymptoottisesti vastaavia vastauksia - ne eroavat toisistaan enintään vakiokertoimella [1] :

Mikä on suurin mahdollinen reunojen lukumäärä kärkigraafissa, jossa mikä tahansa reuna kuuluu yhteen kolmioon? [2] Graafeja, joilla on tämä ominaisuus, kutsutaan paikallisesti lineaarisiksi kaavioiksi [3] tai paikallisesti täsmääviksi kaavioiksi [4] . $n$
Mikä on suurin mahdollinen reunojen lukumäärä kaksiosaisessa graafissa , jonka osan molemmilla puolilla on kärkipisteet ja jonka reunat voidaan jakaa generoituihin aligraafiin , joista jokainen on täsmäävä [1] ? $n$ $n$
Mikä on suurin määrä pisteiden kolmioita, jotka voidaan valita annetuista pisteistä siten, että missä tahansa kuudessa pisteessä on enintään kaksi valituista kolmioista? [5] Rouge-Szemeredin ongelma etsii vastausta näihin vastaaviin kysymyksiin. $n$

Muodostaaksesi kaksiosaisen graafin luodun sovitusongelman yhdeksi kolmiotehtäväksi lisäämällä joukko graafin kärkipisteitä, yksi kullekin luodulle sovitukselle, ja lisäämällä kärkien ja kaksiosaisen graafin reunat tämän kolmannen joukon kärkipisteeseen, kun kaksiosainen graafi kuuluu luotuun vastaavuuteen . Tuloksena saadaan tasapainotettu kolmiosainen graafi, jonka kärjet ovat kolmioiden ainutlaatuisuusominaisuus. Toisessa suunnassa mikä tahansa graafi, jolla on kolmion yksilöllisyysominaisuus, voidaan pelkistää tasapainotetuksi kolmiosaiseksi graafiksi jakamalla kärkiosuudet kolmelle yhtä suurelle joukolle satunnaisesti ja säilyttämällä kolmiot, jotka määrittävät osuuksien jakautumisen. Tämä johtaa kolmioiden ja reunojen vakiosuhteeseen. Tasapainotettu kolmiosainen graafi, jolla on kolmion ainutlaatuisuusominaisuus, voidaan muuntaa osioiduksi kaksiosaiseksi graafiksi poistamalla yksi sen kolmesta kärkien alajoukosta, jolloin luodaan generoitu vastaavuus kunkin poistetun kärjen naapureille. $n$ $u$ $v$ $w$ $UV$ $w$ $3n$

Muuntaaksesi graafin, jossa on ainutlaatuinen kolmio reunaa kohti, kolmoisjärjestelmäksi otamme graafin kolmiot kolmoisiksi. Yksikään kuusi pistettä ei voi sisältää kolmea kolmiota ilman, että joko kahdella kolmesta kolmiosta on yhteinen reuna tai kaikki kolme kolmiota muodostavat neljännen kolmion, jolla on yhteinen reuna kunkin kanssa. Toisessa suunnassa kolmoisjärjestelmän muuttamiseksi kaavioksi poista ensin kaikki neljän pisteen joukot, jotka sisältävät kaksi kolmoa. Nämä neljä pistettä eivät voi olla läsnä muissa kolmioissa, eivätkä ne siksi voi lisätä enempää kuin lineaarista määrää kolmoiskappaleita. Nyt muodostamme kaavion, joka yhdistää minkä tahansa pisteparin, joka kuuluu mihin tahansa jäljellä olevista kolmioista.

Alaraja

Melkein neliöllinen rajoitus Rouge-Szemeredi-ongelmalle voidaan johtaa Felix Behrendin tuloksesta, jonka mukaan parittomalla alkuluvulla moduloivilla luvuilla on suuria Salem-Spencer-joukkoja , koon alijoukkoja ilman kolmen termin aritmeettisia progressioita [6 ] . Behrendin tuloksen avulla voidaan rakentaa kolmiosaisia graafia, joissa jokaisella segmentillä on kärkipiste, graafi sisältää reunat ja jokainen reuna kuuluu yhteen kolmioon. Tällöin tämän konstruktion mukaan myös reunojen lukumäärä on [5] . $s$ $A$ ${\displaystyle |A|=p/e^{O({\sqrt {\log p))))$ $s$ $3|A|p$ $n=3p$ ${\displaystyle n^{2}/e^{O({\sqrt {\log n))))$

Luodaksemme tämän tyyppisen graafin Berendin osajoukosta, jossa ei ole aritmeettisia progressioita , numeroimme kunkin osuuden kärjet alkaen - ja rakennamme kolmiot, joiden muoto on modulo kullekin välille alkaen to ja jokaiselle numerolle kuuluu . Esimerkiksi kanssa ja tuloksena saadaan tasapainotettu kolmiosainen graafi, jossa on 9 kärkeä ja 18 reunaa, kuten kuvassa. Näitä kolmioita yhdistämällä muodostetulla graafilla on haluttu ominaisuus, että jokainen reuna kuuluu täsmälleen yhteen kolmioon. Jos näin ei olisi, olisi kolmio , jossa , ja kuuluvat , mikä rikkoo oletusta, että [5] :ssä ei ole aritmeettisia progressioita . $A$ $0$ $p-1$ ${\näyttötyyli (x,x+a,x+2a)}$ $s$ $x$ $0$ $p-1$ $a$ $A$ $p=3$ $A=\{\pm 1\}$ ${\näyttötyyli (x,x+a,x+a+b)}$ $a$ $b$ $c=(a+b)/2$ $A$ ${\näyttötyyli (a,c,b)}$ $A$

Yläraja

Szemedin säännönmukaisuuslemmaa voidaan käyttää osoittamaan, että missä tahansa Rouzi-Szemeredin ongelman ratkaisussa on korkeintaan kulmia tai kolmioita [5] . Jacob Fox Count Deletion Lemman vahvempi versio tarkoittaa, että ratkaisun koko ei ylitä . Tässä ja ovat edustajia merkinnöistä "o small" ja , ja tarkoittaa iteroitua logaritmia . Fox osoitti, että mistä tahansa graafista, jossa on pisteitä ja kolmioita, joillekin voi löytää aligraafin ilman kolmioita poistamalla suurimmat reunat [7] . Kolmion ainutlaatuisuusominaisuuden omaavassa kaaviossa on (luonnollisesti) kolmioita, joten tuloksena tulee . Mutta tässä kaaviossa jokainen reunan poisto poistaa vain yhden kolmion, joten kaikkien kolmioiden poistamiseksi poistettavien reunojen määrä on yhtä suuri kuin kolmioiden lukumäärä. $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$

Historia

Ongelma on nimetty Imre Z. Rougyn ja Endre Szemedyn mukaan, jotka tutkivat ongelmaa kolmoispisteiden muotoilussa vuoden 1978 julkaisussa [5] . Kuitenkin W. J. Brown, Pal Erdős ja Vera T. Szos tutkivat ongelmaa aiemmin kahdessa julkaisussa vuonna 1973, joissa he osoittivat, että kolmosten enimmäismäärä voi olla [8] , ja olettivat sen olevan itse asiassa [9 ] . Ruzsa ja Szemedy antoivat (epätasaiset) lähes neliömetrin ylä- ja alarajat ongelmalle parantaen merkittävästi Brownin, Erdősin ja Sosan alarajaa ja heidän olettamuksensa todisteita [5] . $\Omega (n^{3/2})$ $o(n^{2})$

Sovellukset

Tiheiden kuvaajien olemassaoloa, jotka voidaan hajottaa suuriksi generoiduiksi täsmäyksiksi, on käytetty tehokkaiden testien rakentamiseen, onko Boolen funktio lineaarinen, mikä on laskennallisen monimutkaisuusteorian PCP-lauseen avainkomponentti [10] . Ominaisuudentarkistusalgoritmien teoriassa käytettiin Rouzi-Szemeredi-ongelman hyvin tunnettuja tuloksia osoittamaan, että on mahdollista tarkistaa, sisältääkö graafi tietyn aligraafin (jossa on yksipuolinen virhe kyselyiden määrässä polynomi virheparametrissa) jos ja vain jos, milloin on kaksiosainen graafi [11] . $H$ $H$

Kaavioiden yhteensovittamista koskevien suoratoistoalgoritmien teoriassa (esim. mainostajien sovittaminen mainospaikkoihin) vastaavuuden kattavuuden laatu (harvat osakaaviot, jotka säilyttävät likimäärin vastaavuuksien koon kaikissa kärkien alajoukoissa) liittyy läheisesti kaksiosaisten kaavioiden tiheyteen. jotka voidaan hajottaa luoduiksi vastaavuuksiksi. Tässä konstruktiossa käytetään muunneltua muotoa Ruzi-Semeredi-ongelmasta, jossa generoitujen täsmäysten määrä voi olla paljon pienempi kuin pisteiden lukumäärä, mutta jokaisen generoidun sovituksen tulee kattaa suurin osa graafin pisteistä. Tässä ongelman versiossa on mahdollista rakentaa kaavioita, joissa on epävakio määrä lineaarisen kokoisia luotuja vastaavuuksia, ja tämä tulos johtaa lähes täsmällisiin rajoihin striimaussovitusalgoritmien approksimaatiokertoimelle [12] [13] [14 ] [15] .

Rouzi-Szemeredi-ongelman subkadraattista ylärajaa käytettiin myös rajoituksen saamiseksi cap -joukkojen koosta [16] ennen kuin tälle ongelmalle osoitettiin vahvemmat muodon rajat [ 17] . Se tarjoaa myös tunnetuimman ylärajan jalustan pakkausta varten [18] . $o(3^{n})$ ${\displaystyle c^{n))$ $c<3$

Muistiinpanot

↑ 1 2 3 Komlós J., Simonovits M. Combinatorics, Paul Erdős on kahdeksankymmentä, voi. 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 Äärimmäiset ongelmat graafien paikallisille ominaisuuksille // The Australasian Journal of Combinatorics. - 1991. - T. 4 . — S. 25–31 .
↑ Dalibor Fronček. Paikallisesti lineaariset graafit // Mathematica Slovaca. - 1989. - T. 39 , no. 1 . - s. 3-6 .
↑ Larrión F., Pizaña MA, Villarroel-Flores R. Pienet paikalliset nK 2 -kaaviot // Ars Combinatoria. - 2011. - T. 102 . — S. 385–391 .
↑ 1 2 3 4 5 6 Ruzsa IZ, Szemerédi E. Kolmoisjärjestelmät , joissa ei ole kuutta pistettä, joissa on kolme kolmiota // Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Voi. II. - Pohjois-Hollanti, 1978. - T. 18. - S. 939-945. - (Keskustelu. Math. Soc. Janos Bolyai).
↑ Behrend FA Kokonaislukujoukoista, joissa ei ole kolmea termiä aritmeettisessa progressiossa // Proceedings of the National Academy of Sciences . - T. 32 , no. 12 . — S. 331–332 . - doi : 10.1073/pnas.32.12.331 .
↑ Jacob Fox. Uusi todiste kuvaajan poistolemasta // Matematiikan Annals . - 2011. - T. 174 , no. 1 . - S. 561-579 . - doi : 10.4007/annals.2011.174.1.17 .
↑ Sós VT , Erdős P. , Brown WG Kolmiomittaisten pallojen olemassaolosta 3-kaavioissa ja niihin liittyvistä ongelmista // Periodica Mathematica Hungarica. - 1973. - T. 3 , no. 3-4 . — S. 221–228 . - doi : 10.1007/BF02018585 .
↑ Brown WG, Erdős P. , Sós VT Jotkut äärimmäiset ongelmat r -graafissa // Uusia suuntauksia graafiteoriassa (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971). - Academic Press, 1973. - S. 53-63 .
↑ Johan Håstad, Avi Wigderson. Lineaarisuuden ja PCP:n graafitestien yksinkertainen analyysi // Random Structures & Algorithms. - 2003. - T. 22 , no. 2 . — S. 139–160 . - doi : 10.1002/rsa.10068 .
↑ Noga Alon . Aligraafien testaus suurissa kaavioissa // Random Structures & Algorithms. - 2002. - T. 21 , no. 3-4 . — S. 359–370 . - doi : 10.1002/rsa.10056 .
↑ Ashish Goel, Michael Kapralov, Sanjeev Khanna. Diskreettejä algoritmeja käsittelevän 23. vuotuisen ACM-SIAM-symposiumin julkaisut. - ACM, 2012. - S. 468-485.
↑ Michael Kapralov. Proceedings of Twenty4th Annual ACM-SIAM Symposium on Discrete Algorithms. - SIAM, 2013. - S. 1679-1697. - doi : 10.1137/1.9781611973105.121 .
↑ Christian Konrad. Suurin yhteensopivuus kääntöporttivirroissa // Algoritmit - ESA 2015. - Heidelberg: Springer, 2015. - T. 9294. - P. 840–852. - (Luentomuistiinpanot in Comput. Sci.). - doi : 10.1007/978-3-662-48350-3_70 .
↑ Jacob Fox, Hao Huang, Benny Sudakov. Graafeista, jotka voidaan hajottaa lineaaristen kokojen indusoituihin vastaavuuksiin // Bulletin of the London Mathematical Society . - 2017. - T. 49 , nro 1 . — s. 45–57 . - doi : 10.1112/blms.12005 . - arXiv : 1512.07852 .
↑ Frankl P., Graham RL, Rödl V. Abelin ryhmien osajoukoista, joissa ei ole 3-termiistä aritmeettista progressiota // Journal of Combinatorial Theory . - 1987. - T. 45 , no. 1 . — S. 157–161 . - doi : 10.1016/0097-3165(87)90053-7 .
↑ Jordan Ellenberg, Dion Gijswijt. Suurista osajoukoista ilman kolmen termin aritmeettista progressiota // 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. -kasvavan sekvenssin pituus . - 2016. - arXiv : 1609.08688 . $s$ $r$