Lokalt linjediagram

En lokalt linjär graf är en oriktad graf i närheten av varje vertex som genereras av en matchande . Det vill säga, för alla hörn måste varje grannskap ligga intill exakt en annan hörn intill . På motsvarande sätt hör vilken kant som helst av en sådan graf till en enda triangel [1] . Lokalt linjära grafer kallas även lokalt matchande grafer [2] . $v$ $v$ $v$ $UV$ $uvw$

Exempel på lokalt linjära grafer inkluderar triangulära kaktusar , linjediagram av triangelfria 3-reguljära grafer och den direkta produkten av mindre lokalt linjära grafer. Vissa Kneser-grafer , och vissa mycket regelbundna grafer , är också lokalt linjära.

Vissa lokalt linjära grafer har ett nästan kvadratiskt antal kanter. Frågan om hur täta dessa grafer är kan vara en av formuleringarna av Ruza–Szemeredi-problemet . Även kända är de tätaste plana graferna , som kan vara lokalt linjära.

Konstruktioner och exempel

Vissa konstruktioner för lokalt linjära grafer är kända.

Klistrar och verk

Vänskapsgrafer , bildade genom att limma ihop en uppsättning trianglar vid en gemensam vertex, är lokalt linjära. Dessa är de enda finita graferna som har den starkare egenskapen att vilket par av hörn som helst (intilliggande eller inte) har exakt en gemensam närliggande vertex [3] . Mer generellt är varje triangulär kaktus , en graf där alla enkla cykler är triangulära och alla par av enkla cykler har högst en gemensam vertex, lokalt linjär.

Låt och vara vilka som helst två lokalt linjära grafer, välj en triangel från var och en av graferna och limma ihop de två graferna genom att identifiera par i dessa trianglar (detta är en sorts summa-för-klick- operation på grafer). Då förblir den resulterande grafen lokalt linjär [4] . $G$ $H$

Den direkta produkten av graferna för två lokalt linjära grafer förblir linjärt lokal, eftersom alla trianglar i produkten kommer från den ena eller den andra faktorn. Till exempel är Paley-grafen med nio hörn (grafen för en 3-3 duoprism ) den direkta produkten av två trianglar [1] . Hamminggrafer är produkter av trianglar och är därför återigen lokalt linjära [5] . $H(d,3)$ $d$

Reproduktion

Om en graf är en triangelfri 3-regelbunden graf , så är en linjegraf en graf som bildas genom att transformera varje kant av grafen till en ny vertex och koppla samman två hörn med en kant i om motsvarande kanter på grafen har en gemensam ändpunkt. Dessa grafer är 4-regelbundna och lokalt linjära. Vilken 4-regelbunden lokalt linjär graf som helst kan konstrueras på detta sätt [6] . Till exempel kan cuboctahedron- grafen utformas på detta sätt som en kublinjegraf, och nio-vertex Paley-grafen är en hjälplinjegraf . Petersen -grafens linjediagram , en annan graf av denna typ, har en egenskap som liknar celler , att det är den minsta möjliga grafen där den största klicken har tre hörn, varje hörn tillhör två icke-överlappande klick, och den kortaste cykeln med kanter från olika klick har längd fem [7] . $G$ $L(G)$ $G$ $L(G)$ $G$ $K_{{3,3}}$

En mer komplex multiplikationsprocess gäller för plana grafer . Låt vara en plan graf inbäddad i ett plan på ett sådant sätt att varje sida är fyrkantig, som en kubgraf. Det är nödvändigt, om det har hörn, att ansiktet har grafer. Om vi klistrar in ett kvadratiskt antiprisma i grafens yta och sedan tar bort de ursprungliga kanterna på grafen får vi en ny lokalt linjär plan graf med hörn och kanter [4] . Till exempel kan en kuboktaeder erhållas på detta sätt från två ytor (inre och yttre) av en 4-cykel. $G$ $G$ $n$ $n-2$ $G$ $G$ $5(n-2)+2$ $12(n-2)$

Algebraisk konstruktion

Kneser-grafen har hörn som representerar -element-delmängder av -elementuppsättningen. Två hörn är intill varandra om motsvarande delmängder inte skär varandra. När , den resulterande grafen är lokalt linjär, eftersom det för varje två icke-korsande -elementdelmängder finns exakt en -elementundermängd (komplementet av deras förening) som inte skär båda uppsättningarna. Den resulterande lokallinjegrafen har hörn och kanter. Till exempel, för Kneser är grafen lokalt linjär med 15 hörn och 45 kanter [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}$

Lokalt linjära grafer kan också konstrueras från progressionsfria uppsättningar av tal. Låta vara ett primtal och låt vara en delmängd av tal modulo , så att inga tre termer bildar en aritmetisk progression modulo . (Det vill säga, det är en Salem-Spencer-uppsättning modulo .) Sedan finns det en tredelad graf där varje del har hörn, har kanter och varje kant tillhör en enda triangel. Sedan, enligt denna konstruktion, är antalet kanter också lika med . För att bygga denna graf numrerar vi hörnen på varje sida av den tredelade grafen från till och bygger en triangel av modulo för var och en i intervallet från till och var och en av . Grafen som bildas av föreningen av dessa trianglar har den förväntade egenskapen att vilken kant som helst tillhör en enda triangel. Om så inte vore fallet skulle det finnas en triangel där , och skulle tillhöra , vilket bryter mot antagandet att det inte finns några aritmetiska progressioner i . [8] Till exempel, med och , blir resultatet en Paley-graf med nio hörn. $sid$ $A$ $sid$ $A$ $sid$ $A$ $sid$ $sid$ $3|A|p$ $n=3p$ ${\displaystyle n^{2}/e^{O({\sqrt {\log n)))))$ $0$ $p-1$ $(x,x+a,x+2a)$ $sid$ $x$ $0$ $p-1$ $a$ $A$ $(x,x+a,x+a+b)$ $a$ $b$ $c=(a+b)/2$ $A$ $(a,c,b)$ $A$ $p=3$ ${\displaystyle A=\{\pm 1\))$

Regelbundna och starkt regelbundna grafer

Varje graf med lokal linje måste ha en jämn grad för varje vertex, eftersom en kant vid varje vertex kan paras ihop till trianglar. Den direkta produkten av två lokalt linjära reguljära grafer är återigen lokalt linjär och regelbunden med grad lika med summan av faktorernas potenser. Således finns det regelbundna lokalt linjära grafer av vilken jämn grad som helst [1] . -Vanliga lokalt linjegrafer måste ha åtminstone hörn, eftersom det finns så många trianglar och grannar. (Inga två hörn i en triangel kan ha gemensamma grannar utan att bryta lokal linjäritet.) Reguljära grafer med exakt detta antal hörn är endast möjliga när 1, 2, 3 eller 5 är unikt definierade för vart och ett av dessa fyra fall. De fyra reguljära graferna på vilka denna gräns nås som en funktion av antalet hörn är den 2-regelbundna triangeln (3 hörn), den 4-regelbundna Paley-grafen (9 hörn), den 6-regelbundna Kneser-grafen (15 hörn) , och det 10-regelbundna komplementet Greve Schläfli (27 toppar). Den sista 27-vertex 10-reguljära grafen i listan är också en 27-linjers skärningsgraf på en kubisk yta [2] . $2r$ $6r-3$ $r$ $K_{3}$ $KG_{6,2}$

En starkt regelbunden graf kan beskrivas med en fyrdubbling av parametrar , där är lika med antalet hörn, är lika med antalet kanter som faller in mot vertexen, är lika med antalet gemensamma grannar för alla intilliggande hörnpar, och är lika med antalet gemensamma grannar för alla icke intilliggande hörnpar. När , är grafen lokalt linjär. Lokalt linjära grafer, som nämnts ovan, är starkt regelbundna och deras parametrar är det $(n,k,\lambda ,\mu )$ $n$ $k$ $\lambda$ $\mu$ $\lambda=1$

triangel (3,2,1,0),
Paley-graf med nio hörn (9,4,1,2),
Antal Kneser (15,6,1,3), $KG_{6,2}$
komplement till Schläfli-grafen (27,10,1,5).

Andra lokalt linjära starkt regelbundna grafer

Brouwer-Hemers-grafen (81,20,1,6) [9]
greve av Berlekamp-van Lint-Seidel (243,22,1,2) [10]
Greve Cossidente - Penttils (378,52,1,8), [11]
Earl of Games (729,112,1,20). [12]

Andra potentiellt giltiga kombinationer med inkluderar (99,14,1,2) och (115,18,1,3), men det är inte känt om det finns starkt regelbundna grafer med dessa parametrar [13] . Frågan om förekomsten av en starkt regelbunden graf med parametrar (99,14,1,2) är känd som Conways 99-grafproblem, och John Horton Conway erbjöd ett pris på $1 000 till den som löste det [14] . $\lambda=1$

Det finns oändligt många avstånd-reguljära grafer av grad 4 eller 6 som är lokalt linjära. Förutom starkt regelbundna grafer av samma grad inkluderar de linjegrafen för Petersen-grafen, Hamming-grafen och halva Foster-grafen [15] . $H(3,3)$

Densitet

En av formuleringarna av Ruzi-Szemeredi- problemet frågar om det maximala antalet kanter i en lokalt linjär graf med hörn. Som Imre Z. Rouja och Endre Szemeredy bevisade är detta maximala antal lika med , men också lika med någon . Konstruktionen av lokalt linjära grafer från progressionsfria uppsättningar leder till de tätaste kända lokalt linjära graferna med kanter [8] . $n$ $o(n^{2})$ $\Omega (n^{2-\varepsilon })$ $\varepsilon >0$ $n^{2}/\exp O({\sqrt {\log n)))$

Bland plana grafer är det maximala antalet kanter i en lokalt linjär vertexgraf . Kubaktaedergrafen är den första i en oändlig sekvens av polyedriska grafer med hörn och kanter för , konstruerade genom att expandera kvadratiska ytor till antiprismor. Dessa exempel visar att denna övre gräns är exakt [4] . $n$ ${\tfrac {12}{5}}(n-2)$ $n=5k+2$ ${\tfrac {12}{5}}(n-2)=12k$ $k=2,3,\dots$ ${\displaystyle K_{2,k))$

Anteckningar

↑ 1 2 3 Dalibor Fronček. Lokalt linjära grafer // Mathematica Slovaca. - 1989. - T. 39 , nr. 1 . — S. 3–6 .
↑ 1 2 3 Larrión F., Pizaña MA, Villarroel-Flores R. Små lokalt nK 2 grafer // Ars Combinatoria. - 2011. - T. 102 . — S. 385–391 .
↑ Paul Erdős , Alfred Rényi , Vera T. Sós . Om ett problem med grafteori // Studia Sci. Matematik. Ungern.. - 1966. - T. 1 . — S. 215–235 .
↑ 1 2 3 Bohdan Zelinka. Polytopa lokalt linjära grafer // Mathematica Slovaca. - 1988. - T. 38 , nr. 2 . — S. 99–103 .
↑ Alice Devillers, Wei Jin, Cai Heng Li, Cheryl E. Praeger. Lokal 2-geodesisk transitivitet och klickgrafer // Journal of Combinatorial Theory . - 2013. - T. 120 , nr. 2 . — S. 500–508 . - doi : 10.1016/j.jcta.2012.10.004 . . I notationen av denna referens betecknas familjen av -regelbundna grafer som . $2r$ $F(r,2)$
↑ Andrea Munaro. On line grafer av subkubiska triangelfria grafer // Diskret matematik . - 2017. - T. 340 , nr. 6 . - S. 1210-1226 . - doi : 10.1016/j.disc.2017.01.006 .
↑ Kong Fan. Om generaliserade burar // Journal of Graph Theory. - 1996. - T. 23 , nr. 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. Trippelsystem utan sex punkter som bär tre trianglar // Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II. - Nord-Holland, 1978. - T. 18. - S. 939-945. - (Colloq. Math. Soc. Janos Bolyai).
↑ Brouwer AE, Haemers WH Struktur och unikhet hos den (81,20,1,6) starkt regelbundna grafen // Diskret matematik . - 1992. - T. 106/107 . — s. 77–82 . - doi : 10.1016/0012-365X(92)90532-K .
↑ Berlekamp ER, van Lint JH, Seidel JJ En starkt regelbunden graf härledd från den perfekta ternära Golay-koden // A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971). - Nord-Holland, 1973. - S. 25-30 . - doi : 10.1016/B978-0-7204-2262-7.50008-9 .
↑ Antonio Cossidente, Tim Penttila. Hemisystems on the Hermitian yta // Journal of the London Mathematical Society . - 2005. - T. 72 , nr. 3 . — S. 731–741 . - doi : 10.1112/S0024610705006964 .
↑ Andriy V. Bondarenko, Danylo V. Radchenko. På en familj av starkt regelbundna grafer med // Journal of Combinatorial Theory . - 2013. - T. 103 , nr. 4 . — S. 521–531 . - doi : 10.1016/j.jctb.2013.05.005 . $\lambda=1$
↑ Makhnev A. A. På starkt regelbundna grafer med // Matem. anteckningar. - 1988. - T. 44 , nr. 5 . — S. 667–672, 702 . $\lambda=1$
↑ Sa'ar Zehavi, Ivo Fagundes David de Olivera. Inte Conways 99-grafproblem. - 2017. - arXiv : 1707.08047 .
↑ Akira Hiraki, Kazumasa Nomura, Hiroshi Suzuki. Avståndsreguljära grafer av valens 6 och // Journal of Algebraic Combinatorics. - 2000. - T. 11 , nr. 2 . — S. 101–134 . - doi : 10.1023/A:1008776031839 . $a_1=1$