When Does the Zero-One Law Hold? (Q3979555)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 20164
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | When Does the Zero-One Law Hold? |
scientific article; zbMATH DE number 20164 |
Statements
When Does the Zero-One Law Hold? (English)
0 references
26 June 1992
0 references
threshold function
0 references
zero-one law
0 references
random graph
0 references
probability
0 references
0 references
0 references
0 references
0 references
0 references
0.73191214
0 references
Let \(G(n,p)\) denote a random graph on vertex set \(\{1,2,3,\dots,n\}\), where each pair \((i,j)\) of vertices are adjacent with independent probability \(p\). Let \(\text{P}[G(n,p)\models A]\) be the probability that \(G(n,p)\) satisfies the property \(A\). A function \(p=p(n)\) is said to satisfy the Zero-One Law if \[ \lim_{n\to\infty}\text{P}\bigl[G(n,p)\models A\bigr]=0\quad\text{or}\quad 1 \] for all statements \(A\) of the first order theory of graphs. The authors give a characterization of those \(p=p(n)\) that satisfy the Zero-One Law.
0 references
