Greve Rado

Rado-grafen  är den enda (upp till isomorfism ) räknebara grafen R så att, för varje finit graf G och dess vertex v , varje inbäddning av G −  v i R som en genererad subgraf kan utökas till en inbäddning av G i R . Som ett resultat innehåller Rado-grafen alla ändliga och uträkneligt oändliga grafer som subgrafer. Greve Rado är också känd under namnen Random Count och Count Erdős-Renyi .

Historik

Radografen konstruerades av Wilhelm Ackermann och återupptäcktes flera gånger, i synnerhet av Richard Rado [1] , men symmetriegenskaperna hos denna graf konstruerad på ett annat sätt övervägdes tidigare av Pal Erdős och Alfred Rényi [2] .

Ett liknande föremål i metrisk geometri , det så kallade Urysohn-utrymmet , var känt mycket tidigare.

Byggnad

Rado tog icke-negativa heltal som hörn på grafen. En kant förbinder hörn x och y vid ( x  <  y ) om den x -te siffran i den binära representationen av y är icke-noll.

Till exempel består mängden av alla grannar till vertex 0 av udda hörn, medan grannarna till vertex 1 är vertex 0 (den enda vertex vars siffra i den binära representationen av 1 är icke-noll) och alla hörn modulo 4 som är kongruenta till 2 och 3.

Hitta isomorfa subgrafer

Rado-grafen uppfyller följande töjbarhetsvillkor: för alla disjunkta uppsättningar av hörn U och V finns det en vertex x associerad med alla hörn i U och ingen i V . Till exempel kan du ta

Då ligger bitarna som inte är noll i den binära representationen av x intill alla hörn av U. Emellertid har x inga bitar som inte är noll som motsvarar hörnen på V och x är tillräckligt stor för att den x -te biten av något element i V är noll. X har alltså inga angränsande hörn i V .

Denna idé att hitta hörn som gränsar till alla hörn i en delmängd och ingen av en annan kan användas för att konstruera en isomorf kopia av vilken ändlig eller oändlig räknebar graf G som helst och lägga till den ena hörnen efter den andra i följd. Låt Gi  vara en subgraf av G som genereras av dess första i hörn och anta att G i redan har hittats som den inducerade grafen för vertexdelmängden S i Rado-grafen. Låt v  vara nästa hörn i G och låt U  vara mängden grannar till v i G i . Låt V  vara en uppsättning av hörn som inte är grannar till v i grafen G i . Om x  är en vertex av Rado-grafen intill alla hörn av U och inte intill alla hörn av V , så genererar S  ∪ { x } en subgraf som är isomorf till G i  + 1 .

Genom induktion, med utgångspunkt från den tomma grafen, får vi att alla ändliga eller oändliga räknebara grafer genereras av en Rado-graf.

Unikhet

Rado-grafen, upp till isomorfism, är den enda räknebara grafen som har töjbarhetsegenskapen. Låt G och H  vara två grafer med denna egenskap. Låt Gi och H i  vara två isomorfa genererade subgrafer i G respektive H . Låt g i och h i  vara de första hörnen i numreringsordningen i graferna G respektive H , som inte tillhör G i och H i . Sedan, genom att applicera töjbarhetsegenskapen två gånger, kan man hitta isomorfa genererade subgrafer Gi +  1 och H i  + 1 som inkluderar gi och h i tillsammans med alla hörn i de föregående subgraferna . Genom att upprepa denna process kan man konstruera en sekvens av isomorfismer mellan de genererade subgraferna som så småningom innehåller alla hörn G och H . Således, efter fram och tillbaka metoden , måste G och H vara isomorfa [3] .

Genom att tillämpa samma konstruktion av två isomorfa subgrafer av Rado-grafen kan det visas att Rado -grafen är ultrahomogen  - varje isomorfism mellan två genererade subgrafer av Rado-grafen kan utökas till en automorfism av hela Rado-grafen [3] . I synnerhet finns det en automorfism som tar ett ordnat par av angränsande till vilket annat sådant par, så att Rado-grafen är en symmetrisk graf .

Motståndskraft mot ändliga förändringar

Om grafen G erhålls från Rado-grafen genom att ta bort ett eventuellt ändligt antal kanter eller hörn eller genom att lägga till ett ändligt antal kanter, påverkar ändringarna inte grafens töjbarhetsegenskap - för något par av uppsättningar U och V , förmågan att hitta en vertex i den modifierade grafen som ligger intill alla hörn från U och inte intill någon vertex av V , kvarstår. Vi lägger helt enkelt till de modifierade delarna av grafen G till V och tillämpar utvidgningsegenskapen i den omodifierade Rado-grafen. Sålunda leder varje ändlig förändring av detta slag till en graf som är isomorf mot Rado-grafen.

Partitionsegenskap

För varje partition av vertexuppsättningen av en Rado-graf i två delmängder A och B , eller en partition i vilket ändligt antal delmängder som helst, kommer åtminstone en av de genererade subgraferna att vara isomorf till själva Radografen.

Cameron [3] gav följande korta bevis för detta påstående: Om ingen av de genererade delarna är isomorf till Rado-grafen, förlorar de alla töjbarhetsegenskapen, och därför kan man i varje subgraf hitta ett par uppsättningar U i och V i som inte är utdragbara. Men då bildar föreningen av mängder U i och föreningen V i två mängder som inte kan förlängas i en komplett graf, vilket motsäger Rado-grafens töjbarhetsegenskap.

Endast tre räknebara oändliga oriktade grafer har egenskapen att förbli isomorfa till en av de genererade subgraferna efter division - Rado-grafen, den fullständiga grafen och den tomma grafen [4] [5] . Bonato och Cameron [6] samt Distel et al [5] studerade oändliga riktade grafer med samma divisionsegenskap. Det visade sig att alla erhålls genom att välja orienteringen av bågar i en komplett graf eller en Rado-graf.

Ett liknande resultat är sant för kantpartitioner - för varje uppdelning av kanterna på en Rado-graf i ett ändligt antal uppsättningar finns det en subgraf som är isomorf till hela Rado-grafen med högst två färger. En graf som bara använder en kantfärg kanske inte existerar [7] .

Andra byggen

Det är möjligt att bilda en oändlig graf i Erdős-Rényi-modellen genom att slumpmässigt välja oberoende med sannolikhet 1/2 för varje par av hörn om man ska koppla ihop två hörn med en kant eller inte. Med sannolikhet 1 har den resulterande grafen töjbarhetsegenskapen och är därför isomorf till Rado-grafen.

Samma konstruktion fungerar om vi istället för 1/2 tar vilken fast sannolikhet p som helst som inte är lika med 0 eller 1. Detta resultat, bevisat av Erdős och Renyi 1963 [2] [K 1] , motiverar användningen av den bestämda artikeln i alternativt namn " den slumpmässiga grafen » (slumpmässig graf) för Rado-grafen - för ändliga grafer resulterar användning av ritmodellen Erdős-Rényi ofta i olika grafer, medan en räknebar oändlig graf nästan alltid resulterar i samma. Eftersom det är möjligt att få samma Rado-graf efter att ha omvänt alla val, är Rado-grafen självkomplementär .

Som Cameron skriver [3] , kan Rado-grafen erhållas med metoder liknande de för att konstruera Paley-grafer . Ta som hörn alla primtal som inte ger en rest av 1 när de divideras med 4, och koppla två hörn med en kant om ett av talen är en kvadratisk rest modulo det andra (enligt kvadratisk reciprocitet och uteslutningen av primtal som ge en återstod av 1 när de divideras med 4, denna relation är symmetrisk , så vi får en oriktad graf). Nu, för alla mängder U och V , enligt den kinesiska restsatsen , bildar tal som är kvadratiskt kongruenta moduloprimtal från U och inte jämförbara med primtal från V en periodisk sekvens, så genom Dirichlets sats om primtal i aritmetisk progression denna teoretiska talgraf har utvidgningsegenskapen.

Variationer och generaliseringar

Även om Rado-grafen är universell för inducerade subgrafer, är den inte universell för isometriska grafinbäddningar – Rado-grafen har en diameter på två, och alla grafer med större diameter kan inte bäddas in isometriskt i den. Moss [8] [9] studerade universella grafer för isometrisk inbäddning. Han hittade en familj av universella grafer, en för varje möjlig ändlig grafdiameter. En graf från denna familj med diameter två är en Rado-graf. För metriska utrymmen är den direkta analogen Urysohn-utrymmet .

Rado-grafens universalitetsegenskap kan utökas till linjefärgade grafer. Det vill säga grafer där kanterna tillhör olika färgklasser, men det finns inget vanligt kantfärgningskrav på att varje färg bildar en matchande . För vilket ändligt eller räkningsbart oändligt antal färger χ som helst, finns det en unik räkneligt oändlig graf G χ med kantfärgning i χ-färger så att varje partiell isomorfism av en ändlig graf med färgning i χ-färger kan utökas till en fullständig isomorfism. I denna notation är Rado-grafen G 1 . Trouss [10] studerade automorfismen hos grupper av denna mer allmänna graffamilj.

Ur en teoretisk synvinkel är Rado-grafen ett exempel på en mättad modell .

Shela [11] [12] studerade universella grafer med ett oräkneligt antal hörn.

Se även

Kommentarer

  1. ↑ Erdős och Renyi använde töjbarhetsegenskapen för en graf som erhållits på detta sätt för att visa att den har många automorfismer, men de övervägde inte andra egenskaper som följer av töjbarhet. De märkte också att utvidgningsegenskapen fortsätter att existera i vissa slumpmässiga urvalssekvenser när olika kanter har olika sannolikheter att inkluderas.

Litteratur

  1. ↑ Rado Richard. Universella grafer och universella funktioner // Acta Arith .. - 1964. - T. 9 . — S. 331–340 .
  2. ↑ 1 2 Paul Erdős, Alfred Rényi. Asymmetriska grafer // Acta Mathematica Academiae Scientiarum Hungaricae. - 1963. - T. 14 . — S. 295–315 . - doi : 10.1007/BF01895716 .
  3. ↑ 1 2 3 4 Peter J. Cameron. European Congress of Mathematics, Vol. I (Barcelona, ​​2000). - Basel: Birkhäuser, 2001. - T. 201 . — S. 267–274 .
  4. ↑ Peter J. Cameron. Oligomorfa permutationsgrupper. - Cambridge: Cambridge University Press, 1990. - V. 152 . - S. viii + 160 . — ISBN 0-521-38836-8 .
  5. ↑ 1 2 Reinhard Diestel, Imre Leader, Alex Scott, Stéphan Thomassé. Partitioner och orienteringar av Rado-grafen // Transactions of the American Mathematical Society. - 2007. - T. 359 , nr. 5 . — S. 2395–2405 (elektronisk) . - doi : 10.1090/S0002-9947-06-04086-4 .
  6. ↑ Anthony Bonato, Peter Cameron, Dejan Delic. Turneringar och beställningar med duvhålsegenskapen // Canadian Mathematical Bulletin. - 2000. - T. 43 , nr. 4 . — S. 397–405 . - doi : 10.4153/CMB-2000-047-6 . Arkiverad från originalet den 12 juni 2008.
  7. ↑ Maurice Pouzet, Norbert Sauer. Kantpartitioner av Rado-grafen  // Combinatorica. - 1996. - T. 16 , nr. 4 . — S. 505–520 . - doi : 10.1007/BF01271269 .
  8. ↑ Mossa. Existens och icke-existens av universella grafer // Polska Akademia Nauk. Fundamenta Mathematicae. - 1989. - T. 133 , nr. 1 . — S. 25–37 .
  9. ↑ Mossa. Grafteori, kombinatorier och tillämpningar. Vol. 2 (Kalamazoo, MI, 1988). - New York: Wiley, 1991. - S. 923-937 .
  10. ↑ Fackverk. Gruppen av den countable universella grafen // Mathematical Proceedings of the Cambridge Philosophical Society. - 1985. - T. 98 , nr. 2 . — S. 213–245 . - doi : 10.1017/S0305004100063428 .
  11. ↑ Shelah. På universella grafer utan förekomster av CH // Annals of Pure and Applied Logic. - 1984. - T. 26 , nr. 1 . — s. 75–87 . - doi : 10.1016/0168-0072(84)90042-3 .
  12. ↑ Shelah. Universella grafer utan förekomster av CH: revisited // Israel Journal of Mathematics. - 1990. - T. 70 , nr. 1 . — s. 69–81 . - doi : 10.1007/BF02807219 .