# random graphs

Published articles for random graphs.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## 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$.

## The Giant Component and Explosive Percolation

DevFeed: [The Giant Component and Explosive Percolation](<https://devfeed.tech/articles/the-giant-component-and-explosive-percolation-40375.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/02/02/the-giant-component-and-explosive-percolation/>)

Published: 2015-02-02T09: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>), [Data analysis](<https://devfeed.tech/topics/data-analysis.md>)

Tags: [big-o-notation](<https://devfeed.tech/tags/big-o-notation.md>), [erdos-renyi](<https://devfeed.tech/tags/erdos-renyi.md>), [first-moment-method](<https://devfeed.tech/tags/first-moment-method.md>), [giant-component](<https://devfeed.tech/tags/giant-component.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [inequality](<https://devfeed.tech/tags/inequality.md>), [markov](<https://devfeed.tech/tags/markov.md>), [method-of-moments](<https://devfeed.tech/tags/method-of-moments.md>), [network-science](<https://devfeed.tech/tags/network-science.md>), [percolation](<https://devfeed.tech/tags/percolation.md>), [probability-theory](<https://devfeed.tech/tags/probability-theory.md>), [random-graph](<https://devfeed.tech/tags/random-graph.md>), [random-graphs](<https://devfeed.tech/tags/random-graphs.md>), [random-variables](<https://devfeed.tech/tags/random-variables.md>)

### AI overview

This article develops rigorous results about Erdős-Rényi random graphs, following a conjecture about connectivity at edge probability p = 5/n. It introduces threshold theorems and begins explaining the first moment method, Markov's inequality, and isolated vertices.

### Source excerpt

Last time we left off with a tantalizing conjecture: a random graph with edge probability $ p = 5/n$ is almost surely a connected graph. We arrived at that conjecture from some ad-hoc data analysis, so let's go back and treat it with some more rigorous mathematical techniques. As we do, we'll discover some very interesting "threshold theorems" that essentially say a random graph will either certainly have a property, or it will certainly not have it.

## The Erdős-Rényi Random Graph

DevFeed: [The Erdős-Rényi Random Graph](<https://devfeed.tech/articles/the-erdos-renyi-random-graph-40329.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2013/08/22/the-erdos-renyi-random-graph/>)

Published: 2013-08-22T16:11:18Z

Content type: tutorial

Language: en

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

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [math](<https://devfeed.tech/topics/math.md>), [Networks](<https://devfeed.tech/topics/networks.md>)

Tags: [color](<https://devfeed.tech/tags/color.md>), [combinatorics](<https://devfeed.tech/tags/combinatorics.md>), [erdos](<https://devfeed.tech/tags/erdos.md>), [giant-component](<https://devfeed.tech/tags/giant-component.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graph-coloring](<https://devfeed.tech/tags/graph-coloring.md>), [graph-theory](<https://devfeed.tech/tags/graph-theory.md>), [properties](<https://devfeed.tech/tags/properties.md>), [random-graph](<https://devfeed.tech/tags/random-graph.md>), [random-graphs](<https://devfeed.tech/tags/random-graphs.md>), [renyi](<https://devfeed.tech/tags/renyi.md>), [social-networks](<https://devfeed.tech/tags/social-networks.md>), [structure](<https://devfeed.tech/tags/structure.md>)

### AI overview

This tutorial introduces the Erdős-Rényi random graph model G(n,p), in which each possible edge between n vertices is included independently with probability p. It discusses the model's role in combinatorics and network analysis, along with basic properties, applications, and computational exploration.

### Source excerpt

During the 1950's the famous mathematician Paul Erdős and Alfred Rényi put forth the concept of a random graph and in the subsequent years of study transformed the world of combinatorics. The random graph is the perfect example of a good mathematical definition: it's simple, has surprisingly intricate structure, and yields many applications. In this post we'll explore basic facts about random graphs, slowly detail a proof on their applications to graph theory, and explore their more interesting properties computationally (a prelude to proofs about their structure).