Rado-Graph

In der Mathematik , genauer in der Graphentheorie , ist der Rado - Graph , auch Erdős - Rényi - Graph oder Zufallsgraph genannt , ein abzählbarer unendlicher Graph , der Anfang der 1960er Jahre von Richard Rado , Paul Erdős und Alfréd Rényi untersucht wurde und durch die Erweiterungseigenschaft gekennzeichnet ist . was impliziert, dass er (als Untergraph ) jeden endlichen oder abzählbaren Graphen enthält.

Es gibt mehrere Konstruktionen davon; es ist insbesondere (mit ziemlicher Sicherheit ) der zufällige Graph, den man erhält, indem man zufällig für jedes Knotenpaar wählt, ob sie verbunden sind oder nicht.

Historisch

Der Graph Rado wurde 1937 von Wilhelm Ackermann aus den erblich endlichen Mengen  (in) aufgebaut (genauer beschrieb er einen gerichteten Graphen, aus dem der Rado-Graphen durch Wegnahme der Orientierung gewonnen wird). In ihrer Arbeit auf Zufallsgraphen , Paul Erdös und Alfréd Rényi konstruierten sich als unendliches Zufallsgraphen und zeigten , dass es eine unendliche Anzahl von automorphisms durch ein Argument hat , das auch seine Einzigartigkeit zu beweisen erlauben würde. Richard Rado hat ihn als universellen Graphen wiederentdeckt und eine deterministische Konstruktion gegeben, die im Wesentlichen der von Ackermann entspricht.

Konstruktionen

Binäres Schreiben

Ackermann und Rado gaben eine explizite Konstruktion mit dem Prädikat BIT  (en) . Wenn man die Ecken des Graphen und die natürlichen ganzen Zahlen 0, 1, 2, ... identifiziert, verbindet eine Kante die Ecken x und y (mit x  <  y ) genau dann, wenn das Bit mit Rang x der binären Darstellung von yy ist gleich 1 Zum Beispiel gibt es eine Verbindung zwischen x = 2 und y = 4 = 100 2 , aber nicht zwischen x = 1 und y .

Zufällige Grafiken

Rados Graph erscheint fast sicher, wenn wir das von Erdős und Rény entwickelte Zufallsgraphenmodell auf eine abzählbare Menge von Knoten anwenden . Genauer gesagt, indem man unabhängig für jedes Knotenpaar mit Wahrscheinlichkeit p (0 < p < 1) wählt, ob diese Knoten durch eine Kante verbunden sind, ist der resultierende Graph fast sicher (d. h. mit Wahrscheinlichkeit 1) isomorph zum Graphen von Rado; es ist dieses Ergebnis, das den Artikel rechtfertigt, der im Ausdruck "  der Zufallsgraph" definiert ist, der ihn manchmal bezeichnet.

Ein Graph isomorph zur Graph komplementären zum Rado Graph kann mit einer Wahrscheinlichkeit 1- indem Sie die Ränder (fast sicher) durch den gleichen Aufbau erhalten werden p , die zeigt , dass die Rado Graph ist selbstkomplementär .

Andere Konstruktionen

Die Erweiterungseigenschaft charakterisiert den Rado-Graphen und erlaubt zu zeigen, dass viele Konstruktionen zu ihm isomorph sind.

In Ackermanns Konstruktionen von 1937 sind die Knoten des Rado-Graphen die erblich endlichen Mengen (d. h. die endlichen Mengen, deren Elemente selbst erblich endlich sind) und eine Kante verbindet zwei Knoten, wenn einer von ihnen Teil des anderen ist.

Eine andere Konstruktion des Rado-Graphen ist analog zu der der Paley-Graphen . Die Ecken sind die Primzahlen der Form 4 n + 1, und eine Kante verbindet sie, wenn eine der beiden quadratischen Reste modulo die andere ist (diese Beziehung ist nach dem quadratischen Reziprozitätsgesetz symmetrisch ).

Kann auch als Schnittgraph eines Blocksystems  (en) Unendlich konstruiert werden, wobei jeder Block unendlich (abzählbar) ist.

Eigenschaften

Erweiterungseigenschaft

Der Graph von Rado erfüllt die folgende Erweiterungseigenschaft : Für jedes Paar von Mengen disjunkter endlicher Ecken U und V existiert eine Ecke x, die weder zu U noch zu V gehört und mit allen Ecken von U verbunden ist , aber keiner von denen von V  ; diese Eigenschaft charakterisiert diesen Graphen, wie unten gezeigt .

Die Definition des Graphen durch binäre Darstellung erlaubt eine konstruktive Demonstration, indem man

 :

x ist größer als alle Gebäudeelemente von U und V , benachbart zu allen Elementen U , und da U und V disjunkt sind, grenzt x an jeden Teil von V an .

Die Konstruktion als Zufallsgraph gibt jedem Knoten, der nicht in U oder V liegt, eine Wahrscheinlichkeit p | U | (1- p ) | V | um die Erweiterungseigenschaft unabhängig von den anderen Knoten zu erfüllen; Da es unendlich viele solcher Gipfel gibt, gibt es mit ziemlicher Sicherheit einen, der die Eigenschaft erfüllt.

Untergrafiken

Für jeden endlichen oder unendlichen abzählbaren Graphen G die Erweiterungseigenschaft, um einen Untergraphen des zu G isomorphen Graphen zu erstellen . Der Beweis erfolgt durch Induktion über die Ecken von G (von denen angenommen wird, dass sie durch die ganzen Zahlen indiziert sind): Angenommen, für die ersten n Ecken wird ein Isomorphismus konstruiert , fügen wir eine neue Ecke hinzu, indem wir aus dem Rado-Graphen eine Ecke mit genau den gleichen Verknüpfungen auswählen mit den bereits konstruierten Gipfeln die entsprechenden Scheitelpunkte in G . Aus diesem Grund wird manchmal gesagt, dass Rados Graph ein universeller Graph ist , aber tatsächlich ist er ein schwächerer Begriff als der eines universellen Problems , das durch die Kategorientheorie definiert wird .

Einzigartigkeit

Der Graph von Rado ist bis auf Isomorphismus der einzige abzählbare Graph mit der Erweiterungseigenschaft. Wenn G und H zwei Graphen mit dieser Eigenschaft sind, ist jeder der beiden isomorph zu einem Teilgraphen des anderen; Wenn man die Konstruktion dieser Teilgraphen spezifiziert, kann man durch Induktion einen Isomorphismus zwischen G und H nach dem Hin-und-Her-Verfahren erhalten (analog zum Beweis des Cantor-Bernstein-Theorems ).

Symmetrien

Ausgehend von zwei endlichen und isomorphen Teilgraphen des Rado-Graphen ermöglicht die vorangegangene Konstruktion, diesen Isomorphismus zu einem Automorphismus des gesamten Graphen zu erweitern; wir sagen, dass der Rado-Graphen ultrahomogen ist . Insbesondere existiert ein Automorphismus, der zwei beliebige Kanten übereinander sendet, und der Graph von Rado ist somit ein symmetrischer Graph . Die Gruppe der Automorphismen des Rado-Graphen ist eine einfache Gruppe mit der Kraft des Kontinuums .

Noten

Jede endliche Partition der Ecken des Rado-Graphen induziert mindestens einen Teilgraphen, der zum gesamten Graphen isomorph ist. Cameron 2001 gibt einen kurzen Beweis dafür, der durch Zusammenkleben von Teilmengen jedes induzierten Teilgraphen erhalten wird, die die Erweiterungseigenschaft nicht verifizieren würden. Nur drei abzählbare ungerichtete Graphen haben diese Eigenschaft: der Rado-Graphen, der vollständige Graph und der leere Graph. Bonato, Cameron und Delić 2000 und Diestel et al. 2007 haben gezeigt, dass aus diesen drei Graphen durch die Wahl geeigneter Orientierungen der Kanten die einzigen orientierten Graphen mit der gleichen Eigenschaft erhalten werden.

Wenn wir uns für Partitionen von Kanten interessieren, zeigt ein ähnliches, aber schwächeres Ergebnis, dass es einen Teilgraphen gibt, der isomorph zum gesamten Rado-Graphen ist, indem die Kanten unter zwei der Elemente der Partition gewählt werden, aber dass es nicht immer möglich ist, zu nehmen die Kanten in einem einzigen Element.

Beziehung zur Modelltheorie

Ronald Fagin zeigte, dass, wenn eine Aussage über Graphen (genauer gesagt eine Aussage der egalitären Theorie erster Ordnung, die die Adjazenzrelation enthält , die ausdrückt, dass eine Kante die Knoten a und b verbindet ) für Rados Graph gilt, dies für fast alle endlichen Graphen gilt, das heißt, dass der Anteil der Graphen mit n Knoten, für die die Aussage wahr ist, gegen 1 tendiert, wenn n gegen unendlich geht.

Die Erweiterungseigenschaft kann durch eine unendliche Reihe von Aussagen erster Ordnung ausgedrückt werden , die sie für alle Eckenmengen U und V mit i bzw. j Elementen behaupten . Kann zum Beispiel geschrieben werden als

Haim Gaifman  (in) zeigte, dass die Menge und Aussagen, die bejahen, dass die Adjazenzrelation symmetrisch und antireflexiv ist, die Axiome einer vollständigen Theorie sind , von der der Rado-Graphen das eindeutige abzählbare Modell ist (dieses letzte Ergebnis folgt aus der Eindeutigkeit der Graphen graph mit der Erweiterungseigenschaft und ermöglicht den Nachweis der Vollständigkeit dank des Kriteriums von Łoś – Vaught ).

Verallgemeinerungen

Die universelle Eigenschaft des Rado-Graphen lässt sich beispielsweise nicht auf isometrische Einbettungen, also abstandserhaltende Isomorphismen verallgemeinern  : Der Rado-Graphen hat den Durchmesser zwei, und deshalb kann kein Graph mit größerem Durchmesser isometrisch in ihn eintauchen. Moss konstruierte für jeden Wert von n einen Graphen, der isometrisch alle endlichen Graphen des Durchmessers n enthält , wodurch der vollständige unendliche Graph für n = 1 und der Graph von Rado für n = 2 erhalten wurde.

Saharon Shelah untersuchte die Existenz unzähliger universeller Graphen und erhielt ausreichende Existenzbedingungen auf ihrem Kardinal .

Hinweise und Referenzen

(fr) Dieser Artikel ist teilweise oder vollständig aus dem Wikipedia - Artikel in genommen englischen Titeln „  Rado Graph  “ ( siehe die Liste der Autoren ) .

Anmerkungen

  1. Eine im Wesentlichen äquivalente Konstruktion, aber in festen Begriffen gegeben, bildet Theorem 2 von Cameron 1997 .

Verweise

  1. Ackermann 1937  ; Rado 1964 .
  2. Siehe Cameron 1997 , Ergebnis 1.
  3. Cameron 1997 , Proposition 5.
  4. Cameron 1997 , Satz 2.
  5. Cameron 1997 .
  6. Horsley, Hecht und Sanaei 2011 .
  7. Cameron 1997 , Proposition 6.
  8. Delahaye 2018
  9. Cameron 2001 .
  10. Cameron 1997 , Abschnitt 1.8: Die Gruppe der Automorphismen.
  11. Cameron 1990  ; Diestelet al. 2007 .
  12. Pouzet und Sauer 1996 .
  13. Fagin 1976 .
  14. Spencer 2001 , Abschnitt 1.3, „Erweiterungsanweisungen und verwurzelte Graphen“, S. 17-18 .
  15. Gaifman 1964 .
  16. Gaifman 1964  ; Marker 2002 , Satz 2.4.2, p. 50.
  17. Marker 2002 , Satz 2.2.6, p. 42.
  18. Moos 1989 .
  19. Shelah 1984 .

Literaturverzeichnis

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