Topolojik grafik - Topological graph

Tek geçiş sayısı 13 ve çift geçiş sayısı 15 olan bir grafik.

Gelen matematik bir topolojik grafik bir temsilidir grafik olarak düzlem , köşeler grafiğin belirgin noktalarına ve ile temsil edilen kenarlar ile Ürdün yaylarının (yönelik bağlı adet Ürdün eğrilerinin nokta karşılık gelen çift birleştirme). Bir grafiğin köşelerini temsil eden noktalara ve kenarlarını temsil eden yaylara topolojik grafiğin köşeleri ve kenarları denir . Genellikle bir topolojik grafiğin herhangi iki kenarının sonlu sayıda kesiştiği, hiçbir kenarın uç noktalarından farklı bir tepe noktasından geçmediği ve hiçbir iki kenarın (çarpışmadan) birbirine değmediği varsayılır. Topolojik bir graf, bir grafiğin çizimi olarak da adlandırılır .

Topolojik grafiklerin önemli bir özel sınıfı , kenarların çizgi parçalarıyla temsil edildiği geometrik grafikler sınıfıdır . ( Geometrik grafik terimi bazen daha geniş, biraz belirsiz bir anlamda kullanılır.)

Topolojik grafikler teorisi , esas olarak topolojik grafiklerin birleşimsel özellikleriyle, özellikle de kenarlarının kesişme desenleriyle ilgili bir grafik teorisi alanıdır . Daha çok uygulamaya yönelik bir alan olan grafik çizimi ve yüzeylere grafiklerin gömülmesine odaklanan topolojik çizge teorisi (yani, geçişsiz çizimler) ile yakından ilgilidir .

Topolojik grafikler için aşırı problemler

Ekstrem grafikler teorisindeki temel bir problem şudur: n köşeli bir grafiğin, belirli bir yasaklı alt graf sınıfına ait hiçbir alt graf içermiyorsa sahip olabileceği maksimum kenar sayısı nedir? Bu tür sonuçların prototipi Turán teoremidir , burada yasaklanmış bir altgraf vardır: k köşeli tam bir grafik ( k sabittir). Topolojik ve geometrik grafikler için benzer sorular sorulabilir, şu farkla ki artık belirli geometrik alt konfigürasyonlar yasaklanmıştır.

Tarihsel olarak, böyle bir teoremin ilk örneği , Heinz Hopf ve Erika Pannwitz'in bir sonucunu genişleten Paul Erdős'den kaynaklanmaktadır . O bir geometrik grafiktir kenarlar sayısı olduğu kanıtlanmıştır n  > 2 köşe içeren olmadan olabilir iki ayrık kenarları (hatta bir son nokta paylaşamaz) 'dir , n . John Conway , bu ifadenin basit topolojik grafiklere genelleştirilebileceğini tahmin etti. Bir topolojik graf, kenarlarının herhangi bir çifti, bir uç nokta veya iki kenarın düzgün bir şekilde kesiştiği ortak bir iç nokta olan en fazla bir noktayı paylaşıyorsa "basit" olarak adlandırılır. Conway'in thrackle varsayımı şimdi aşağıdaki gibi yeniden formüle edilebilir: n  > 2 köşesi olan ve iki ayrık kenarı olmayan basit bir topolojik grafik , en fazla n kenarı vardır.

Böyle bir grafiğin kenar sayısı üzerindeki ilk doğrusal üst sınır Lovász ve diğerleri tarafından kurulmuştur . En iyi bilinen üst sınır, 1.428 n , Fulek ve Pach tarafından kanıtlanmıştır . Geometrik grafikler dışında, Conway'in thrackle varsayımının x- monoton topolojik grafikler için doğru olduğu bilinmektedir . Her dikey çizgi her kenarı en fazla bir noktada kesiyorsa , topolojik bir grafiğin x-monoton olduğu söylenir .

Alon ve Erdős , yasak konfigürasyonun k ayrık kenardan ( k  > 2) oluştuğu durum için yukarıdaki sorunun genelleştirilmesinin araştırmasını başlattı . 3 ayrık kenar içermeyen n köşeli geometrik bir grafiğin kenar sayısının O ( n ) olduğunu kanıtladılar . Yaklaşık 2.5 arasında bağlanan uygun n Cerny ile belirlenmiştir. Daha büyük k değerleri için , ilk doğrusal üst sınır, , Pach ve Töröcsik tarafından kurulmuştur. Bu, Tóth tarafından . K ayrık kenarı olmayan basit bir topolojik grafiğin kenar sayısı için sadece bir üst sınır bilinmektedir. Bu, n köşeli her tam basit topolojik grafiğin, Ruiz-Vargas tarafından geliştirilmiş en azından çift ​​geçiş kenarlarına sahip olduğu anlamına gelir . Bu alt sınırın, c  > 0'ın bir sabit olduğu cn'ye daha da iyileştirilmesi mümkündür . ${\ Displaystyle O(k^{4}n)}$${\ Displaystyle O(k^{2}n)}$${\displaystyle O(n\log ^{4k-8}n)}$${\displaystyle c{\frac {\log n}{\log\log n}}}$${\displaystyle cn^{{\frac {1}{2}}-\epsilon }}$

Yarı düzlemsel grafikler

Birinci kenarın ikinci kenarın bir tarafından diğer kenarına geçtiği iki kenarın ortak iç noktasına geçiş denir . Topolojik grafik iki kenarları çapraz bir geçiş tespit durumunda birbirlerine. Herhangi bir k  > 1 tamsayı için , bir topolojik veya geometrik grafiğe, k çift ​​kesişen kenarı yoksa k-yarı düzlemsel denir . Bu terminolojiyi kullanarak, eğer bir topolojik grafik 2-düzlemsel ise, o zaman düzlemsel bir grafiktir . Bu izler Euler-yüzlü formül her düzlemsel grafiği hep N  > 2 köşe en fazla 3 sahiptir , n  6 kenarları -. Bu nedenle, n  > 2 köşesi olan her 2-düzlemsel grafiğin en fazla 3 n  − 6 kenarı vardır.

Pach ve arkadaşları tarafından tahmin edilmiştir. n köşeli her k - yarı düzlemsel topolojik grafiğin en fazla c ( k ) n kenarı vardır, burada c ( k ) yalnızca k'ye bağlı bir sabittir . Bu saptama için de geçerli olduğu bilinmektedir k  = 3 ve k  aynı zamanda için de geçerli olduğu bilinmektedir = 4. dışbükey geometrik grafikler (ki noktaların bir konveks tepe kümesini oluşturan geometrik grafikler için n açılı), ve burada k - kenarları x olarak çizilen yarı düzlemsel topolojik grafikler - tümü dikey bir çizgiyi kesen monoton eğriler. Son sonuç , kenarları x- monoton eğriler olarak çizilen n köşeli her k -yarı düzlemsel topolojik grafiğin, uygun bir sabit c ( k ) için en fazla c ( k ) n  log  n kenarına sahip olduğunu gösterir . Geometrik grafikler için bu daha önce Valtr tarafından kanıtlandı. Bir k - yarı-düzlemsel topolojik grafiğin kenar sayısı için en iyi bilinen genel üst sınır . ${\displaystyle n\log ^{O(\log k)}n}$

geçiş numaraları

O zamandan beri Pál Turan icat onun tuğla fabrikası sorunu sırasında Dünya Savaşı , belirlenmesi veya grafiklerin geçiş sayılarının tahmin grafiği teoride ve algoritmaların teoride popüler bir tema olmuştur. Bununla birlikte, konuyla ilgili yayınlar (açıkça veya dolaylı olarak) kesişen sayıların birbiriyle rekabet eden birkaç tanımını kullanmıştır. Bu, aşağıdaki terminolojiyi tanıtan Pach ve Tóth tarafından belirtildi.

Geçiş sayısı ( G grafiğinin ): Üç kenarın aynı noktadan geçmemesi özelliğiyle , G'nin düzlemdeki tüm çizimleri (yani topolojik grafik olarak tüm temsilleri) üzerindeki minimum geçiş noktası sayısı . cr( G ) ile gösterilir .

Çift geçiş sayısı : G'nin tüm çizimlerinde minimum kesişen kenar çifti sayısı . çift-cr( G ) ile gösterilir.

Tek geçiş sayısı : G'nin tüm çizimlerinde tek sayıda kesişen kenar çiftlerinin minimum sayısı . Tek-cr( G ) ile gösterilir.

Bu parametreler ilgisiz değildir. Her G grafiği için tek-cr( G ) ≤ çift-cr( G ) ≤ cr( G ) vardır . cr( G ) ≤ 2(odd-cr( G )) ^{2 olduğu} ve çift-cr( G ) ≠ tek-cr( G ) için sonsuz sayıda grafik olduğu bilinmektedir . Geçiş numarasının ve çift geçiş numarasının aynı olmadığı hiçbir örnek bilinmemektedir. Bu izler Hanani'yle-Tutte teoremi tek-cr (yani G ) = 0 cr eder ( G Ayrıca tek-CR (bilinmektedir) = 0 G ) =  k eder cr (G) = k için k  = 1, 2, 3. İyi araştırılmış bir başka grafik parametresi de şudur. ${\displaystyle O(\operatöradı {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatöradı {pcr} (G))}$

Doğrusal kesişme sayısı : G'nin düzlemdeki tüm düz çizgi çizimleri (yani, geometrik bir grafik olarak tüm temsilleri) üzerindeki minimum kesişme noktası sayısı, üç kenarın aynı noktadan geçmemesi özelliği ile. lin-cr( G ) ile gösterilir.

Tanım olarak, her G grafiği için cr( G ) ≤ lin-cr( G ) vardır . Bienstock ve Dean tarafından 4 numaralı kesişme ve keyfi olarak büyük doğrusal geçiş sayısına sahip grafikler olduğu gösterilmiştir.

Geometrik grafikler için Ramsey tipi problemler

Geleneksel grafik teorisinde , tipik bir Ramsey tipi sonuç , yeterince büyük tam bir grafiğin kenarlarını sabit sayıda renkle renklendirirsek, o zaman mutlaka belirli bir tipte tek renkli bir alt grafiği bulacağımızı belirtir. Geometrik (veya topolojik) grafikler için benzer sorular sorulabilir, ancak şimdi belirli geometrik koşulları karşılayan tek renkli (tek renkli) alt yapılar arıyoruz. Bu türden ilk sonuçlardan biri, kenarları iki renkle renklendirilen her tam geometrik grafiğin, kesişmeyen tek renkli bir kapsayan ağaç içerdiğini belirtir . Bu tür her geometrik grafiğin aynı rengin ayrık kenarlarını içerdiği de doğrudur . En az cn boyutunda, c  > 0'ın sabit olduğu, kesişmeyen tek renkli bir yolun varlığı, uzun süredir devam eden açık bir problemdir. Sadece n köşe üzerindeki her tam geometrik grafiğin, en az . ${\displaystyle \sol\lceil {\frac {n+1}{3}}\sağ\rceil }$${\displaystyle n^{\frac {2}{3}}}$

topolojik hipergraflar

Bir topolojik grafiği 1 boyutlu basit bir kompleksin topolojik bir gerçekleştirmesi olarak görürsek , yukarıdaki ekstremal ve Ramsey tipi problemlerin nasıl d -boyutlu basit komplekslerin topolojik gerçekleşmelerine genellendiğini sormak doğaldır . Bu yönde bazı ilk sonuçlar var, ancak temel kavramları ve sorunları belirlemek için daha fazla araştırma yapılması gerekiyor.

İki tepe ayrık simplices söylenen çapraz göreli iç ortak bir noktaya varsa. Bir k  > 3 basit kümesi, eğer 2 tanesi bir köşeyi paylaşmıyorsa, ancak göreli içlerinin ortak bir noktası varsa, kuvvetli bir şekilde kesişir .

Bir çift geçiş basitliği olmadan n nokta tarafından yayılan bir d -boyutlu basitler kümesinin en fazla basite sahip olabileceği ve bu sınırın asimptotik olarak sıkı olduğu bilinmektedir. Bu sonuç, üç güçlü kesişen basitlik içermeyen 2 boyutlu basit kümelere genelleştirildi. Eğer k basitleri kuvvetle çaprazlamayı yasaklarsak, buna karşılık gelen en iyi bilinen üst sınır, bazıları için . Bu sonuç, renkli Tverberg teoreminden kaynaklanmaktadır . Tahmin edilen sınırdan uzaktır . ${\displaystyle \mathbb {R} ^{d}}$${\ Displaystyle O(n^{d})}$${\displaystyle \mathbb {R} ^{2}}$${\displaystyle O(n^{d+1-\delta })}$${\displaystyle \delta =\delta (k,d)<1}$${\ Displaystyle O(n^{d})}$

Herhangi bir sabit k  > 1 için, hiçbir k'nin ortak bir iç noktayı paylaşmaması özelliğiyle, bir dizi n nokta tarafından yayılan en fazla d boyutlu basitleri seçebiliriz . Bu asimptotik olarak sıkıdır. ${\displaystyle O(n^{\lceil {\frac {d}{2}}\rceil })}$ ${\displaystyle \mathbb {R} ^{d}}$

Ayrıksa veya yalnızca bir köşeyi paylaşıyorlarsa, içindeki iki üçgenin neredeyse ayrık olduğu söylenir . Eski bir sorundur Gil kalai bazı köşe sette seçilebilir neredeyse ayrık üçgenler en fazla sayıda karar vermek ve diğerleri n noktaların olduğunu . Bu sayının en azından uygun bir c  > 0 sabiti için olduğu n nokta kümesi olduğu bilinmektedir . ${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{3}}$${\görüntüleme stili o(n^{2})}$${\displaystyle cn^{\frac {2}{3}}}$

Referanslar