Rado graf

Rado-grafen, numrerad av Ackermann (1937) och Rado (1964) .

Inom det matematiska området grafteorin är Rado -grafen , Erdős–Rényi-grafen eller den slumpmässiga grafen en uträkneligt oändlig graf som kan konstrueras (med sannolikhet ett ) genom att välja oberoende slumpmässigt för varje par av dess hörn om de ska koppla ihop hörnen vid en kant. Namnen på denna graf hedrar Richard Rado , Paul Erdős och Alfréd Rényi , matematiker som studerade den i början av 1960-talet; det förekommer ännu tidigare i Wilhelm Ackermanns ( 1937 ) verk . Rado-grafen kan också konstrueras icke-slumpmässigt, genom att symmetrisera medlemskapsrelationen för de ärftligt ändliga mängderna, genom att tillämpa BIT-predikatet på de binära representationerna av de naturliga talen , eller som en oändlig Paley-graf som har kanter som förbinder par av primtal . kongruenta med 1 mod 4 som är kvadratiska rester modulo varandra.

Varje finit eller uträkneligt oändlig graf är en inducerad subgraf av Rado-grafen, och kan hittas som en inducerad subgraf av en girig algoritm som bygger upp subgrafen en hörn i taget. Rado-grafen är unikt definierad, bland räknebara grafer, av en förlängningsegenskap som garanterar korrektheten av denna algoritm: oavsett vilka hörn som redan har valts för att utgöra en del av den inducerade subgrafen, och oavsett vilket mönster av angränsningar som behövs för att utöka subgrafen med ytterligare en vertex, kommer det alltid att finnas en annan vertex med det mönstret av angränsningar som den giriga algoritmen kan välja.

Rado-grafen är mycket symmetrisk: all isomorfism av dess inducerade subgrafer kan utökas till en symmetri av hela grafen. De första ordningens logiska meningarna som är sanna för Rado-grafen är också sanna för nästan alla slumpmässiga finita grafer, och meningarna som är falska för Rado-grafen är också falska för nästan alla finita grafer. I modellteori utgör Rado-grafen ett exempel på en mättad modell av en ω-kategorisk och komplett teori .

Historia

Rado-grafen konstruerades först av Ackermann (1937) på två sätt, med hörn antingen de ärftligt ändliga mängderna eller de naturliga talen. (Strängt taget beskrev Ackermann en riktad graf , och Rado-grafen är den motsvarande oriktade grafen som ges genom att glömma riktningarna på kanterna.) Erdős & Rényi (1963) konstruerade Rado-grafen som den slumpmässiga grafen på ett räknat antal punkter. De bevisade att den har oändligt många automorfismer, och deras argument visar också att den är unik även om de inte nämnde detta explicit. Richard Rado ( 1964 ) återupptäckte Rado-grafen som en universell graf , och gav en explicit konstruktion av den med vertexuppsättning de naturliga talen. Rados konstruktion är i huvudsak likvärdig med en av Ackermanns konstruktioner.

Konstruktioner

Binära tal

Ackermann (1937) och Rado (1964) konstruerade Rado-grafen med hjälp av BIT-predikatet enligt följande. De identifierade grafens hörn med de naturliga talen 0, 1, 2, ... En kant förbinder hörn $x$ och $y$ i grafen (där $x< y$ ) närhelst ${\displaystyle x}:$ e biten i den binära representationen av $y$ inte är noll. Sålunda består till exempel grannarna till vertex 0 av alla udda numrerade hörn, eftersom talen vars 0:e bit inte är noll är exakt de udda talen. Vertex 1 har en mindre granne, vertex 0, eftersom 1 är udda och vertex 0 är kopplat till alla udda hörn. De större grannarna till vertex 1 är alla hörn med tal kongruenta med 2 eller 3 modulo 4, eftersom det är exakt talen med en bit som inte är noll vid index 1.

Slumpmässig graf

Rado-grafen uppstår nästan säkert i Erdős–Rényi-modellen av en slumpmässig graf på oräkneligt många hörn. Specifikt kan man bilda en oändlig graf genom att välja, oberoende och med sannolikhet 1/2 för varje par av hörn, om de två hörnen ska kopplas samman med en kant. Med sannolikhet 1 är den resulterande grafen isomorf med Rado-grafen. Denna konstruktion fungerar också om någon fast sannolikhet $p$ som inte är lika med 0 eller 1 används i stället för 1/2.

Detta resultat, visat av Paul Erdős och Alfréd Rényi ( 1963 ), motiverar den bestämda artikeln i det vanliga alternativa namnet " den slumpmässiga grafen" för Rado-grafen. Att upprepade gånger rita en finit graf från Erdős–Rényi-modellen kommer i allmänhet att leda till olika grafer; men när den tillämpas på en räkningsbart oändlig graf, producerar modellen nästan alltid samma oändliga graf.

För varje graf som genereras slumpmässigt på detta sätt kan komplementgrafen erhållas samtidigt genom att vända alla val: inklusive en kant när den första grafen inte inkluderade samma kant, och vice versa. Denna konstruktion av komplementgrafen är ett exempel på samma process att välja slumpmässigt och oberoende om varje kant ska inkluderas, så den genererar också (med sannolikhet 1) Rado-grafen. Därför är Rado-grafen en självkomplementär graf .

Andra konstruktioner

I en av Ackermanns ursprungliga konstruktioner från 1937 indexeras Rado-grafens hörn av de ärftligt ändliga mängderna, och det finns en kant mellan två hörn exakt när en av de motsvarande ändliga mängderna är en medlem av den andra. En liknande konstruktion kan baseras på Skolems paradox , det faktum att det finns en räknebar modell för den första ordningens teori om mängder. Man kan konstruera Rado-grafen från en sådan modell genom att skapa en vertex för varje uppsättning, med en kant som förbinder varje par av uppsättningar där en uppsättning i paret är en medlem av den andra.

Rado-grafen kan också bildas av en konstruktion som liknar den för Paley-grafer , som tar alla de primtal som är kongruenta med 1 modulo 4 som hörn av en graf och kopplar samman två hörn med en kant närhelst ett av de två talen är en kvadratisk rest modulo den andra. Genom kvadratisk ömsesidighet och begränsningen av hörnen till primtal som är kongruenta med 1 mod 4, är detta en symmetrisk relation , så det definierar en oriktad graf, som visar sig vara isomorf med Rado-grafen.

En annan konstruktion av Rado-grafen visar att det är en oändlig cirkulerande graf , med heltal som sina hörn och med en kant mellan varje två heltal vars avstånd (det absoluta värdet av deras skillnad) tillhör en viss mängd $S$ . För att konstruera Rado-grafen på detta sätt $S$ väljas slumpmässigt, eller genom att välja indikatorfunktionen för $S$ för att vara sammanlänkningen av alla finita binära sekvenser .

Rado-grafen kan också konstrueras som blockets skärningsdiagram för en oändlig blockdesign där antalet punkter och storleken på varje block är oändligt oändligt . Det kan också konstrueras som Fraïssé-gränsen för klassen av ändliga grafer.

Egenskaper

Förlängning

Utvidgningsegenskapen för Rado-grafen: för varje två disjunkta ändliga uppsättningar av hörn $U$ och $V$ , finns det en annan vertex $x$ kopplad till allt i $U$ , och till ingenting i $V$

Rado-grafen uppfyller följande förlängningsegenskap: för varje två disjunkta ändliga uppsättningar av hörn $U$ och $V$ finns det en vertex $x$ utanför båda uppsättningarna som är kopplade till alla hörn i $U$ , men har inga grannar i $V$ . Till exempel, med den binära numeriska definitionen av Rado-grafen, låt

$$x=2^{1+\max(U\cup V)}+\sum _{u\in U}2^{u}.$$

Sedan gör bitarna som inte är noll i den binära representationen av $x$ att den ligger intill allt i $U$ . Men $x$ har inga bitar som inte är noll i sin binära representation som motsvarar hörn i $V$ , och $x$ är så stor att den ${\displaystyle x}:$ e biten av varje element av $V$ är noll. Således $x$ inte intill någon vertex i $V$ .

Med den slumpmässiga grafdefinitionen av Rado-grafen har varje vertex utanför unionen av $U$ och $V$ sannolikheten $1/2^{|U|+|V|}$ för att uppfylla förlängningsegenskapen, oberoende av de andra hörnen. Eftersom det finns oändligt många hörn att välja mellan, var och en med samma ändliga sannolikhet för framgång, är sannolikheten en att det finns en vertex som uppfyller förlängningsegenskapen. Med Paley-grafdefinitionen, för alla uppsättningar $U$ och ${\displaystyle V} ,$ enligt den kinesiska restsatsen , talen som är kvadratiska rester modulo varje primtal i $U$ och icke-rester modulo varje primtal i $V$ en periodisk sekvens, så enligt Dirichlets sats om primtal i aritmetiska progressioner har denna talteoretiska graf egenskapen extension.

Inducerade subgrafer

Extensionsegenskapen kan användas för att bygga upp isomorfa kopior av valfri ändlig eller räkningsbar oändlig graf $G$ inom Rado-grafen, som inducerade subgrafer . För att göra det, ordna hörn av $G$ och lägg till hörn i samma ordning till en delkopia av $G$ i Rado-grafen. Vid varje steg kommer nästa vertex i $G$ att ligga intill någon uppsättning $U$ av hörn i $G$ som är tidigare i ordningen av hörnen och som inte gränsar till den återstående uppsättningen $V$ av tidigare hörn i $G$ . Genom tilläggsegenskapen kommer Rado-grafen också att ha en vertex $x$ som ligger intill alla hörn i den partiella kopian som motsvarar medlemmar av $U$ och inte intill alla hörn i den delkopia som motsvarar medlemmar av $V$ . Att lägga till $x$ till den partiella kopian av $G$ ger en större partiell kopia, med ytterligare en vertex.

Denna metod utgör grunden för ett bevis genom induktion , med 0-vertex-subgrafen som basfall, att varje ändlig eller räkningsbart oändlig graf är en inducerad subgraf av Rado-grafen.

Unikhet

Rado-grafen är, upp till grafisomorfism , den enda räknebara grafen med extensionsegenskapen. Låt till exempel $G$ och $H$ vara två räknebara grafer med tilläggsegenskapen, låt $G_{i}$ och $H_{i}$ vara isomorfa finita inducerade subgrafer av $G$ respektive $H$ , och låt $g_{i}$ och $h_{i}$ vara de första hörnen i en uppräkning av de hörn av $G$ respektive $H$ som inte tillhör $G_{i}$ och $H_{i}$ . Sedan, genom att applicera förlängningsegenskapen två gånger, kan man hitta isomorfa inducerade subgrafer $G_{i+1}$ och $H_{i+1}$ inkluderar $\ displaystyle g_{i}}$ och $h_{i}$ tillsammans med alla hörn i de föregående subgraferna. Genom att upprepa denna process kan man bygga upp en sekvens av isomorfismer mellan inducerade subgrafer som så småningom inkluderar varje vertex i $G$ och $H$ . Således, med fram-och-tillbaka-metoden måste $G$ och $H} vara isomorfa.$ displaystyle Eftersom graferna som konstrueras av den slumpmässiga grafkonstruktionen, binära talkonstruktionen och Paley-grafkonstruktionen alla är räknebara grafer med förlängningsegenskapen, visar detta argument att de alla är isomorfa till varandra.

Symmetri

Genom att tillämpa fram-och-tillbaka-konstruktionen på två isomorfa ändliga subgrafer av Rado-grafen utökas deras isomorfism till en automorfism av hela Rado-grafen. Det faktum att varje isomorfism av finita subgrafer sträcker sig till en automorfism av hela grafen uttrycks genom att säga att Rado-grafen är ultrahomogen . I synnerhet finns det en automorfism som tar alla ordnade par av angränsande hörn till vilket annat sådant ordnat par, så Rado-grafen är en symmetrisk graf .

Automorfismgruppen i Rado-grafen är en enkel grupp , vars antal element är kontinuumets kardinalitet . Varje undergrupp av denna grupp vars index är mindre än kontinuumets kardinalitet kan läggas in mellan den punktvisa stabilisatorn och stabilisatorn för en ändlig uppsättning av hörn.

Konstruktionen av Rado-grafen som en oändlig cirkulerande graf visar att dess symmetrigrupp inkluderar automorfismer som genererar en transitiv oändlig cyklisk grupp . Skillnadsmängden för denna konstruktion (mängden avstånd i heltal mellan intilliggande hörn) kan begränsas till att inkludera skillnaden 1, utan att påverka riktigheten av denna konstruktion, av vilket det följer att Rado-grafen innehåller en oändlig Hamilton-bana vars symmetrier är en undergrupp av symmetrierna i hela grafen.

Robusthet mot ändliga förändringar

Om en graf $G$ bildas från Rado-grafen genom att radera ett ändligt antal kanter eller hörn, eller lägga till ett ändligt antal kanter, påverkar ändringen inte förlängningsegenskapen för grafen. För alla par av uppsättningar $U$ och $V$ är det fortfarande möjligt att hitta en vertex i den modifierade grafen som ligger intill allt i $U$ och inte intill allt i ${\ displaystyle V}$ , genom att lägga till de modifierade delarna av $G$ till $V$ och tillämpa förlängningsegenskapen i den omodifierade Rado-grafen. Därför resulterar varje ändlig modifiering av denna typ i en graf som är isomorf till Rado-grafen.

Dela

För varje uppdelning av hörn av Rado-grafen i två uppsättningar $A$ och ${\displaystyle B},$ eller mer allmänt för en partition i ändligt många delmängder, minst en av subgraferna inducerad av en av partitionerna set är isomorfa till hela Rado-grafen. Cameron (2001) ger följande korta bevis: om ingen av delarna inducerar en subgraf som är isomorf till Rado-grafen, saknar de alla extensionsegenskapen, och man kan hitta par av uppsättningar U i {\displaystyle U_{ $}$ och $V_{i}$ som inte kan utökas inom varje subgraf. Men då skulle föreningen av mängderna $U_{i}$ och föreningen av mängderna $V_{i}$ bilda en mängd som inte kunde utökas i hela grafen, vilket motsäger Rado-grafens förlängningsegenskap. Denna egenskap att vara isomorf till en av de inducerade subgraferna i vilken partition som helst hålls av endast tre oändliga oriktade grafer som kan räknas upp: Rado-grafen, den fullständiga grafen och den tomma grafen . Bonato, Cameron & Delić (2000) och Diestel et al. (2007) undersöker oändliga riktade grafer med samma partitionsegenskap; alla bildas genom att välja orienteringar för kanterna på hela grafen eller Rado-grafen.

Ett relaterat resultat gäller kantpartitioner istället för vertexpartitioner: för varje partition av kanterna på Rado-grafen i ändligt många uppsättningar, finns det en subgraf som är isomorf till hela Rado-grafen som använder högst två av färgerna. Det kanske inte nödvändigtvis finns en isomorf subgraf som bara använder en färg på kanterna.

Modellteori och 0-1 lagar

Fagin (1976) använde Rado-grafen för att bevisa en noll-ett-lag för första ordningens påståenden i grafernas logik . När ett logiskt påstående av denna typ är sant eller falskt för Rado-grafen, är det också sant eller falskt (respektive) för nästan alla finita grafer.

Första ordningens fastigheter

Grafernas första ordningens språk är samlingen av välformade meningar i matematisk logik bildade av variabler som representerar grafernas hörn, universella och existentiella kvantifierare , logiska bindemedel och predikat för jämlikhet och närliggande hörn. Till exempel kan villkoret att en graf inte har några isolerade hörn uttryckas av meningen

$$\forall u:\exists v:u\sim v$$

där $\sim$ symbolen indikerar närliggande relation mellan två hörn. Denna mening $S$ är sann för vissa grafer, och falsk för andra; en graf $G$ sägs modellera $S$ , skriven $G\models S$ , om $S$ är sant för hörn och närliggande relation till ${ \displaystyle G}$ .

Förlängningsegenskapen för Rado-grafen kan uttryckas av en samling första ordningens meningar ${\displaystyle E_{i,j}} ,$ som anger att för varje val av $i$ hörn i en mängd $A$ och $j$ hörn i en mängd ${\displaystyle B} ,$ alla distinkta, det finns en vertex intill allt i $A$ och icke intill allt i $B$ . Till exempel $E_{1,1}$ skrivas som

$$\forall a:\forall b:a\neq b\rightarrow \exists c:c\neq a\wedge c\neq b\wedge c\sim a\wedge \lnot (c\sim b).$$

Fullständighet

Gaifman (1964) bevisade att meningarna ${\displaystyle E_{i,j}} ,$ tillsammans med ytterligare meningar som anger att adjacensrelationen är symmetrisk och antireflexiv (det vill säga att en graf som modellerar dessa meningar är oriktad och har inga självslingor), är axiomen för en komplett teori . Detta betyder att för varje första ordningens mening $S$ kan exakt en av $S$ och dess negation bevisas från dessa axiom. Eftersom Rado-grafen modellerar förlängningsaxiomen, modellerar den alla meningar i denna teori.

kallas en teori som bara har en modell (upp till isomorfism) med en given oändlig kardinalitet $\lambda$$\lambda$ -categorical . Det faktum att Rado-grafen är den unika räknebara grafen med extensionsegenskapen innebär att den också är den unika räknebara modellen för dess teori. Denna unika egenskap hos Rado-grafen kan uttryckas genom att säga att teorin för Rado-grafen är ω-kategorisk . Łoś och Vaught bevisade 1954 att när en teori är $\lambda$ –kategorisk (för vissa oändliga kardinal $\lambda$ ) och dessutom inte har några ändliga modeller, då måste teorin vara komplett. Därför följer Gaifmans teorem att teorin om Rado-grafen är komplett från det unika med Rado-grafen genom Łoś–Vaught-testet .

Finita grafer och beräkningskomplexitet

Som Fagin (1976) bevisade, är de första ordningens meningar som kan bevisas från förlängningsaxiomen och modellerade av Rado-grafen exakt de meningar som är sanna för nästan alla slumpmässiga finita grafer. Detta betyder att om man väljer en $n$ -vertexgraf likformigt slumpmässigt bland alla grafer på $n$ märkta hörn, så närmar sig sannolikheten att en sådan mening är sann för den valda grafen en i gräns när $n$ närmar sig oändligheten. Symmetriskt är de meningar som inte är modellerade av Rado-grafen falska för nästan alla slumpmässiga ändliga grafer. Det följer att varje första ordningens mening är antingen nästan alltid sann eller nästan alltid falsk för slumpmässiga finita grafer, och dessa två möjligheter kan särskiljas genom att avgöra om Rado-grafen modellerar meningen. Fagins bevis använder kompakthetssatsen . Baserat på denna likvärdighet har teorin om meningar som modellerats av Rado-grafen kallats "teorin för den slumpmässiga grafen" eller "den nästan säkra teorin om grafer".

På grund av denna 0-1-lag är det möjligt att testa om någon speciell första ordningens mening är modellerad av Rado-grafen under en begränsad tid, genom att välja ett tillräckligt stort värde på n {\displaystyle n} $räkna$ antalet av $n$ -vertexgrafer som modellerar meningen. Men här är "tillräckligt stor" åtminstone exponentiell i meningens storlek. Till exempel antyder tilläggsaxiomet $E_{k,0}$ förekomsten av en $\displaystyle (k+1)}$ -vertex klick , men en klick av den storleken finns med hög sannolikhet endast i slumpmässiga grafer av storleken exponentiell i $k$ . Det är osannolikt att avgöra om Rado-grafen modellerar en given mening kan göras snabbare än exponentiell tid, eftersom problemet är PSPACE-komplett .

Mättad modell

Ur modellteoretisk synvinkel är Rado-grafen ett exempel på en mättad modell . Detta är bara en logisk formulering av egenskapen att Rado-grafen innehåller alla finita grafer som inducerade subgrafer.

I detta sammanhang är en typ en uppsättning variabler tillsammans med en samling begränsningar för värdena för några eller alla predikaten som bestäms av dessa variabler; en komplett typ är en typ som begränsar alla predikat som bestäms av dess variabler. I teorin om grafer representerar variablerna hörn och predikaten är närliggande punkter mellan hörn, så en komplett typ anger om en kant finns eller saknas mellan varje par av hörn som representeras av de givna variablerna. Det vill säga, en komplett typ specificerar subgrafen som en viss uppsättning vertexvariabler inducerar.

En mättad modell är en modell som realiserar alla typer som har ett antal variabler som högst motsvarar modellens kardinalitet. Rado-grafen har inducerat subgrafer av alla ändliga eller uträkneligt oändliga typer, så den är mättad.

Relaterade begrepp

Även om Rado-grafen är universell för inducerade subgrafer, är den inte universell för isometriska inbäddningar av grafer, där en isometrisk inbäddning är en grafisomorfism som bevarar avståndet . Rado-grafen har en diameter två, så alla grafer med större diameter bäddas inte in isometriskt i den. Moss ( 1989 , 1991 ) har beskrivit en familj av universella grafer för isometrisk inbäddning, en för varje möjlig ändlig grafdiameter; grafen i hans familj med diameter två är Rado-grafen.

Henson -graferna är räknebara grafer (en för varje positivt heltal $i$ ) som inte innehåller en $i$ -vertex clique , och är universella för $i$ -clique-fria grafer. De kan konstrueras som inducerade subgrafer av Rado-grafen. Rado-grafen, Henson-graferna och deras komplement, osammanhängande sammanslutningar av uträkneligt oändliga klickar och deras komplement, och oändliga osammanhängande sammanslutningar av isomorfa finita klickar och deras komplement är de enda möjliga, räknat oändliga homogena graferna .

Rado-grafens universalitetsegenskap kan utökas till kantfärgade grafer; det vill säga grafer där kanterna har tilldelats olika färgklasser, men utan det vanliga kantfärgningskravet att varje färgklass bildar en matchande . För varje ändligt eller räkningsbart oändligt antal färger $\chi$ , finns det en unik räkneligt oändlig $\chi$ -kantfärgad graf $G_{\chi }$ så att varje partiell isomorfism av en $\chi$ -kantfärgad finit graf kan utökas till en fullständig isomorfism. Med denna notation är Rado-grafen bara $G_{1}$ . Truss (1985) undersöker automorfismgrupperna i denna mer generella familj av grafer.

Det följer av de klassiska modellteoretiska övervägandena för att konstruera en mättad modell att under kontinuumhypotesen CH finns det en universell graf med kontinuum många hörn. Naturligtvis, under CH är kontinuumet lika med ${\displaystyle \aleph _{1}} ,$ den första oräkneliga kardinalen . Shelah ( 1984 , 1990 ) använder forcering för att undersöka universella grafer med $\aleph _{1}$ många hörn och visar att även i frånvaro av CH kan det finnas en universell graf med storlek $\aleph _{1}$ . Han undersöker också analoga frågor för högre kardinaliteter.

Anteckningar

•   Ackermann, Wilhelm (1937), "Die Widerspruchsfreiheit der allgemeinen Mengenlehre", Mathematische Annalen , 114 (1): 305–315, doi : 10.1007/BF01594179 , S2CID 120576556
•   Bonato, Anthony; Cameron, Peter ; Delić, Dejan (2000), "Tournaments and orders with the pigeonhole property", Canadian Mathematical Bulletin , 43 (4): 397–405, doi : 10.4153/CMB-2000-047-6 , MR 1793941 .
•    Cameron, Peter J. (1990), Oligomorphic permutation groups , London Mathematical Society Lecture Note Series, vol. 152, Cambridge: Cambridge University Press, ISBN 0-521-38836-8 , MR 1066691 .
•   Cameron, Peter J. (1997), "The random graph", The mathematics of Paul Erdős, II , Algorithms and Combinatorics , vol. 14, Berlin: Springer, s. 333–351, arXiv : 1301.7544 , Bibcode : 2013arXiv1301.7544C , MR 1425227 .
•   Cameron, Peter J. (2001), "The random graph revisited" (PDF) , European Congress of Mathematics , Vol. I (Barcelona, ​​2000) , Progr. Math., vol. 201, Basel: Birkhäuser, s. 267–274, doi : 10.1007/978-3-0348-8268-2_15 , MR 1905324 .
•   Diestel, Reinhard; Ledare, Imre ; Scott, Alex; Thomassé, Stéphan (2007), "Partitions and orientations of the Rado graph", Transactions of the American Mathematical Society , 359 (5): 2395–2405, doi : 10.1090/S0002-9947-06-04026-4 , 66MR 6 7 .
•   Enderton, Herbert B. (1972), A matematical introduction to logic , Academic Press, New York-London, MR 0337470 .
•   Erdős, P. ; Rényi, A. (1963), "Asymmetric graphs", Acta Mathematica Academiae Scientiarum Hungaricae , 14 (3–4): 295–315, doi : 10.1007/BF01895716 , MR 0156334 .
•     Fagin, Ronald (1976), "Probabilities on finite models" (PDF) , The Journal of Symbolic Logic , 41 (1): 50–58, doi : 10.1017/s0022481200051756 , JSTOR 2272945 , S 4272945 , 6 MR 3104 5 .
•   Gaifman, Haim (1964), "Concerning measurements in first order calculi", Israel Journal of Mathematics , 2 : 1–18, doi : 10.1007/BF02759729 , MR 0175755 .
• Grandjean, Étienne (1983), "Complexity of the first-order theory of nästan alla finita strukturer", Information and Control , 57 (2–3): 180–204, doi : 10.1016/S0019-9958(83)80043-6 MR 0742707 .   _
•   Henson, C. Ward (1971), "A family of countable homogeneous graphs", Pacific Journal of Mathematics , 38 : 69–83, doi : 10.2140/pjm.1971.38.69 , MR 0304242 .
•    Hodges, Wilfrid (1997), A Shorter Model Theory , Cambridge University Press, ISBN 0-521-58713-1 , OCLC 468298248
•    Horsley, Daniel; Pike, David A.; Sanaei, Asiyeh (2011), "Existential closure of block intersection graphs of infinite designs having infinite block size", Journal of Combinatorial Designs , 19 (4): 317–327, doi : 10.1002 /jcd.20283 , 89ID 7028 , 82ID 7028 , 89ID 7028 , 89ID 7028 .
•    Lachlan, AH; Woodrow, Robert E. (1980), "Countable ultrahomogeneous undirected graphs", Transactions of the American Mathematical Society , 262 (1): 51–94, doi : 10.2307/1999974 , JSTOR 1999974 , MR 0583847 .
•   Lascar, D. (2002), "Automorphism groups of saturated structures; a review", Proceedings of the International Congress of Mathematicians, Vol. II (Peking, 2002) (PDF) , högre utgåva. Press, Beijing, s. 25–33, arXiv : math/0304205 , Bibcode : 2003math......4205L , MR 1957017 .
•   Łoś, J. (1954), "Om kategoriseringen i kraft av elementära deduktiva system och några relaterade problem", Colloquium Math. , 3 : 58-62, doi : 10,4064/cm-3-1-58-62 , MR 0061561 .
•    Marker, David (2002), Model theory , Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, ISBN 0-387-98760-6 , MR 1924282 .
•   Moss, Lawrence S. (1989), "Existence and nonexistence of universal graphs", Polska Akademia Nauk. Fundamenta Mathematicae , 133 (1): 25–37, doi : 10.4064/fm-133-1-25-37 , MR 1059159 .
•   Moss, Lawrence S. (1991), "The universal graphs of fixed finite diameter", Grafteori, kombinatorik och tillämpningar. Vol. 2 (Kalamazoo, MI, 1988) , Wiley-Intersci. Publ., New York: Wiley, s. 923–937, MR 1170834 .
•    Pouzet, Maurice; Sauer, Norbert (1996), "Edge partitions of the Rado graph", Combinatorica , 16 (4): 505–520, doi : 10.1007/BF01271269 , MR 1433638 , S2CID 206793062 .
• Rado, Richard (1964), "Universella grafer och universella funktioner" (PDF) , Acta Arith. , 9 (4): 331–340, doi : 10.4064/aa-9-4-331-340 .
•   Shelah, Saharon (1984), "On universal graphs without instances of CH", Annals of Pure and Applied Logic , 26 (1): 75–87, doi : 10.1016/0168-0072(84)90042-3 , MR 0739914 .
•   Shelah, Saharon (1990), "Universal graphs without instances of CH: revisited", Israel Journal of Mathematics , 70 (1): 69–81, doi : 10.1007/BF02807219 , MR 1057268 .
•    Spencer, Joel (2001), The Strange Logic of Random Graphs , Algorithms and Combinatorics, vol. 22, Springer-Verlag, Berlin, doi : 10.1007/978-3-662-04538-1 , ISBN 3-540-41654-4 , MR 1847951 .
•    Truss, JK (1985), "The group of the countable universal graph", Mathematical Proceedings of the Cambridge Philosophical Society , 98 (2): 213–245, Bibcode : 1985MPCPS..98..213T , doi : 10.100506/030506/04017 / 80000000000000000 MR 0795890 , S2CID 122772888 .
•   Vaught, Robert L. (1954), "Applications to the Löwenheim-Skolem-Tarski theorem to problems of completeness and decidability", Indagationes Mathematicae , 16 : 467–472, doi : 10.1016/S1385-7258(54) 50 , MR 0063993 .