Paikallisesti viivakaavio

Paikallisesti lineaarinen graafi on suuntaamaton graafi jokaisen huippupisteen läheisyydessä , jonka on luonut täsmäävä . Toisin sanoen minkä tahansa pisteen kohdalla minkä tahansa naapuruston on oltava täsmälleen yhden muun pisteen vieressä . Vastaavasti mikä tahansa tällaisen graafin reuna kuuluu yhteen kolmioon [1] . Paikallisesti lineaarisia kuvaajia kutsutaan myös paikallisesti täsmäytyskaavioiksi [2] . $v$ $v$ $v$ $UV$ $uvw$

Esimerkkejä paikallisesti lineaarisista kaavioista ovat kolmiomaiset kaktukset , kolmiottomien 3-säännöllisten kaavioiden viivakaaviot ja pienempien paikallisesti lineaaristen kaavioiden suora tulos. Tietyt Kneser-kaaviot ja jotkut vahvasti säännölliset kaaviot ovat myös paikallisesti lineaarisia.

Joillakin paikallisesti lineaarisilla kaavioilla on melkein neliöllinen määrä reunoja. Kysymys näiden graafien tiheydestä voi olla yksi Ruza–Szemeredi-ongelman muotoiluista . Tunnetaan myös tiheimmät tasomaiset graafit , jotka voivat olla paikallisesti lineaarisia.

Rakenteet ja esimerkit

Joitakin paikallisesti lineaaristen graafien konstruktioita tunnetaan.

Liimaa ja teoksia

Ystävyyskaaviot , jotka on muodostettu liimaamalla yhteen joukko kolmioita yhteen yhteiseen kärkeen, ovat paikallisesti lineaarisia. Nämä ovat ainoat äärelliset graafit, joilla on vahvempi ominaisuus, että millä tahansa pisteparilla (vierellä tai ei) on täsmälleen yksi yhteinen naapuripiste [3] . Yleisemmin sanottuna mikä tahansa kolmikaktus , kaavio, jossa kaikki yksinkertaiset syklit ovat kolmion muotoisia ja kaikilla yksinkertaisten syklien parilla on enintään yksi yhteinen kärki, on paikallisesti lineaarinen.

Olkoon ja mitkä tahansa kaksi paikallisesti lineaarista kuvaajaa, valitse kustakin kaaviosta kolmio ja liimaa nämä kaksi kuvaajaa yhteen tunnistamalla parit näissä kolmioissa (tämä on eräänlainen summa napsautuksella -toiminto kaavioissa). Tällöin tuloksena oleva graafi pysyy paikallisesti lineaarisena [4] . $G$ $H$

Minkä tahansa kahden paikallisesti lineaarisen graafin kuvaajien suora tulo pysyy lineaarisesti paikallisena, koska tuotteen kaikki kolmiot ovat peräisin yhdestä tai toisesta tekijästä. Esimerkiksi Paley-graafi , jossa on yhdeksän kärkeä ( 3-3 duoprisman graafi ) on kahden kolmion suora tulo [1] . Hamming-graafit ovat kolmioiden tuloja ja ovat siksi taas paikallisesti lineaarisia [5] . $H(d,3)$ $d$

Jäljentäminen

Jos graafi on kolmioton 3-säännöllinen graafi , niin viivagraafi on graafi, joka muodostetaan muuntamalla graafin jokainen reuna uudeksi kärjeksi ja yhdistämällä kaksi kärkeä reunalla, jos graafin vastaavilla reunoilla on yhteinen päätepiste. Nämä kaaviot ovat 4-säännöllisiä ja paikallisesti lineaarisia. Mikä tahansa 4-säännöllinen paikallisesti lineaarinen graafi voidaan rakentaa tällä tavalla [6] . Esimerkiksi kuutiokaedrigraafi voidaan muodostaa tällä tavalla kuutioviivagraafina ja yhdeksän kärjen Paley-graafi on hyödyllisyysviivagraafi . Petersenin graafin viivagraafilla, toisella tämän tyyppisellä graafilla, on soluja muistuttava ominaisuus , että se on pienin mahdollinen graafi, jossa suurimmalla klikkilla on kolme kärkeä, kukin kärki kuuluu kahteen ei-päällekkäiseen klikkiin ja lyhyin sykli eri klikkeistä peräisin olevien reunojen pituus on viisi [7] . $G$ $L(G)$ $G$ $L(G)$ $G$ $K_{{3,3}}$

Monimutkaisempi kertolaskuprosessi koskee tasokaavioita . Antaa olla tasokuvaaja, joka on upotettu tasoon siten, että jokainen pinta on nelikulmainen, kuten kuutiokaavio. Jos sillä on kärkipisteitä, kasvossa on oltava graafit. Jos liitetään neliön antiprisma graafin pintaan ja sitten poistetaan graafin alkuperäiset reunat , saadaan uusi paikallisesti lineaarinen tasograafi, jossa on kärkipisteet ja reunat [4] . Esimerkiksi kuutioktaedri voidaan saada tällä tavalla 4-syklin kahdelta pinnalta (sisä- ja ulkopuolelta). $G$ $G$ $n$ $n-2$ $G$ $G$ $5(n-2)+2$ $12(n-2)$

Algebrallinen rakenne

Kneser-graafissa on kärjet , jotka edustavat -elementtijoukon -elementtiosajoukkoja . Kaksi kärkeä ovat vierekkäin, jos vastaavat osajoukot eivät leikkaa. Kun , tuloksena oleva graafi on paikallisesti lineaarinen, koska jokaiselle kahdelle ei-leikkaava -alkio-osajoukolle on täsmälleen yksi -elementtiosajoukko (niiden liiton komplementti), joka ei leikkaa molempia joukkoja. Tuloksena olevalla paikallisesti viivagrafiikalla on kärkipisteet ja reunat. Esimerkiksi Kneserin graafi on paikallisesti lineaarinen ja siinä on 15 kärkeä ja 45 reunaa [2] . ${\displaystyle KG_{a,b))$ ${\tbinom {a}{b))$ $b$ $a$ $a=3b$ $b$ $b$ ${\tbinom {3b}{b))$ ${\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}$ $b = 2$ $KG_{6,2}$

Paikallisesti lineaarisia kuvaajia voidaan rakentaa myös etenemisvapaista lukujoukoista. Antaa olla alkuluku ja antaa olla lukujen osajoukko modulo siten, että mikään kolme termiä ei muodosta aritmeettista etenemistä modulo . (Toisin sanoen se on Salem-Spencer-joukko modulo .) Sitten on kolmiosainen graafi, jossa jokaisella osalla on kärjet, on reunat ja jokainen reuna kuuluu yhteen kolmioon. Sitten tämän rakenteen mukaan reunojen lukumäärä on myös yhtä suuri kuin . Rakentaaksesi tämän kaavion, numeroimme kolmiosaisen kaavion molemmilla puolilla olevat kärjet alkaen - ja rakennamme modulon kolmion kullekin aikavälille - ja kukin . Näiden kolmioiden yhdistämisellä muodostetulla graafilla on odotettu ominaisuus, että mikä tahansa reuna kuuluu yhteen kolmioon. Jos näin ei olisi, olisi kolmio , jossa , ja kuuluisi ryhmään , mikä rikkoo oletusta, että : ssä ei ole aritmeettisia progressioita . [8] Esimerkiksi ja , tuloksena on Paley-graafi, jossa on yhdeksän kärkeä. $s$ $A$ $s$ $A$ $s$ $A$ $s$ $s$ $3|A|p$ $n=3p$ ${\displaystyle n^{2}/e^{O({\sqrt {\log n))))$ $0$ $p-1$ ${\näyttötyyli (x,x+a,x+2a)}$ $s$ $x$ $0$ $p-1$ $a$ $A$ ${\näyttötyyli (x,x+a,x+a+b)}$ $a$ $b$ $c=(a+b)/2$ $A$ ${\näyttötyyli (a,c,b)}$ $A$ $p=3$ $A=\{\pm 1\}$

Säännölliset ja vahvasti säännölliset kaaviot

Jokaisella paikallisesti viivagraafilla on oltava parillinen aste jokaiselle kärkipisteelle, koska kunkin kärjen reuna voidaan yhdistää kolmioiksi. Kahden paikallisesti lineaarisen säännöllisen graafin suora tulo on taas paikallisesti lineaarinen ja säännöllinen, jonka aste on yhtä suuri kuin tekijöiden potenssien summa. Siten on olemassa säännöllisiä paikallisesti lineaarisia kuvaajia, joilla on parillinen aste [1] . -Säännöllisissä paikallisissa viivakaavioissa on oltava vähintään kärjet, koska kolmioita ja naapureita on niin paljon. (Millään kahdella kolmion kärjellä ei voi olla yhteisiä naapureita paikallista lineaarisuutta rikkomatta.) Säännölliset graafit, joissa on täsmälleen tämä määrä pisteitä, ovat mahdollisia vain, kun niitä on 1, 2, 3 tai 5, ja ne on määritelty yksilöllisesti kullekin näistä neljästä tapauksesta. Neljä säännöllistä kuvaajaa, joilla tämä raja saavutetaan pisteiden lukumäärän funktiona, ovat 2-säännöllinen kolmio (3 kärkeä), 4-säännöllinen Paley-graafi (9 pistettä), 6-säännöllinen Kneser-graafi (15 pistettä) ja 10-säännöllisen komplementin Count Schläfli (27 huippua). Listan viimeinen 27-pisteinen 10-säännöllinen graafi on myös 27-viivainen leikkausgraafi kuutiopinnalla [ 2] . $2r$ $6r-3$ $r$ $K_{3}$ $KG_{6,2}$

Voimakkaasti säännöllinen graafi voidaan kuvata parametrien nelinkertaisella , jossa on yhtä suuri kuin pisteiden lukumäärä, on yhtä suuri kuin kärkeen osuvien reunojen lukumäärä, on yhtä suuri kuin minkä tahansa vierekkäisen pisteparin yhteisten naapureiden lukumäärä, ja on yhtä suuri kuin yhteisten naapureiden lukumäärä mille tahansa ei vierekkäiselle kärkiparille. Kun , kaavio on paikallisesti lineaarinen. Paikallisesti lineaariset graafit, kuten edellä mainittiin, ovat vahvasti säännöllisiä ja niiden parametrit ovat $(n,k,\lambda ,\mu )$ $n$ $k$ $\lambda$ $\mu$ $\lambda=1$

kolmio (3,2,1,0),
Paley-graafi, jossa on yhdeksän kärkeä (9,4,1,2),
Kneser-luku (15,6,1,3), $KG_{6,2}$
Schläfli-graafin komplementti (27,10,1,5).

Muut paikallisesti lineaariset vahvasti säännölliset graafit

Brouwer-Hemersin kaavio (81,20,1,6) [9]
Berlekamp-van Lint-Seidelin määrä (243,22,1,2) [10]
Count Cossidente – Penttils (378,52,1,8), [11]
Earl of Games (729 112 1, 20). [12]

Muita mahdollisesti kelvollisia yhdistelmiä ovat (99,14,1,2) ja (115,18,1,3), mutta ei tiedetä, onko näillä parametreilla vahvasti säännöllisiä kuvaajia [13] . Kysymys vahvasti säännöllisen graafin olemassaolosta parametreillä (99,14,1,2) tunnetaan Conwayn 99-graafin ongelmana, ja John Horton Conway tarjosi 1000 dollarin palkinnon sille, joka ratkaisi sen [14] . $\lambda=1$

On äärettömän monta etäisyyssäännöllistä 4- tai 6-asteista kuvaajaa, jotka ovat paikallisesti lineaarisia. Voimakkaasti säännöllisten samanasteisten graafien lisäksi ne sisältävät Petersen-graafin viivakaavion, Hamming-graafin ja half Foster-graafin [15] . $H(3,3)$

Tiheys

Yksi Ruzi-Szemeredi-tehtävän formulaatioista kysyy reunojen maksimimäärää paikallisesti lineaarisessa graafissa, jossa on pisteet. Kuten Imre Z. Rouja ja Endre Szemedy osoittivat , tämä maksimiluku on yhtä suuri , mutta myös yhtä suuri kuin mikä tahansa . Paikallisesti lineaaristen graafien rakentaminen etenemisvapaista joukoista johtaa tiheimpiin tunnetuihin paikallisesti lineaarisiin graafisiin reunoilla [8] . $n$ $o(n^{2})$ $\Omega (n^{2-\varepsilon })$ $\varepsilon >0$ $n^{2}/\exp O({\sqrt {\log n)))$

Tasograafien joukossa reunojen maksimimäärä paikallisesti lineaarisessa huippupistegraafissa on . Kuutio - oktaedrigraafi on ensimmäinen monitahoisten graafien äärettömässä sarjassa, jonka kärjet ja reunat on muodostettu laajentamalla neliöpintoja antiprismoiksi. Nämä esimerkit osoittavat, että tämä yläraja on tarkka [4] . $n$ ${\tfrac {12}{5}}(n-2)$ $n=5k+2$ ${\tfrac {12}{5}}(n-2)=12k$ $k=2,3,\dots$ ${\näyttötyyli K_{2,k))$

Muistiinpanot

↑ 1 2 3 Dalibor Fronček. Paikallisesti lineaariset graafit // Mathematica Slovaca. - 1989. - T. 39 , no. 1 . - s. 3-6 .
↑ 1 2 3 Larrión F., Pizaña MA, Villarroel-Flores R. Pienet paikallisesti nK 2 -kaaviot // Ars Combinatoria. - 2011. - T. 102 . — S. 385–391 .
↑ Paul Erdős , Alfred Rényi , Vera T. Sós . Graafiteorian ongelmasta // Studia Sci. Matematiikka. Unkari.. - 1966. - T. 1 . — S. 215–235 .
↑ 1 2 3 Bohdan Zelinka. Polytooppiset paikallisesti lineaariset graafit // Mathematica Slovaca. - 1988. - T. 38 , no. 2 . — S. 99–103 .
↑ Alice Devillers, Wei Jin, Cai Heng Li, Cheryl E. Praeger. Paikallinen 2-geodeettinen transitiivisuus ja klikkikaaviot // Journal of Combinatorial Theory . - 2013. - T. 120 , no. 2 . — S. 500–508 . - doi : 10.1016/j.jcta.2012.10.004 . . Tämän viitteen merkinnöissä -säännöllisten kaavioiden perhe on merkitty nimellä . $2r$ $F(r,2)$
↑ Andrea Munaro. On line graafit subcubic kolmio-free graafit // Discrete Mathematics . - 2017. - T. 340 , nro 6 . - S. 1210-1226 . - doi : 10.1016/j.disc.2017.01.006 .
↑ Kong-fani. Yleistetyistä häkeistä // Journal of Graph Theory. - 1996. - T. 23 , no. 1 . — S. 21–31 . - doi : 10.1002/(SICI)1097-0118(199609)23:1<21::AID-JGT2>3.0.CO;2-M .
↑ 1 2 Ruzsa IZ, Szemerédi E. Kolmoisjärjestelmät ilman 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).
↑ Brouwer AE, Haemers WH (81,20,1,6) vahvasti säännöllisen graafin rakenne ja ainutlaatuisuus // Discrete Mathematics . - 1992. - T. 106/107 . — s. 77–82 . - doi : 10.1016/0012-365X(92)90532-K .
↑ Berlekamp ER, van Lint JH, Seidel JJ Täydellisestä kolmiosaisesta Golay-koodista johdettu vahvasti säännöllinen graafi // Tutkimus kombinatorisesta teoriasta (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). - Pohjois-Hollanti, 1973. - S. 25-30 . - doi : 10.1016/B978-0-7204-2262-7.50008-9 .
↑ Antonio Cossidente, Tim Penttila. Hemisysteemit Hermitian pinnalla // Journal of the London Mathematical Society . - 2005. - T. 72 , no. 3 . — S. 731–741 . - doi : 10.1112/S0024610705006964 .
↑ Andriy V. Bondarenko, Danylo V. Radchenko. Vahvasti säännöllisten kaavioiden perheessä // Journal of Combinatorial Theory . - 2013. - T. 103 , no. 4 . - S. 521-531 . - doi : 10.1016/j.jctb.2013.05.005 . $\lambda=1$
↑ Makhnev A. A. Vahvasti säännöllisillä kaavioilla // Matem. muistiinpanoja. - 1988. - T. 44 , no. 5 . - S. 667-672, 702 . $\lambda=1$
↑ Sa'ar Zehavi, Ivo Fagundes David de Olivera. Ei Conwayn 99-kaavion ongelma. - 2017. - arXiv : 1707.08047 .
↑ Akira Hiraki, Kazumasa Nomura, Hiroshi Suzuki. Etäisyyssäännölliset kaaviot valenssista 6 ja // Journal of Algebraic Combinatorics. - 2000. - T. 11 , no. 2 . — S. 101–134 . - doi : 10.1023/A:1008776031839 . $a_1=1$