Grafico Rado

In matematica , e più precisamente nella teoria dei grafi , il grafo di Rado , chiamato anche grafo di Erdős-Rényi o grafo casuale , è un grafo infinito numerabile studiato nei primi anni '60 da Richard Rado , Paul Erdős e Alfréd Rényi , caratterizzato dalla proprietà di estensione , il che implica che contiene (come sottografo ) qualsiasi grafo finito o numerabile.

Ne esistono diverse costruzioni; si tratta in particolare ( quasi sicuramente ) del grafo casuale ottenuto scegliendo a caso per ogni coppia di vertici se sono connessi o meno.

Storico

Il grafo Rado fu costruito da Wilhelm Ackermann nel 1937 dagli insiemi ereditari finiti  (in) (più esattamente, descrisse un grafo diretto da cui si ottiene il grafo Rado rimuovendo l'orientamento). Nel loro lavoro sui grafi casuali , Paul Erdős e Alfréd Rényi lo hanno costruito come un grafo casuale infinito e hanno mostrato che ha un numero infinito di automorfismi con un argomento che permetterebbe anche di dimostrarne l'unicità. Richard Rado lo riscoprì come grafo universale e diede una costruzione deterministica sostanzialmente equivalente a quella di Ackermann.

costruzioni

Scrittura binaria

Ackermann e Rado hanno fornito una costruzione esplicita utilizzando il predicato BIT  (en) . Identificando i vertici del grafo e gli interi naturali 0, 1, 2, ..., un arco collega i vertici x e y (con x  <  y ) se e solo se il bit di rango x della rappresentazione binaria di y è uguale a 1 Ad esempio, esiste un collegamento tra x = 2 e y = 4 = 100 2 , ma non tra x = 1 e y .

Grafici casuali

Il grafo di Rado appare quasi sicuramente quando applichiamo il modello di grafo casuale sviluppato da Erdős e Rény a un insieme numerabile di vertici. Più precisamente, scegliendo indipendentemente per ogni coppia di vertici con probabilità p (0 < p <1) se questi vertici sono collegati da un arco, il grafo risultante è quasi sicuramente (cioè con probabilità 1) isomorfo al grafo di Rado; è questo risultato che giustifica l'articolo definito nell'espressione "  il grafico casuale" che talvolta lo designa.

Un grafo isomorfo al grafo complementare al grafo Rado può essere ottenuto (quasi sicuramente) con la stessa costruzione scegliendo gli archi con probabilità 1– p , il che mostra che il grafo Rado è autocomplementare .

Altre costruzioni

La proprietà di estensione caratterizza il grafo Rado, e permette di mostrare che molte costruzioni sono ad esso isomorfe.

Nelle costruzioni di Ackermann del 1937, i vertici del grafo di Rado sono gli insiemi ereditari finiti (cioè gli insiemi finiti i cui elementi sono essi stessi ereditariamente finiti) e un arco collega due vertici quando uno di essi è parte dell'altro.

Un'altra costruzione del grafico Rado è analoga a quella dei grafici Paley . I vertici sono i numeri primi della forma 4 n + 1, e un arco li collega se uno dei due è residuo quadratico modulo l'altro (questa relazione è simmetrica secondo la legge di reciprocità quadratica ).

Può anche essere costruito come il grafico di intersezione di un sistema di blocchi  (en) infinito in cui ogni blocco è infinito (numerabile).

Proprietà

Proprietà di estensione

Il grafo di Rado soddisfa la seguente proprietà di estensione : per ogni coppia di insiemi di vertici finiti disgiunti U e V , esiste un vertice x che non appartiene né a U né a V , e connesso a tutti i vertici di U , ma nessuno di quelli di V  ; questa proprietà caratterizza questo grafico, come mostrato di seguito .

La definizione del grafo per rappresentazione binaria permette una dimostrazione costruttiva, ponendo

 :

x è maggiore di tutti gli elementi costruttivi di U e V , adiacenti a tutti gli elementi U , e poiché U e V sono disgiunti, x è adiacente a qualsiasi parte di V .

La costruzione come grafo casuale dà a ciascun vertice non in U o V una probabilità p | U | (1- p ) | V | soddisfare la proprietà di estensione, indipendentemente dagli altri vertici; poiché ci sono un'infinità di tali vette, ce n'è quasi sicuramente una che soddisfa la proprietà.

Sottografi

Per ogni grafo numerabile finito o infinito G , la proprietà di estensione per costruire un sottografo del grafo Rado isomorfo a G . La dimostrazione si fa per induzione sui vertici di G (assunto indicizzato dagli interi): supponendo che si costruisca un isomorfismo per i primi n vertici, si aggiunge un nuovo vertice scegliendo dal grafo di Rado un vertice avente esattamente gli stessi collegamenti con i vertici già costruiti i corrispondenti vertici in G . Per questo motivo si dice talvolta che il grafo di Rado sia un grafo universale , ma in realtà è una nozione più debole di quella di problema universale , definito dalla teoria delle categorie .

Unicità

Il grafo di Rado è, fino all'isomorfismo , l'unico grafo numerabile avente la proprietà di estensione. Infatti, se G e H sono due grafi aventi questa proprietà, ciascuno dei due è isomorfo a un sottografo dell'altro; specificando la costruzione di questi sottografi, è possibile ottenere per induzione un isomorfismo tra G e H utilizzando il metodo avanti e indietro (analogamente alla dimostrazione del teorema di Cantor-Bernstein ).

simmetrie

Partendo da due sottografi finiti e isomorfi del grafo Rado, la costruzione precedente permette di estendere questo isomorfismo in un automorfismo dell'intero grafo; diciamo che il grafico Rado è ultraomogeneo . In particolare, esiste un automorfismo che invia due archi qualsiasi uno sull'altro, e il grafo di Rado è quindi un grafo simmetrico . Il gruppo di automorfismi del grafo Rado è un gruppo semplice con la potenza del continuo .

Spartito

Qualsiasi partizione finita dei vertici del grafo Rado induce almeno un sottografo isomorfo all'intero grafo. Cameron 2001 ne dà una breve dimostrazione, ottenuta incollando tra loro sottoinsiemi di ciascun sottografo indotto che non verificherebbero la proprietà di estensione. Solo tre grafi non orientati numerabili hanno questa proprietà: il grafo Rado, il grafo completo e il grafo vuoto. Bonato, Cameron e Delić 2000 e Diestel et al. 2007 hanno mostrato che gli unici grafici orientati aventi la stessa proprietà sono ottenuti da questi tre grafici scegliendo opportuni orientamenti degli spigoli.

Se siamo interessati a partizioni di archi, un risultato simile, ma più debole, mostra che esiste un sottografo isomorfo all'intero grafo di Rado scegliendo gli archi tra due degli elementi della partizione, ma che non sempre è possibile prendere i bordi in un unico elemento.

Relazione con la teoria dei modelli

Ronald Fagin dimostrato che se una dichiarazione di grafici (più rigorosamente una dichiarazione di primo ordine teoria egualitaria contenente la relazione di adiacenza , che esprime che un bordo collega vertici un e b ) è vero per il grafico di Rado, è vero per quasi tutti i grafici finiti, vale a dire che la proporzione di grafi con n vertici per i quali l'affermazione è vera tende a 1 quando n tende all'infinito.

La proprietà di estensione può essere espressa da una serie infinita di affermazioni del primo ordine , asserendola per tutti gli insiemi di vertici U e V aventi rispettivamente i e j elementi. Ad esempio, può essere scritto come

Haim Gaifman  (in) ha dimostrato che l'insieme di e le affermazioni che affermano che la relazione di adiacenza è simmetrica e antiriflessiva sono gli assiomi di una teoria completa , di cui il grafo di Rado è l'unico modello numerabile (quest'ultimo risultato segue dall'unicità dei grafi avendo la proprietà di estensione, e permette di dimostrare la completezza grazie al criterio di Łoś – Vaught ).

generalizzazioni

La proprietà universale del grafo di Rado non si generalizza, ad esempio, alle immersioni isometriche, cioè agli isomorfismi che conservano la distanza  : il grafo di Rado è di diametro due, e quindi nessun grafico di diametro maggiore non può immergersi in esso isometricamente. Moss costruì per ogni valore di n un grafico contenente isometricamente tutti i grafici finiti di diametro n , ottenendo il grafico infinito completo per n = 1 e il grafico di Rado per n = 2.

Saharon Shelah ha studiato l'esistenza di innumerevoli grafi universali, ottenendo sufficienti condizioni di esistenza sul loro cardinale .

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato "  Rado graph  " ( vedi elenco degli autori ) .

Appunti

  1. Una costruzione sostanzialmente equivalente, ma data in termini prefissati, costituisce il Teorema 2 di Cameron 1997 .

Riferimenti

  1. Ackermann 1937  ; Rado 1964 .
  2. Vedi Cameron 1997 , risultato 1.
  3. Cameron 1997 , Proposizione 5.
  4. Cameron 1997 , Teorema 2.
  5. Cameron 1997 .
  6. Horsley, Pike e Sanaei 2011 .
  7. Cameron 1997 , Proposizione 6.
  8. Delahaye 2018
  9. Cameron 2001 .
  10. Cameron 1997 , sezione 1.8: il gruppo degli automorfismi.
  11. Cameron 1990  ; Diestel et al. 2007 .
  12. Pouzet e Sauer 1996 .
  13. Fagin 1976 .
  14. Spencer 2001 , sezione 1.3, "Extension Statements and Rooted Graphs", p. 17-18 .
  15. Gaifman 1964 .
  16. Gaifman 1964  ; Marker 2002 , Teorema 2.4.2, p. 50.
  17. Marker 2002 , Teorema 2.2.6, p. 42.
  18. Moss 1989 .
  19. Sela 1984 .

Bibliografia

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">