Rado-Graph

Der Rado-Graph (auch als Erdős-Rényi-Graph oder Zufallsgraph bezeichnet) ist ein spezieller abzählbar unendlicher Graph, der fast sicher entsteht, wenn jedes Knotenpaar unabhängig und mit Wahrscheinlichkeit ${\displaystyle {\tfrac {1}{2}}}$ durch eine Kante verbunden wird.

Eine wichtige Erkenntnis ist, dass ein Satz ${\displaystyle \varphi }$ in der Prädikatenlogik erster Stufe genau dann für fast alle endlichen Graphen gilt, wenn ${\displaystyle \varphi }$ vom Rado-Graphen erfüllt wird.

Er ist aufgrund von Arbeiten in den 1960er-Jahren nach Richard Rado bzw. Rado, Paul Erdős und Alfréd Rényi benannt, taucht aber schon 1937 bei Wilhelm Ackermann auf.

1. ↑ Rado, Universal graphs and universal functions, Acta Arithmetica, Band 9, 1964, S. 331–340.
2. ↑ Paul Erdős, Alfred Rényi, Asymmetric graphs, Acta Mathematica Academiae Scientiarum Hungaricae, Band 14, 1963, S. 295–315
3. ↑ Ackermann, Die Widerspruchsfreiheit der allgemeinen Mengenlehre, Mathematische Annalen, Band 114, 1937, S. 305–315