# Zero-One Laws for Random Graphs

DevFeed: [Zero-One Laws for Random Graphs](<https://devfeed.tech/articles/zero-one-laws-for-random-graphs-40376.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/02/09/zero-one-laws-for-random-graphs/>)

Published: 2015-02-09T09:00:00Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [big-o-notation](<https://devfeed.tech/tags/big-o-notation.md>), [connectivity](<https://devfeed.tech/tags/connectivity.md>), [countability](<https://devfeed.tech/tags/countability.md>), [distribution](<https://devfeed.tech/tags/distribution.md>), [erdos-renyi](<https://devfeed.tech/tags/erdos-renyi.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [logic](<https://devfeed.tech/tags/logic.md>), [logical](<https://devfeed.tech/tags/logical.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [model-theory](<https://devfeed.tech/tags/model-theory.md>), [network-science](<https://devfeed.tech/tags/network-science.md>), [parameter](<https://devfeed.tech/tags/parameter.md>), [random-graph](<https://devfeed.tech/tags/random-graph.md>), [random-graphs](<https://devfeed.tech/tags/random-graphs.md>), [statement](<https://devfeed.tech/tags/statement.md>), [vertex](<https://devfeed.tech/tags/vertex.md>)

## AI overview

This article introduces zero-one laws for Erdős-Rényi random graphs. It explains that many graph properties, including properties expressible in first-order logic, have probabilities that tend toward zero or one as the graph grows, with behavior determined by relevant thresholds or constant edge probabilities.

## Source excerpt

Last time we saw a number of properties of graphs, such as connectivity, where the probability that an Erdős-Rényi random graph $ G(n,p)$ satisfies the property is asymptotically either zero or one. And this zero or one depends on whether the parameter $ p$ is above or below a universal threshold (that depends only on $ n$ and the property in question). To remind the reader, the Erdős-Rényi random "graph" $ G(n,p)$ is a distribution over graphs that you draw from by including each edge independently with probability $ p$.