Topologický graf - Topological graph

Graf s lichým křížením číslo 13 a párovým křížením číslo 15.^[1]

v matematika, a topologický graf je reprezentace a graf v letadlo, Kde vrcholy grafu jsou reprezentovány odlišnými body a hrany podle Jordan oblouky (spojené kousky Jordan křivky ) spojením odpovídajících dvojic bodů. Body představující vrcholy grafu a oblouky představující jeho hrany se nazývají vrcholy a hrany topologického grafu. Obvykle se předpokládá, že jakékoli dvě hrany topologického grafu protínají konečný počet opakování, žádná hrana neprochází vrcholem odlišným od jeho koncových bodů a žádné dvě hrany se navzájem nedotýkají (bez křížení). Topologický graf se také nazývá a výkres grafu.

Důležitou speciální třídou topologických grafů je třída geometrické grafy, kde jsou hrany reprezentovány úsečky. (Termín geometrický graf se někdy používá v širším, poněkud vágním smyslu.)

Teorie topologických grafů je oblastí teorie grafů, zabývající se hlavně kombinační vlastnosti topologických grafů, zejména s křížovými vzory jejich hran. Je to úzce spjato s kreslení grafu, obor, který je více zaměřen na aplikace, a teorie topologických grafů, která se zaměřuje na vkládání grafů do povrchů (tj. výkresů bez křížení).

Extrémní problémy pro topologické grafy

Základní problém v teorie extrémních grafů je následující: jaký je maximální počet hran, kterých je graf n vrcholy mohou mít, pokud neobsahují žádný podgraf patřící do dané třídy zakázané podgrafy? Prototyp takových výsledků je Turánova věta, kde je jeden zakázaný podgraf: kompletní graf s k vrcholy (k je opraveno). Analogické otázky lze položit pro topologické a geometrické grafy, přičemž rozdíly jsou nyní jisté geometrické subkonfigurace jsou zakázány.

Historicky je první instance takové věty způsobena Paul Erdős, který rozšířilvýsledek Heinz Hopf a Erika Pannwitz.^[2] Dokázal, že maximální počet hran, s nimiž je geometrický graf n > 2 vrcholy mohou mít bez obsazení dva nesouvislé okraje (který nemůže sdílet ani koncový bod) je n. John Conway domníval se, že toto tvrzení lze zobecnit na jednoduché topologické grafy. Topologický graf se nazývá „jednoduchý“, pokud libovolná dvojice jeho hran sdílí nejvýše jeden bod, což je buď koncový bod, nebo společný vnitřní bod, ve kterém se tyto dvě hrany správně protínají. Conway je thrackle domněnku lze nyní přeformulovat takto: Jednoduchý topologický graf s n > 2 vrcholy a nejvýše žádné dvě nesouvislé hrany n hrany.

První lineární horní mez na počtu hran takového grafu byla stanovena pomocí Lovász et al ..^[3]Nejznámější horní mez, 1,428n, prokázali Fulek a Pach.^[4] Kromě geometrických grafů je známo, že pro Conwayovu závadu platí domněnka Xmonotónní topologické grafy.^[5] Topologický graf se říká, že je x-monotónní pokud každá svislá čára protíná každou hranu maximálně v jednom bodě.

Alon a Erdős^[6] zahájil vyšetřování zevšeobecnění výše uvedené otázky v případě, že se jedná o zakázanou konfiguraci k disjunktní hrany (k > 2). Dokázali, že počet hran geometrického grafu o nvrcholy obsahující žádné 3 nesouvislé hrany je Ó(n). Optimální hranice zhruba 2,5n určil Černý.^[7]Pro větší hodnoty k, první lineární horní mez, ${ displaystyle O (k ^ {4} n)}$, založili Pach a Töröcsik.^[8] To Tóth vylepšil na ${ displaystyle O (k ^ {2} n)}$.^[9]Pro počet hran jednoduchého topologického grafu s č k disjunktní hrany, pouze an ${ displaystyle O (n log ^ {4k-8} n)}$ horní mez je známa.^[10] To znamená, že každý úplný jednoduchý topologický graf s n vrcholy má alespoň ${ displaystyle c { frac { log n} { log log n}}}$ párové křížení hran, které bylo vylepšeno na ${ displaystyle cn ^ {{ frac {1} {2}} - epsilon}}$ autor: Ruiz-Vargas.^[11] Je možné, že tuto dolní mez lze dále vylepšit na cn, kde C > 0 je konstanta.

Kvazi-planární grafy

Společný vnitřní bod dvou hran, u kterého první hrana prochází z jedné strany druhé hrany na druhou, se nazývá a přechod. Dva okraje topologického grafu přejít navzájem, pokud určí přechod. Pro jakékoli celé číslo k > 1, nazývá se topologický nebo geometrický graf k-kvazi-planární pokud nemá k pomocí této terminologie, je-li topologický graf 2-kvazi-planární, pak se jedná o rovinný grafVyplývá to z Eulerův polyedrický vzorec že každý rovinný graf s n > 2 vrcholy mají maximálně 3n - 6 hran. Proto každý 2-kvazi-planární graf s n > 2 vrcholy mají maximálně 3n - 6 hran.

Domnívá se o tom Pach et al.^[12] že každý k-kvazi-planární topologický graf s n vrcholy má maximálně C(k)nhrany, kde C(k) je konstanta závislá pouze na k. Je známo, že tato domněnka platí k = 3^[13][14] a k = 4.^[15] Je také známo, že platí pro konvexní geometrické grafy (to je pro geometrické grafy, jejichž vrcholy tvoří množinu vrcholů konvexní n-gon),^[16] a pro k-kvazi-planární topologické grafy, jejichž hrany jsou nakresleny jako X-monotónní křivky, které všechny překračují svislou čáru.^[17][18]Poslední výsledek znamená, že každý k-kvazi-planární topologický graf s n vrcholy, jejichž hrany jsou nakresleny jako X- monotónní křivky mají maximálně C(k)n logn hrany pro vhodnou konstantu C(k). U geometrických grafů to dříve prokázal Valtr.^[19] Nejznámější generál horní hranice pro počet hran a k-kvazi-planární topologický graf je ${ Displaystyle n log ^ {O ( log k)} n}$.^[20]

Křížení čísel

Od té doby Pál Turán razil jeho problém cihelny^[21] v době druhá světová válka „Stanovení nebo odhad počtu křížení grafů je oblíbeným tématem v teorii grafů a v teorii algoritmů.^[22] Publikace v předmětu však (výslovně nebo implicitně) používaly několik konkurenčních definic křížení čísel. Na to poukázali Pach a Tóth,^[23] který uvedl následující terminologii.

Křížení číslo (grafu G): Minimální počet hraničních přechodů na všech výkresech G v rovině (tj. všechny její reprezentace jako topologický graf) s vlastností, že žádné tři hrany neprojdou stejným bodem. Označuje se cr (G).

Číslo křížení párů: Minimální počet křížení dvojic hran přes všechny výkresy G. Označuje se pomocí pair-cr (G).

Zvláštní číslo: Minimální počet těch párů hran, které překračují lichý počet opakování u všech výkresů G. Označuje se lichým-cr (G).

Tyto parametry nesouvisí. Jeden má odd-cr (G) ≤ pair-cr (G) ≤ cr (G) pro každý graf G. Je známo, že cr (G) ≤ 2 (lichý-cr (G))^2[23] a ${ displaystyle O ( operatorname {pcr} (G) ^ { frac {3} {2}} log ^ {2} operatorname {pcr} (G))}$^[24]a že existuje nekonečně mnoho grafů, pro které pár-cr (G) ≠ odd-cr (G).^[1] Nejsou známy žádné příklady, pro které by číslo křížení a číslo křížení párů nebylo stejné. Vyplývá to z Věta Hanani – Tutte^[25][26] ten odd-cr (G) = 0 znamená cr (G) = 0. Je také známo, že odd-cr (G) = k naznačuje cr (G) = k pro k = 1, 2, 3.^[27]Dalším dobře prozkoumaným parametrem grafu je následující.

Přímočaré číslo křížení: Minimální počet křížení na všech přímých výkresech G v rovině (tj. všechny její reprezentace jako geometrický graf) s vlastností, že žádné tři hrany neprojdou stejným bodem. Označuje se lin-cr (G).

Podle definice má člověk cr (G) ≤ lin-cr (G) pro každý graf G. Bienstock a Dean ukázali, že existují grafy s křížením číslo 4 a s libovolně velkým přímým číslem křížení.^[28]

Problémy Ramseyho typu pro geometrické grafy

V tradičním teorie grafů, typický Výsledek typu Ramsey uvádí, že pokud obarvíme okraje dostatečně velkého úplného grafu pevným počtem barev, pak nutně najdeme a jednobarevný podgraf určitého typu.^[29] Podobné otázky lze položit pro geometrické (nebo topologické) grafy, až na to, že nyní hledáme jednobarevné (jednobarevné) podstruktury splňující určité geometrické podmínky.^[30]Jeden z prvních výsledků tohoto druhu uvádí, že každý úplný geometrický graf, jehož okraje jsou obarveny dvěma barvami, obsahuje nepřekračující monochromatický kostra.^[31] Je také pravda, že každý takový geometrický graf obsahuje ${ displaystyle left lceil { frac {n + 1} {3}} right rceil}$ disjunktní hrany stejné barvy.^[31] Existence nepřekračující se monochromatické dráhy o velikosti alespoň cn, kde C > 0 je konstanta, je dlouhodobě otevřený problém. Je známo pouze to, že každý úplný geometrický graf je na n vrcholy obsahuje nejméně křížovou jednobarevnou cestu délky ${ displaystyle n ^ { frac {2} {3}}}$.^[32]

Topologické hypergrafy

Podíváme-li se na topologický graf jako na topologickou realizaci 1-dimenzionálního zjednodušený komplex Je přirozené se ptát, jak se výše uvedené extrémní a Ramseyho problémy zobecňují na topologické realizace d-dimenzionální zjednodušené komplexy. V tomto směru existují určité počáteční výsledky, ale k identifikaci klíčových pojmů a problémů je zapotřebí dalšího výzkumu.^[33][34][35]

Říká se, že existují dva disjunktní vrcholy přejít pokud mají jejich relativní interiéry společný bod. Sada k > 3 jednoduchosti silně kříž pokud ne 2 z nich sdílí vrchol, ale jejich relativní interiéry mají společný bod.

Je známo, že soubor d-rozměrné jednoduchosti překlenuty n body v ${ displaystyle mathbb {R} ^ {d}}$ bez dvojice přechodů může mít maximum ${ displaystyle O (n ^ {d})}$ jednoduchosti a tato vazba je asymptoticky těsná.^[36] Tento výsledek byl zobecněn na sady dvourozměrných jednoduchostí v ${ displaystyle mathbb {R} ^ {2}}$ bez tří silně překračujících jednoduchostí.^[37]Pokud to zakážeme k silně překračující jednoduchost, odpovídající nejznámější horní mez je ${ displaystyle O (n ^ {d + 1- delta})}$,^[36] pro některé ${ displaystyle delta = delta (k, d) <1}$. Tento výsledek vyplývá z barevné Tverbergova věta.^[38] Je to daleko od domnělé hranice ${ displaystyle O (n ^ {d})}$.^[36]

Pro všechny pevné k > 1, můžeme vybrat maximálně ${ displaystyle O (n ^ { lceil { frac {d} {2}} rceil})}$ d-dimenzionální jednoduchosti rozložené sadou n body v ${ displaystyle mathbb {R} ^ {d}}$ s majetkem, který č k z nich sdílí společný vnitřní bod.^[36][39] To je asymptoticky těsné.

Dva trojúhelníky dovnitř ${ displaystyle mathbb {R} ^ {3}}$ se říká, že jsou téměř disjunktní pokud jsou disjunktní nebo sdílejí pouze jeden vrchol. Je to starý problém Gil Kalai a další rozhodnout, zda největší počet téměř disjunktních trojúhelníků, které lze zvolit na nějaké vrcholové množině n body v ${ displaystyle mathbb {R} ^ {3}}$ je ${ displaystyle o (n ^ {2})}$. Je známo, že existují sady n body, pro které je toto číslo alespoň ${ displaystyle cn ^ { frac {2} {3}}}$ pro vhodnou konstantu C > 0.^[40]

Reference