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.