The threshold (edge probability) for certain properties such as diameter two ($\sqrt{2\frac{lnn}{n}}$) are dependent on number of nodes in Erdős-Rényi graphs. Because of which as $n \to \infty$, the threshold edge probability seems to be lower and lower. How does that make any sense? How does small edge probability ensure that the graph is not just connected but also has two hops? What am I missing here?
2026-03-27 13:38:18.1774618698
Why does the threshold for most properties in Erdős-Rényi graphs tend to decrease with increasing nodes?
228 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
There are 1 best solutions below
Related Questions in PROBABILITY
- How to prove $\lim_{n \rightarrow\infty} e^{-n}\sum_{k=0}^{n}\frac{n^k}{k!} = \frac{1}{2}$?
- Is this a commonly known paradox?
- What's $P(A_1\cap A_2\cap A_3\cap A_4) $?
- Prove or disprove the following inequality
- Another application of the Central Limit Theorem
- Given is $2$ dimensional random variable $(X,Y)$ with table. Determine the correlation between $X$ and $Y$
- A random point $(a,b)$ is uniformly distributed in a unit square $K=[(u,v):0<u<1,0<v<1]$
- proving Kochen-Stone lemma...
- Solution Check. (Probability)
- Interpreting stationary distribution $P_{\infty}(X,V)$ of a random process
Related Questions in PROBABILITY-THEORY
- Is this a commonly known paradox?
- What's $P(A_1\cap A_2\cap A_3\cap A_4) $?
- Another application of the Central Limit Theorem
- proving Kochen-Stone lemma...
- Is there a contradiction in coin toss of expected / actual results?
- Sample each point with flipping coin, what is the average?
- Random variables coincide
- Reference request for a lemma on the expected value of Hermitian polynomials of Gaussian random variables.
- Determine the marginal distributions of $(T_1, T_2)$
- Convergence in distribution of a discretized random variable and generated sigma-algebras
Related Questions in GRAPH-THEORY
- characterisation of $2$-connected graphs with no even cycles
- Explanation for the static degree sort algorithm of Deo et al.
- A certain partition of 28
- decomposing a graph in connected components
- Is it true that if a graph is bipartite iff it is class 1 (edge-coloring)?
- Fake induction, can't find flaw, every graph with zero edges is connected
- Triangle-free graph where every pair of nonadjacent vertices has exactly two common neighbors
- Inequality on degrees implies perfect matching
- Proving that no two teams in a tournament win same number of games
- Proving that we can divide a graph to two graphs which induced subgraph is connected on vertices of each one
Related Questions in RANDOM-GRAPHS
- Bound degrees of sparse random graphs
- Connectivity of random graphs - proof $\frac{logn}{n}$ is threshold
- In weighed random graph where the edge weight is restricted to $[0,1]$, what are the usual assumptions of edge weight distribution?
- Upper Bound on Vertices in SCC Graph of Directed Random Graph
- The degree of a vertex in $G(n,m)$ is approx. Poisson
- What is the expected length of the diameter of a special random graph?
- Clique numbers and Theorem 4.5.1 in "The Probabilistic Method" by Alon and Spencer
- Expected global clustering coefficient for Erdős–Rényi graph
- Probability of having a path of a given length in a random graph?
- Correlation for random graph (Erdos-Renyi)
Related Questions in NETWORK
- On the Hex/Nash connection game theorem
- minimal number of edges for a graph of size N so that there are two paths between any pair of nodes
- what is mean "Number of connected Triplets of vertices" in global clustering
- What is this "logarithmic golden ratio of scale-free networks" really called?
- Are there textbooks or resources on the mathematics of networks?
- Proving an inequality when a graph is not connected
- Probability of at least two bits
- Probability in terms of slots wasted during network contention
- Network Science: Terminology for graphs with different kinds of edges
- Number of Spanning Trees With A Relation to Contraction of Graph
Trending Questions
- Induction on the number of equations
- How to convince a math teacher of this simple and obvious fact?
- Find $E[XY|Y+Z=1 ]$
- Refuting the Anti-Cantor Cranks
- What are imaginary numbers?
- Determine the adjoint of $\tilde Q(x)$ for $\tilde Q(x)u:=(Qu)(x)$ where $Q:U→L^2(Ω,ℝ^d$ is a Hilbert-Schmidt operator and $U$ is a Hilbert space
- Why does this innovative method of subtraction from a third grader always work?
- How do we know that the number $1$ is not equal to the number $-1$?
- What are the Implications of having VΩ as a model for a theory?
- Defining a Galois Field based on primitive element versus polynomial?
- Can't find the relationship between two columns of numbers. Please Help
- Is computer science a branch of mathematics?
- Is there a bijection of $\mathbb{R}^n$ with itself such that the forward map is connected but the inverse is not?
- Identification of a quadrilateral as a trapezoid, rectangle, or square
- Generator of inertia group in function field extension
Popular # Hahtags
second-order-logic
numerical-methods
puzzle
logic
probability
number-theory
winding-number
real-analysis
integration
calculus
complex-analysis
sequences-and-series
proof-writing
set-theory
functions
homotopy-theory
elementary-number-theory
ordinary-differential-equations
circles
derivatives
game-theory
definite-integrals
elementary-set-theory
limits
multivariable-calculus
geometry
algebraic-number-theory
proof-verification
partial-derivative
algebra-precalculus
Popular Questions
- What is the integral of 1/x?
- How many squares actually ARE in this picture? Is this a trick question with no right answer?
- Is a matrix multiplied with its transpose something special?
- What is the difference between independent and mutually exclusive events?
- Visually stunning math concepts which are easy to explain
- taylor series of $\ln(1+x)$?
- How to tell if a set of vectors spans a space?
- Calculus question taking derivative to find horizontal tangent line
- How to determine if a function is one-to-one?
- Determine if vectors are linearly independent
- What does it mean to have a determinant equal to zero?
- Is this Batman equation for real?
- How to find perpendicular vector to another vector?
- How to find mean and median from histogram
- How many sides does a circle have?
The property you chose, diameter 2, is a good example. There are two competing considerations: For two fixed nodes $x,y$, there are about $n$ (more precisely, $n-2$) potential paths between them; the threshold for one of these paths being available (retained, or open) is $n^{-1/2}$. Guaranteeing such a path for every pair is what costs the additional logarithmic factor.