Topologisk graf

En topologisk graf är en representation av en graf på ett plan , där grafens hörn representeras av olika punkter, och kanterna är Jordan-kurvor (sammankopplade delar av Jordan-kurvor ) som förbinder motsvarande par av punkter . Punkterna som representerar grafens hörn och bågarna som representerar kanterna kallas för den topologiska grafens hörn och kanter . Det antas vanligtvis att två kanter på en topologisk graf skär ett ändligt talgånger, medan ingen kant passerar genom spetsen (förutom när spetsen är kantens ändpunkt) och inga två kanter berör 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 kanter representeras av linjesegment . (Termen geometrisk graf används också i en vidare och inte helt tydlig betydelse.)

Topologisk grafteori är en gren av grafteorin som främst handlar om de kombinatoriska egenskaperna hos topologiska grafer, i synnerhet skärningspunkten mellan kanter. Teorin är nära besläktad med grafvisualisering, som är mer tillämpningsorienterad, och topologisk grafteori , som särskilt specialiserar sig på inbäddningar av grafer i ytor (det vill säga kartlägga dem utan skärningspunkter).

Extrema problem för topologiska grafer

Det grundläggande problemet med extremal grafteori är följande: "Vilket är det största antalet kanter som en graf med n hörn kan ha om den inte innehåller subgrafer av en given klass av förbjudna subgrafer ?". Ett av de första resultaten av att lösa detta problem är Turans sats , som har en förbjuden subgraf, en komplett graf med k hörn ( k är fast). Liknande problem finns för topologiska och geometriska grafer med andra förbjudna geometriska underkonfigurationer .

Historiskt sett var den första av satserna om denna fråga satsen från Pal Erdős , som utökade resultatet av Heinz Hopf och Erika Pannwitz [2] . Han bevisade att det maximala antalet kanter som en geometrisk graf med hörn kan ha som inte innehåller två icke-korsande kanter (även utan gemensamma ändhörn) ä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 har minst en gemensam punkt, som antingen är ändpunkten (bågvertex) eller den gemensamma inre punkten för två skärande bågar. Conways trekle -förmodan kan nu omformuleras enligt följande: "En enkel topologisk vertexgraf där inga två kanter skär varandra har högst n kanter." Den första övre gränsen för antalet kanter av en sådan graf fastställdes av Lovas , Pach och Shegedi [3] . Den minsta kända övre gränsen (1.428 n ) hittades av Fulek och Pach [4] . Förutom geometriska grafer är det känt att Conways gissningar om treckles är sanna för x -monotona topologiska grafer [5] . En topologisk graf sägs vara x-monotone , om någon vertikal linje skär kanten i högst en punkt.

Alon och Erdős [6] initierade forskning för att generalisera ovanstående frågor för de fall då den förbjudna konfigurationen består av k -disjunkta kanter ( ). De bevisade att antalet kanter i en n -vertex geometrisk graf som inte innehåller 3-disjunkta kanter är O ( n ). En optimal gräns på cirka 2,5 n hittades av Czerny [7] . För stora värden på k fastställde Pakh och Terechik [8] den första linjära övre gränsen . Det förbättrades av Tos till [9] . På antalet kanter av enkla topologiska grafer som inte har k -disjunkta kanter är endast den övre gränsen känd [10] . Det följer av detta att varje komplett enkel topologisk graf med n hörn har åtminstone kanter. Detta värde har förbättrats till Ruiz-Vargas [11] .

Kvasiplanära grafer

Den gemensamma inre punkten för två kanter, där den första kanten passerar från ena sidan av den andra kanten till dess andra sida, kallas en skärning . Två kanter på en topologisk graf skär varandra om de har en skärning. För vilket heltal som helst kallas en topologisk eller geometrisk graf k-kvasiplanar om den inte har k parvis skärande kanter. Med sådan terminologi, om en topologisk graf är 2-kvasiplanär, så är det en plan graf . Det följer av Eulers formel att varje plan graf med hörn har som mest kanter. Därför har varje 2-kvasiplanär graf med hörn på de flesta kanter.

Pach, Szarohi och Mari [12] förmodade att varje k -kvasiplanär topologisk graf med n hörn har som mest 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 [13] [14] och [15] . Det är också känt att vara sant för konvexa geometriska grafer (det vill säga geometriska grafer vars hörn bildar en konvex n - gon) [16] , såväl som för k -kvasiplanära topologiska grafer vars kanter representeras som x -monotona kurvor som skär en vertikal linje [ 17] [18] . Det följer av det sista resultatet att varje k -kvasiplanär topologisk graf med n hörn, vars kanter är ritade som x -monotona kurvor, har som mest kanter för motsvarande konstant c ( k ). För geometriska grafer bevisades detta påstående tidigare av Waltre [19] . Den minst kända gemensamma övre gränsen för antalet kanter av en k -kvasiplanar topologisk graf är [20] . En preliminär version av detta resultat publicerades i Jakob Fox och Janos Pach [21] .

Korsande nummer

Ända sedan Pal Turan formulerade sitt tegelfabriksproblem [22] under andra världskriget , har bestämning eller uppskattning av skärningsantal av grafer varit ett populärt ämne inom grafteori och algoritmteori [23] . Publikationer om frågan har dock (explicit eller implicit) använt några konkurrerande definitioner av antalet korsningar. Detta påpekades av Pach och Tos [9] och föreslog följande terminologi.

Antal skärningspunkter (av en graf G ): Det minsta antalet skärningspunkter bland alla ritningar av en graf G i planet (det vill säga alla representationer av en graf som en topologisk graf) med egenskapen att inga tre kanter passerar genom samma punkt. Detta nummer betecknas som cr( G ).

Antal parvisa korsningar : Det minsta antalet korsande kantpar bland alla ritningar av graf G. Detta nummer betecknas som par-cr( G ).

Antal udda korsningar : Det minsta antalet par kanter som skär ett udda antal gånger bland alla ritningar i graf G. Detta nummer betecknas som udda-cr( G ).

Dessa parametrar är inte oberoende. Vi har för vilken graf som helst G . Det är känt att [24] och [25] , och även att det finns oändligt många grafer för vilka [1] . En preliminär version av dessa resultat tillkännagavs i en artikel av Pelsmeier, Stefankovic och Schaefer [26] . Inget exempel är känt där antalet korsningar och det parvisa antalet korsningar inte är lika. Det följer av Hanani-Tatta-satsen [27] [28] att . Det är också känt att från följer för [29] .

En annan väl studerad grafparameter är antalet räta linjekorsningar . Det är det minsta antalet skärningspunkter bland alla ritningar av en graf G i planet med linjesegment (det vill säga bland alla representationer i form av en geometrisk graf) med egenskapen att inga tre kanter passerar genom samma punkt. Numret betecknas som lin-cr( G ).

Per definition har vi för vilken graf som helst G . Binstock och Dean visade att det finns grafer med 4 skärningar och ett godtyckligt stort antal linjeskärningar [30] .

Ramsey-typ problem för geometriska grafer

I traditionell grafteori anger typiska resultat av Ramsey-typ att när man färglägger kanterna på en tillräckligt stor komplett graf med ett fast antal färger, är det säkert att hitta en monokromatisk subgraf av en viss typ [31] . Liknande frågor kan ställas för geometriska (eller topologiska) grafer, förutom att i detta fall eftersträvas monokroma (av samma färg) substrukturer som uppfyller vissa geometriska villkor [32] . Ett av de första resultaten av detta slag säger att varje komplett geometrisk graf vars kanter är färgade i två färger innehåller ett disjunkt monokromatiskt spännträd [33] . Det är också sant att varje sådan geometrisk graf innehåller icke-korsande kanter av samma färg [33] . Förekomsten av icke-korsande monokroma banor av storleken åtminstone cn , där är en konstant, förblir ett långvarigt olöst problem. Det är bara känt att varje komplett geometrisk graf med n hörn innehåller en icke-korsande monokrom bana med längd åtminstone [34] .

Topologiska hypergrafer

När man analyserar en topologisk graf som en topologisk realisering av ett endimensionellt förenklat komplex , uppstår frågan: hur man generaliserar de extrema Ramsey-typproblemen som beskrivs ovan till den topologiska realiseringen av d - dimensionella förenklade komplex. Det finns flera initiala resultat i denna riktning, men de kräver ytterligare forskning för att identifiera nyckelbegrepp och problem [35] [36] [37] .

Två vertexlösa simplexar sägs skära varandra om deras relativa inre har en gemensam punkt. Uppsättningar av förenklingar är strikt skärande om inte två av dem delar en gemensam vertex, men de delar alla en gemensam inre punkt.

Det är känt att uppsättningen av d -dimensionella simpliceringar som sträcks av n punkter in utan ett par korsande simpliceringar kan ha som mest simpliceringar, och denna gräns är asymptotiskt exakt [38] . Detta resultat har generaliserats till uppsättningar av tvådimensionella förenklingar utan att tre av dem skär varandra kraftigt [39] . Om vi ​​lägger ett förbud mot k starkt skärande simpliceringar, så är motsvarande välkända övre gräns [38] , för vissa . Detta resultat följer av Tverbergs färgsats [40] . Det erhållna resultatet är långt ifrån den gräns som antas i hypotesen [38] .

För vilken fix som helst kan vi välja (högst) d -dimensionella förenklingar som sträcks av en uppsättning av n punkter med egenskapen att ingen k av dem har en gemensam inre punkt [38] [41] . Denna kvantitet är asymptotiskt exakt.

De säger att två trianglar i nästan inte skär , om de inte skär varandra, eller bara har en gemensam vertex. Det finns ett gammalt problem av Gil Kalai (et al.): att avgöra om det största antalet nästan osammanhängande trianglar som kan väljas på någon uppsättning n -punkts hörn i . Det är känt att det finns uppsättningar av n punkter för vilka detta antal inte är mindre än för motsvarande konstant [42] .

Anteckningar

  1. ↑ 1 2 Pelsmajer, Schaefer, Štefankovič, 2008 , sid. 442–454.
  2. ↑ Hopf och Pannwitz, 1934 , sid. 114.
  3. ↑ Lovász, Pach, Szegedy, 1997 , sid. 369–376.
  4. ↑ Fulek, Pach, 2011 , sid. 345–355.
  5. ↑ Pach, Sterling, 2011 , sid. 544–548.
  6. ↑ Alon, Erdős, 1989 , sid. 287–290.
  7. ↑ Černý, 2005 , sid. 679–695.
  8. ↑ Pach, Töröcsik, 1994 , sid. 1–7.
  9. ↑ 12 Toth , 2000 , sid. 126–132.
  10. ↑ Pach, Toth, 2003 , sid. 133–140.
  11. ↑ Ruiz-Vargas, 2015 , sid. 29–34.
  12. ↑ Pach, Shahrokhi, Mario, 1996 , sid. 111–117.
  13. ↑ Agarwal, Aronov, Pach et al., 1997 , sid. 1–9.
  14. ↑ Ackerman, Tardos, 2007 , sid. 563–571.
  15. ↑ Ackerman, 2009 , sid. 365–375.
  16. ↑ Capoyleas, Pach, 1992 , sid. 9–15.
  17. ↑ Suk, 2011 , sid. 266–277.
  18. ↑ Fox, Pach, Suk, 2013 , sid. 550–561.
  19. ↑ Valtr, 1997 , sid. 205–218.
  20. ↑ Fox, Pach, 2012 , sid. 853–866.
  21. ↑ Fox, Pach, 2008 , sid. 346–354.
  22. ↑ Turán, 1977 , sid. 7–9.
  23. ↑ Garey och Johnson, 1983 , sid. 312–316.
  24. ↑ Pach, Toth, 2000 , sid. 225–246.
  25. ↑ Matousek, 2014 , sid. 135–139.
  26. ↑ Pelsmajer, Štefankovič, Schaefer, 2005 , sid. 386–396.
  27. ↑ Chojnacki, 1934 , sid. 135–142.
  28. ↑ Tutte, 1970 , sid. 45–53.
  29. ↑ Pelsmajer, Schaefer, Štefankovič, 2007 , sid. 489–500.
  30. ↑ Bienstock, Dean, 1993 , sid. 333–348.
  31. ↑ Graham, Rothschild, Spencer, 1990 .
  32. ↑ Károlyi, 2013 .
  33. ↑ 1 2 Károlyi, Pach och Tóth, 1997 , sid. 247–255.
  34. ↑ Károlyi, Pach, Tóth, Valtr, 1998 , sid. 375–388.
  35. ↑ Pach, 2004 .
  36. ↑ Matoušek, Dancer, Wagner, 2009 , sid. 855–864.
  37. ↑ Brass, 2004 , sid. 25–33.
  38. ↑ 1 2 3 4 Dey, Pach, 1998 , sid. 473–484.
  39. ↑ Suk, 2013 .
  40. ↑ Živaljević, Vrećica, 1992 , sid. 309–318.
  41. ↑ Bárány, Furédi, 1987 , sid. 436–445.
  42. ↑ Károlyi, Solymosi, 2002 , sid. 577–583.

Litteratur