Topologisk graf

En graf med udda korsningsnummer 13 och parkorsningsnummer 15.

I matematik är en topologisk graf en representation av en graf i planet , där grafens hörn representeras av distinkta punkter och kanterna av Jordanbågar (sammankopplade delar av Jordan-kurvor ) som förenar motsvarande par av punkter. Punkterna som representerar en grafs hörn och bågarna som representerar dess kanter kallas hörn och kanter på den topologiska grafen. Det antas vanligtvis att två kanter på en topologisk graf korsar ett ändligt antal gånger, ingen kant passerar genom en spets som skiljer sig från dess ändpunkter och att inga två kanter rör vid varandra (utan att korsa). En topologisk graf kallas också en ritning av en graf.

En viktig specialklass av topologiska grafer är klassen av geometriska grafer , där kanterna representeras av linjesegment . (Termen geometrisk graf används ibland i en bredare, något vag betydelse.)

Teorin för topologiska grafer är ett område av grafteorin , huvudsakligen berört med kombinatoriska egenskaper hos topologiska grafer, i synnerhet med korsningsmönstren för deras kanter. Det är nära besläktat med grafritning , ett fält som är mer applikationsorienterat, och topologisk grafteori , som fokuserar på inbäddningar av grafer i ytor (det vill säga ritningar utan korsningar).

Extrema problem för topologiska grafer

Ett grundläggande problem i extremal grafteori är följande: vad är det maximala antalet kanter som en graf med n hörn kan ha om den inte innehåller någon subgraf som tillhör en given klass av förbjudna subgrafer ? Prototypen för sådana resultat är Turáns sats , där det finns en förbjuden subgraf: en komplett graf med k hörn ( k är fast). Analoga frågor kan ställas för topologiska och geometriska grafer, med skillnaden att nu är vissa geometriska underkonfigurationer förbjudna.

Historiskt sett beror det första exemplet på en sådan teorem på Paul Erdős , som utökade ett resultat av Heinz Hopf och Erika Pannwitz . Han bevisade att det maximala antalet kanter som en geometrisk graf med n > 2 hörn kan ha utan att innehålla två disjunkta kanter (som inte ens kan dela en ändpunkt) är n . John Conway förmodade att detta uttalande kan generaliseras till enkla topologiska grafer. En topologisk graf kallas "enkel" om något par av dess kanter delar högst en punkt, som antingen är en ändpunkt eller en gemensam inre punkt där de två kanterna korsar varandra. Conways thrackle -förmodan kan nu omformuleras enligt följande: En enkel topologisk graf med n > 2 hörn och inga två disjunkta kanter har högst n kanter.

Den första linjära övre gränsen för antalet kanter av en sådan graf fastställdes av Lovász et al. Den mest kända övre gränsen, 1,3984 n , bevisades av Fulek och Pach . Bortsett från geometriska grafer är Conways thrackle-förmodan känd för att vara sann för x -monotona topologiska grafer. En topologisk graf sägs vara x-monotone om varje vertikal linje skär varje kant i högst en punkt.

Alon och Erdős inledde undersökningen av generaliseringen av ovanstående fråga till fallet där den förbjudna konfigurationen består av k disjunkta kanter ( k > 2). De bevisade att antalet kanter på en geometrisk graf med n hörn, som inte innehåller 3 osammanhängande kanter är O ( n ). Den optimala gränsen på ungefär 2,5 n bestämdes av Černý. För större värden på k fastställdes den första linjära övre gränsen, ${\displaystyle O(k^{4}n)} av Pach och Töröcsik.$ Detta förbättrades av Tóth till $O(k^{2}n)$ . För antalet kanter i en enkel topologisk graf utan k disjunkta kanter är endast en $O(n\log ^{4k-8}n)$ övre gräns känd . Detta innebär att varje komplett enkel topologisk graf med n hörn har åtminstone $c{\frac {\log n}{\log \log n}}$ parvisa disjunkta kanter, vilket var förbättrad till $cn^{{\frac {1}{2}}-\epsilon }$ av Ruiz-Vargas. Det är möjligt att denna nedre gräns kan förbättras ytterligare till cn , där c > 0 är en konstant.

Kvasiplanära grafer

En gemensam inre punkt av två kanter, där den första kanten passerar från den ena sidan av den andra kanten till den andra, kallas en korsning . Två kanter på en topologisk graf korsar varandra om de bestämmer en korsning. För varje heltal k > 1 kallas en topologisk eller geometrisk graf k-kvasiplanär om den inte har några k parvisa korsande kanter. Med denna terminologi, om en topologisk graf är 2-kvasiplanär, så är det en plan graf . Det följer av Eulers polyedriska formel att varje plan graf med n > 2 hörn har högst 3 n − 6 kanter. Därför har varje 2-kvasiplanar graf med n > 2 hörn högst 3 n − 6 kanter.

Det har givits av Pach et al. att varje k -kvasiplanar topologisk graf med n hörn har som mest c ( k ) n kanter, där c ( k ) är en konstant som endast beror på k . Denna gissning är känd för att vara sann för k = 3 och k = 4. Den är också känd för att vara sann för konvexa geometriska grafer (det vill säga för geometriska grafer vars hörn bildar vertexuppsättningen av en konvex n -gon), och för k -kvasiplanära topologiska grafer vars kanter är ritade som x -monotona kurvor, som alla korsar en vertikal linje. Det sista resultatet antyder att varje k -kvasiplanar topologisk graf med n hörn, vars kanter är ritade som x -monotona kurvor har högst c ( k ) n log n kanter för en lämplig konstant c ( k ). För geometriska grafer bevisades detta tidigare av Valtr. Den mest kända allmänna övre gränsen för antalet kanter på en k -kvasiplanar topologisk graf är $n\log ^{O(\log k)}n$ . Detta innebär att varje komplett topologisk graf med n hörn har minst $n^{\frac {1}{O(\log \log n)}}$ parvisa korsande kanter, vilket förbättrades till en kvasilinjär gräns i fallet med geometriska grafer.

Korsande siffror

Ända sedan Pál Turán myntade sitt tegelfabriksproblem under andra världskriget har bestämning eller uppskattning av korsning av antal grafer varit ett populärt tema inom grafteorin och i teorin om algoritmer som är rikligt med kända långvariga öppna problem som Albertson gissningar , Harary-Hills gissningar eller det fortfarande olösta Turáns tegelfabriksproblem . Publikationerna i ämnet (explicit eller implicit) använde dock flera konkurrerande definitioner av korsning av siffror. Detta påpekades av Pach och Tóth, som introducerade följande terminologi.

Korsningsnummer (av en graf G ): Det minsta antalet korsningspunkter över alla ritningar av G i planet (det vill säga alla dess representationer som en topologisk graf) med egenskapen att inga tre kanter passerar genom samma punkt. Det betecknas med cr( G ).

Antal korsande par : Minsta antal korsande kanter över alla ritningar av G . Det betecknas med par-cr( G ).

Udda korsningsnummer : Det minsta antalet av dessa par av kanter som korsar ett udda antal gånger, över alla ritningar av G . Det betecknas med udda-cr( G ).

Dessa parametrar är inte orelaterade. Man har udda-cr( G ) ≤ par-cr( G ) ≤ cr( G ) för varje graf G . Det är känt att cr( G ) ≤ 2(udda-cr( G )) ² och $O(\operatörsnamn {pcr} (G )^{\frac {3}{2}}\log ^{2}\operatörsnamn {pcr} (G))$ och att det finns oändligt många grafer för vilka par-cr( G ) ≠ udda-cr( G ) . Inga exempel är kända där korsningsnumret och parkorsningsnumret inte är samma. Det följer av Hanani–Tuttes sats att odd-cr( G ) = 0 innebär cr( G ) = 0. Det är också känt att odd-cr( G ) = k innebär cr(G)=k för k = 1, 2, 3. En annan väl undersökt grafparameter är följande.

Rättlinjigt korsningsnummer : Det minsta antalet korsningspunkter över alla rätlinjiga ritningar av G i planet (det vill säga alla dess representationer som en geometrisk graf) med egenskapen att inga tre kanter passerar genom samma punkt. Det betecknas med lin-cr( G ).

Per definition har man cr( G ) ≤ lin-cr( G ) för varje graf G . Det visades av Bienstock och Dean att det finns grafer med korsningsnummer 4 och med godtyckligt stort rätlinjigt korsningsnummer.

Beräkning av korsningsnumret är NP-komplett i allmänhet. Därför fokuserar en stor mängd forskning på sina uppskattningar. Crossing Lemma är ett hörnstensresultat som ger allmänt tillämpliga nedre gränser för korsningsnumret. Flera intressanta varianter och generaliseringar av Crossing Lemma är kända för Jordan-kurvor och degenererade korsningstal, där det senare relaterar föreställningen om korsningstalet till grafsläktet .

Ramsey-typ problem för geometriska grafer

I traditionell grafteori säger ett typiskt resultat av Ramsey-typ att om vi färgar kanterna på en tillräckligt stor komplett graf med ett fast antal färger, så hittar vi nödvändigtvis en monokromatisk subgraf av en viss typ. Man kan ställa liknande frågor för geometriska (eller topologiska) grafer, förutom att vi nu letar efter monokromatiska (enfärgade) understrukturer som uppfyller vissa geometriska villkor. Ett av de första resultaten av detta slag säger att varje komplett geometrisk graf vars kanter är färgade med två färger innehåller ett icke-korsande monokromatiskt spännträd . Det är också sant att varje sådan geometrisk graf innehåller $\left\lceil {\frac {n+1}{3}}\right\rceil$ osammanhängande kanter av samma färg. Förekomsten av en icke-korsande monokromatisk bana av storleken åtminstone cn , där c > 0 är en konstant, är ett långvarigt öppet problem. Det är bara känt att varje komplett geometrisk graf på n hörn innehåller en icke-korsande monokromatisk bana med längd minst $n^{\frac {2}{3}}$ .

Topologiska hypergrafer

Om vi ser en topologisk graf som en topologisk realisering av ett 1-dimensionellt förenklat komplex , är det naturligt att fråga hur ovanstående extrema och Ramsey-typ problem generaliserar till topologiska realiseringar av d -dimensionella förenklade komplex. Det finns några initiala resultat i denna riktning, men det kräver ytterligare forskning för att identifiera nyckelbegrepp och problem.

Två vertex disjunkta simplices sägs korsa om deras relativa inre har en punkt gemensamt. En uppsättning av k > 3 förenklingar korsar starkt om inte två av dem delar en vertex, men deras relativa inre har en punkt gemensam.

Det är känt att en uppsättning d -dimensionella förenklingar som sträcks av n punkter i $\mathbb {R} ^{d}$ utan ett par korsande förenklingar kan ha högst $O (n^{d})$ förenklade och denna gräns är asymptotiskt snäv. Detta resultat generaliserades till uppsättningar av 2-dimensionella förenklingar i $\mathbb {R} ^{2}$ utan tre starkt korsande förenklingar. Om vi förbjuder k att kraftigt korsa förenklingar, är motsvarande mest kända övre gräns $O(n^{d+1-\delta })$ , för vissa $\delta =\delta (k,d)<1$ . Detta resultat följer av den färgade Tverbergs satsen . Det är långt ifrån den förmodade gränsen för $O(n^{d})$ .

För vilken fast k > 1 som helst kan vi välja högst $O(n^{\lceil {\frac {d}{2}}\rceil })$ d -dimensionella förenklingar spännde av en uppsättning av n punkter i $\mathbb {R} ^{d}$ med egenskapen att ingen k av dem delar en gemensam inre punkt. Detta är asymptotiskt snävt.

Två trianglar i $\mathbb {R} ^{3}$ sägs vara nästan disjunkta om de är disjunkta eller om de bara delar en vertex. Det är ett gammalt problem för Gil Kalai och andra att avgöra om det största antalet nästan osammanhängande trianglar som kan väljas på någon vertexuppsättning av n punkter i $\mathbb {R} ^{3}$ är $o(n^{2})$ . Det är känt att det finns uppsättningar av n punkter för vilka detta tal är åtminstone $cn^{\frac {3}{2}}$ för en lämplig konstant c > 0.