Yerel olarak doğrusal grafik - Locally linear graph

Dokuz köşeli Paley grafiği yerel olarak doğrusaldır. Altı üçgeninden biri yeşil renkle vurgulanmıştır.

Olarak grafik teorisi , bir lokal lineer bir grafiktir bir olan yönsüz grafik her kenar tam bir üçgen ait olduğu. Eşdeğer olarak, grafiğin her köşesi için komşularının her biri tam olarak bir diğer komşuya bitişiktir, bu nedenle komşular bir uyarılmış eşleşmeye eşleştirilebilir . Yerel olarak doğrusal grafikler, yerel olarak eşleştirilmiş grafikler olarak da adlandırılır.

Yerel olarak doğrusal grafikler için birçok yapı bilinmektedir. Yerel olarak doğrusal grafiklere örnek olarak üçgen kaktüs grafikleri , 3-düzenli üçgen içermeyen grafiklerin çizgi grafikleri ve daha küçük yerel doğrusal grafiklerin Kartezyen ürünleri dahildir . Belirli Kneser grafikleri ve belirli güçlü düzenli grafikler de yerel olarak doğrusaldır.

Lokal olarak lineer grafiklerin kaç tane kenarı olabileceği sorusu , Ruzsa-Szemerédi probleminin formülasyonlarından biridir . Her ne kadar yoğun grafikleri noktaların sayısının karesi ile orantılıdır kenarları bir sayı olabilir, lokal olarak doğrusal grafikleri, en az küçük bir sabit olmayan bir faktör ile kısa bir kare düşen, kenarların daha az sayıda vardır. Yerel olarak doğrusal olabilen en yoğun düzlemsel grafikler de bilinmektedir. En az yoğun yerel doğrusal grafikler üçgen kaktüs grafikleridir.

İnşaatlar

Yapıştırma ve ürünler

Arkadaşlık grafikleri

Dostluğu grafikleri tek paylaşılan tepe birlikte üçgen bir koleksiyon yapıştırma ile oluşturulan, grafikler, lokal olarak doğrusaldır. Her bir köşe çiftinin (bitişik veya değil) tam olarak bir ortak komşuyu paylaştığı daha güçlü özelliğe sahip tek sonlu grafiklerdir. Daha genel olarak, her üçgen kaktüs grafiği , herhangi bir ek döngü oluşturmadan üçgenlerin ortak köşelere yapıştırılmasıyla oluşturulan bir grafik, yerel olarak doğrusaldır.

Yerel olarak doğrusal grafikler, grafikler üzerinde klik toplamı işleminin bir biçimi olan aşağıdaki işlemle daha küçük yerel doğrusal grafiklerden oluşturulabilir . Herhangi iki yerel doğrusal grafik olsun ve her birinden bir üçgen seçin ve seçilen iki üçgende karşılık gelen köşe çiftlerini birleştirerek iki grafiği yapıştırın. Daha sonra elde edilen grafik yerel olarak doğrusal kalır. ${\görüntüleme stili G}$${\görüntüleme stili H}$

Kartezyen ürün lokal olarak doğrusal herhangi iki lokal doğrusal grafikleri kalıntılarının üründe herhangi üçgenler birinde üçgenler veya diğer faktörler geliyor çünkü. Örneğin, dokuz köşeli Paley grafiği ( 3-3 ikili prizmanın grafiği ) iki üçgenin Kartezyen çarpımıdır. Hamming grafik bir Kartezyen ürün üçgenler ve yine lokal olarak doğrusaldır. ${\görüntüleme stili H(d,3)}$${\görüntüleme stili d}$

Daha küçük grafiklerden

Kendileri yerel olarak doğrusal olmayan bazı grafikler, daha büyük yerel olarak doğrusal grafikler oluşturmak için bir çerçeve olarak kullanılabilir. Böyle bir yapı çizgi grafikleri içerir . Herhangi bir grafik için çizgi grafiği , her kenarı için bir tepe noktası olan bir grafiktir . Temsil ettikleri iki kenar ortak bir bitiş noktasına sahip olduğunda, içindeki iki köşe bitişiktir . Eğer a, 3-düzenli üçgen içermeyen grafik , daha sonra çizgi grafiği 4-düzenli ve yerel olarak doğrusaldır. Her tepe için bir üçgen vardır ve üç kenar olaya karşılık gelen üçgenin ile . Her 4 düzenli yerel doğrusal grafik bu şekilde oluşturulabilir. Örneğin, küboctahedronun grafiği bir küpün çizgi grafiğidir, dolayısıyla yerel olarak doğrusaldır. Yukarıda Kartezyen bir ürün olarak oluşturulan yerel doğrusal dokuz köşeli Paley grafiği, fayda grafiğinin çizgi grafiği gibi farklı bir şekilde de oluşturulabilir . Petersen grafiğinin çizgi grafiği de bu yapı ile yerel olarak doğrusaldır. Kafeslere benzer bir özelliği vardır : en büyük kliğin üç köşesi olduğu, her tepe noktasının tam olarak iki ayrık klikte olduğu ve farklı kliklerden kenarları olan en kısa döngünün uzunluğu beş olan mümkün olan en küçük grafiktir . ${\görüntüleme stili G}$${\görüntüleme stili L(G)}$${\görüntüleme stili G}$${\görüntüleme stili L(G)}$${\görüntüleme stili G}$${\görüntüleme stili G}$ ${\görüntüleme stili L(G)}$${\görüntüleme stili v}$${\görüntüleme stili G}$${\görüntüleme stili v}$ ${\ Displaystyle K_{3,3}}$

Cuboctahedron , bir küp çizgi grafik olarak veya bir 4-döngüsünün iç ve dış yüzleri üzerine antiprisms yapıştırma ile oluşturulabilir grafik doğrusal lokal olarak düzlemsel bir

Düzlemsel grafikler için daha karmaşık bir genişleme süreci geçerlidir . Her yüz bir dörtgen olacak şekilde düzleme gömülü bir düzlemsel grafik olsun , örneğin bir küpün grafiği gibi. 'nin her yüzüne kare bir antiprizma yapıştırmak ve ardından orijinal kenarlarını silmek, yeni bir yerel doğrusal düzlemsel grafik üretir. Kenarları ve sonuç köşe sayısı hesaplanabilir Euler-yüzlü formül edin: sahip köşe, tam olan yüzleri ve yüzlerini değiştirilmesi sonucu antiprisms göre olan köşeleri ve kenarlarının. Örneğin, küboktahedron yine bu şekilde 4 çevrimin iki yüzünden (iç ve dış) üretilebilir. Bu yapının kaldırılan 4-döngüsü, küboctahedron üzerinde, çokyüzlüyü ikiye bölen kare yüzlerinin dört köşegeninin bir çevrimi olarak görülebilir. ${\görüntüleme stili G}$${\görüntüleme stili G}$${\görüntüleme stili G}$${\görüntüleme stili G}$${\görüntüleme stili n}$${\görüntüleme stili n-2}$${\görüntüleme stili G}$${\ Displaystyle 5(n-2)+2}$${\görüntüleme stili 12(n-2)}$

cebirsel yapılar

Belirli Kneser grafikleri , eşit boyutlu kümelerin kesişim modellerinden oluşturulan grafikler , yerel olarak doğrusaldır. Kneser grafikleri, temsil ettikleri kümelerin boyutu ve bu kümelerin çizildiği evrenin boyutu olmak üzere iki parametreyle tanımlanır. Kneser grafiği , bir -element kümesinin -element alt kümelerini temsil eden ( binom katsayıları için standart gösterimde) köşelere sahiptir . Bu grafikte, karşılık gelen alt kümeler ortak hiçbir öğesi olmayan ayrık kümeler olduğunda iki köşe bitişiktir . olduğu özel durumda , elde edilen grafik yerel olarak doğrusaldır, çünkü her iki ayrık eleman altkümesi için ve her ikisinden de tam olarak ayrık bir başka eleman altkümesi vardır, ne in ne de içinde olan tüm elemanlardan oluşur . Ortaya çıkan yerel olarak doğrusal grafiğin köşeleri ve kenarları vardır. Örneğin , Kneser grafiği için 15 köşe ve 45 kenar ile yerel olarak doğrusaldır. ${\displaystyle KG_{a,b}}$${\displaystyle {\tbinom {a}{b}}}$${\görüntüleme stili b}$${\görüntüleme stili bir}$${\görüntüleme stili a=3b}$${\görüntüleme stili b}$${\görüntüleme stili X}$${\görüntüleme stili Y}$${\görüntüleme stili b}$${\görüntüleme stili X}$${\görüntüleme stili Y}$${\displaystyle {\tbinom {3b}{b}}}$${\displaystyle {\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}}$${\görüntüleme stili b=2}$${\displaystyle KG_{6,2}}$

Yerel olarak doğrusal grafikler, ilerlemesiz sayı kümelerinden de oluşturulabilir. Izin bir asal sayı olmak ve izin sayıların bir alt kümesi modulo öyle ki hiçbir üç üyesi formu bir aritmetik ilerleme modulo . (Yani, bir Salem-Spencer modulo kümesidir .) Bu küme , yerel olarak doğrusal olan köşeleri ve kenarları olan üç parçalı bir grafik oluşturmak için kullanılabilir . Bu grafiği oluşturmak için, her biri ile arasında numaralandırılmış üç köşe kümesi yapın . Her dizi için aralığındadır için ve her bir elemanın bir , sayısı ile köşe bağlayan bir üçgen yapısı köşeler ilk kümesi, bir sayı ile köşe numarası ile köşe ikinci sette ve tepe köşe üçüncü setinde . Tüm bu üçgenlerin birleşimi olarak bir grafik oluşturun. Üçgenlerin birleşimi olduğu için elde edilen grafiğin her kenarı bir üçgene aittir. Ancak bu şekilde oluşturulanlardan başka üçgen olamaz. Başka bir üçgenin tepe sayılı olurdu nerede , ve tüm aittir için hiçbir aritmetik ilerlemeler söz konusu olduğu varsayımını ihlal içinde . Örneğin ve ile bu yapının sonucu dokuz köşeli Paley grafiğidir. ${\görüntüleme stili p}$${\görüntüleme stili A}$${\görüntüleme stili p}$${\görüntüleme stili A}$${\görüntüleme stili p}$${\görüntüleme stili A}$${\görüntüleme stili p}$${\ Displaystyle 3p}$${\displaystyle 3p\cdot |A|}$${\görüntüleme stili 0}$${\görüntüleme stili p-1}$${\görüntüleme stili x}$${\görüntüleme stili 0}$${\görüntüleme stili p-1}$${\görüntüleme stili bir}$${\görüntüleme stili A}$${\görüntüleme stili x}$${\görüntüleme stili x+a}$${\görüntüleme stili x+2a}$${\görüntüleme stili (x,x+a,x+a+b)}$${\görüntüleme stili bir}$${\görüntüleme stili b}$${\görüntüleme stili c=(a+b)/2}$${\görüntüleme stili A}$${\görüntüleme stili (a,c,b)}$${\görüntüleme stili A}$${\görüntüleme stili p=3}$${\displaystyle A=\{\pm 1\}}$

düzenlilik

Birkaç köşeli düzenli grafikler

Bir grafik, tüm köşeleri aynı dereceye , gelen kenarların sayısına sahip olduğunda düzgündür . Her bir yerel lineer grafiğin her bir tepe noktasında çift dereceye sahip olması gerekir, çünkü her tepe noktasındaki kenarlar üçgenler halinde eşleştirilebilir. İki yerel olarak doğrusal düzenli grafiğin Kartezyen çarpımı, faktörlerin derecelerinin toplamına eşit derecede, yine yerel olarak doğrusal ve düzenlidir. Bu nedenle, her çift derecenin düzenli yerel doğrusal grafiklerini üretmek için, ikinci dereceden (üçgenler) yerel olarak doğrusal grafiklerin Kartezyen ürünleri alınabilir.

-Normal lokal doğrusal grafikleri önerilen en az bir bu kadar herhangi bir üçgen arasındaki kesişme noktaları ve komşuları yalnız olduğundan, köşeleri. (Üçgenin hiçbir iki köşesi, yerel doğrusallığı ihlal etmeden bir komşuyu paylaşamaz.) Tam olarak bu kadar çok köşesi olan düzenli grafikler yalnızca 1, 2, 3 veya 5 olduğunda mümkündür ve bu dört durumun her biri için benzersiz olarak tanımlanır. Köşe sayısında bu sınırı karşılayan dört düzenli grafik, 3 köşeli 2 düzgün üçgen , 9 köşeli 4 düzenli Paley grafiği, 15 köşeli 6 düzenli Kneser grafiği ve 27 köşeli 10 düzenli grafiktir. grafiği tamamlamak arasında SCHLAFLI grafiği . Son 27 köşeli 10-düzenli grafik ayrıca kübik bir yüzey üzerindeki 27 çizginin kesişme grafiğini temsil eder . ${\ Displaystyle 2r}$${\ Displaystyle 6r-3}$${\görüntüleme stili r}$${\görüntüleme stili K_{3}}$${\displaystyle KG_{6,2}}$

Kesinlikle düzenli grafikler

Bir güçlü normal grafik parametrelerinin bir dörtlü ile karakterize edilebilir köşelerin sayısı, vertex olay kenarların sayısı olan köşelerin her komşu çifti için ortak komşularının sayısıdır ve her paylaşılan komşu sayısıdır bitişik olmayan köşe çifti. Zaman grafiği yerel olarak doğrusaldır. Kuvvetle düzenli grafikler olan yukarıda bahsedilen yerel doğrusal grafikler ve bunların parametreleri ${\görüntüleme stili (n,k,\lambda ,\mu )}$${\görüntüleme stili n}$${\görüntüleme stili k}$${\ Displaystyle \ lambda }$${\görüntüleme stili \mu }$${\displaystyle \lambda =1}$

• üçgen (3,2,1,0),
• dokuz köşeli Paley grafiği (9,4,1,2),
• Kneser grafiği (15,6,1,3) ve${\displaystyle KG_{6,2}}$
• Schläfli grafiğinin tümleyeni (27,10,1,5).

Diğer yerel olarak doğrusal güçlü düzenli grafikler şunları içerir:

• Brouwer-Haemers grafik (81,20,1,6),
• Berlekamp-Van Tüysüz Seidel grafik (243,22,1,2),
• Cossidente-Penttila grafik (378,52,1,8) ve
• Oyun grafiktir (729,112,1,20).

(99,14,1,2) ve (115,18,1,3) ile potansiyel olarak geçerli olan diğer kombinasyonlar, ancak bu parametrelerle güçlü düzenli grafiklerin olup olmadığı bilinmemektedir. Parametreli (99,14,1,2) güçlü düzenli bir grafiğin varlığı sorunu Conway'in 99-graf problemi olarak bilinir ve John Horton Conway çözümü için 1000$ ödül teklif etmiştir. ${\displaystyle \lambda =1}$

Mesafe-düzenli grafikler

Yerel olarak doğrusal olan sonlu sayıda 4. veya 6. derece uzaklık-düzenli grafikler vardır. Aynı derecede güçlü düzenli grafiklerin ötesinde, Petersen grafiğinin çizgi grafiğini, Hamming grafiğini ve yarıya bölünmüş Foster grafiğini de içerirler . ${\görüntüleme stili H(3,3)}$

Yoğunluk

Mümkün olan en yoğun yerel doğrusal düzlemsel grafikler, bir düzlemsel grafiğin her dörtgen yüzüne (mavi köşeler ve kesikli sarı kenarlar) bir antiprizmanın (kırmızı köşeler ve siyah kenarlar) yapıştırılmasıyla oluşturulur.

Ruzsa–Szemerédi probleminin bir formülasyonu, bir -vertex yerel lineer grafikte maksimum kenar sayısını sorar . As Imre Z. Ruzsa ve Endre Szemeredi'nin kanıtladı bu maksimum sayıdır ama her için . İlerlemesiz kümelerden yerel olarak doğrusal grafiklerin oluşturulması, kenarları olan , bilinen en yoğun yerel doğrusal grafiklere yol açar . (Bu formüllerde, , , ve sırasıyla küçük o notasyonu , büyük Omega notasyonu ve büyük O notasyonu örnekleridir .) ${\görüntüleme stili n}$${\ Displaystyle o(n^{2})}$${\displaystyle \Omega (n^{2-\varepsilon })}$${\displaystyle \varepsilon >0}$${\displaystyle n^{2}/\exp O({\sqrt {\log n}})}$${\görüntüleme stili o}$${\görüntüleme stili\Omega }$${\görüntüleme stili O}$

Arasında düzlemsel grafikler , bir yerel olarak doğrusal grafikte kenarlarının sayısı köşe olup . Grafiği cuboctahedron sonsuz dizisinde ilk bir çok-yüzlü grafikler ile köşe ve kenarları, bir dört kenarlı yüzleri genişleterek inşa antiprisms içine. Bu örnekler, üst sınıra ulaşılabileceğini göstermektedir. ${\görüntüleme stili n}$${\görüntüleme stili {\tfrac {12}{5}}(n-2)}$${\görüntüleme stili n=5k+2}$${\displaystyle {\tfrac {12}{5}}(n-2)=12k}$${\görüntüleme stili k=2,3,\nokta }$${\görüntüleme stili K_{2,k}}$${\görüntüleme stili {\tfrac {12}{5}}(n-2)}$

Her yerel doğrusal grafik, kendisinden herhangi bir eşleşme kaldırıldıktan sonra bağlı kalma özelliğine sahiptir, çünkü grafik boyunca herhangi bir yolda, eşleşen her kenar üçgeninin diğer iki kenarı ile değiştirilebilir. Bu özelliğe sahip grafikler arasında en az yoğun olan üçgen kaktüs grafikleridir ve aynı zamanda en az yoğun yerel lineer grafiklerdir.

Referanslar