A random graph is a graph that is chosen according to some probability distribution. In the most common model, $G_{n, p}$, a graph has $n$ vertices, and edges are present independently with probability $p$.

learn more… | top users | synonyms

1
vote
0answers
10 views

The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
0
votes
0answers
19 views

Probability of maximum degree in On random graphs I by Erdos

In The Maximum Degree of a Random Graph by RIORDAN et al., the authors commented that the study of the distribution of the maximum degree $d^{max}(G)$ of a random graph $G$ was started by Erdos and ...
0
votes
1answer
31 views

Confused with the power set of an integer

I am going through The Maximum Degree of a Random Graph by RIORDAN et al. On the second page, the notation $\mathbb{P}(\mathcal{D})$ is used which I assume the power set of the set $\mathcal{D}$. ...
0
votes
0answers
10 views

The random graph quantity $S(n: K, L)$

I am going through Degree sequences of random graphs by Béla Bollobás. On page $3$ the author introduces the quantity $S(n: K, L)$ without any explanation. Could anyone please help me in ...
0
votes
1answer
13 views

Calculating the probability of a graph being Erdos-Renyi

Given an undirected, unweighted graph with |V| = 11 and |E|= 19 and given probability p=0.5 I have to calculate the probability of the graph being generated using the Erdos-Renyi Model. I applied the ...
0
votes
2answers
45 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
-2
votes
0answers
14 views

Parallel Luby Algorithm för finding Maximal independent set

This the Algorithm of Luby: MIS Luby Algorithm This Algorithm at the end spent O(log n). I want to understand why exactly O(log n), I need also a mathematical prove of this. Also How many ...
0
votes
0answers
30 views

Show With High Probability $G_{n, p}$ has an induced path of length $(\log(n))^{1/2}$

The problem on which I am working states: Let the probability $p = d/n$ where $d > 1$. Show that with high probability, $G_{n, p}$ contains an induced path of length $(\log(n))^{1/2}$. My ...
2
votes
3answers
50 views

Finding the limit of ${n-1 \choose k}p^k(1-p)^{n-1-k}$ as $n$ goes to infinity

On this Wikipedia page on random graphs, they compute this limit to be $$\lim_{n\to\infty}\binom{n-1}kp^k(1-p)^{n-1-k}=\frac{(np)^ke^{-np}}{k!}$$ with $np$ constant. Any hints on how to get that? ...
3
votes
2answers
62 views

Show With High Probability, No Vertex Belongs to More than One Triangle

I am working on a random graphs problem, which is stated as follows: Suppose that $p = d/n$, where $d$ is constant. Prove that with high probability (w.h.p.), no vertex belongs to more than one ...
1
vote
0answers
38 views

Are the vertices of a Voronoi diagram obtained from a Sierpinski attractor also a kind of attractor?

Trying to understand how the Voronoi Diagrams work I did a test generating the Voronoi diagram of the points obtained from The Chaos Game algorithm when it is applied to a $3$-gon. The result is a set ...
1
vote
2answers
32 views

Ensure a graph approximates an Erdős-Renyi random graph even as nodes are added

Suppose we have a graph $G$ where the number of nodes increases over time, e.g. whenever the mean number of edges per node exceeds some value (which may be a function of the number of nodes). What is ...
0
votes
1answer
53 views

Sparse sequence of random graphs

I have the following definition for sparse random graphs: In the lecture it was said that actually this type of graphs have a lot of "hubs", i.e. a lot of vertices of high degree. But this is ...
2
votes
2answers
70 views

Max matching size in a random graph

Consider the random graph $G(n,\frac{1}{n})$. I'm trying to estimate the size of the maximum matching in $G$. If we look at one vertex, the expected value of its degree is $\frac{n-1}{n}$ so it ...
1
vote
1answer
20 views

Random graph application

Hi am looking at the theorem 1.1 but I can't come to that distribution. Can someone tell me how does this factor comes in the distribution of $D_n^*$? That sounds trivial but I cannot get it. ...
0
votes
0answers
21 views

Why do Erdos-Renyi prove theorems for class $A$?

In Erdos-Renyi's first paper on Random Graphs (1959), whose link you can find here, they prove four theorems using a lemma. In three of the later theorems, they say that focussing simply on class $A$ ...
0
votes
1answer
26 views

Random Graph - lower bound in the number of edges going out from a subset of vertices

I need to proof the following: Show that exist a costant $c=c(p)>0$ (with p the probability in the random graph) such that for a subset $X\subset V(G)$ with G a random graph G(n,p) and with ...
1
vote
2answers
35 views

Is it possible to construct the Rado Graph as a countably infinite graph with non-constant edge probabilities?

Let's say we have a countably infinite set $V$ of vertices and a map $f:V\times{V}\to{(0,1)}$ that assigns to each pair $(i,j)$ of vertices an edge with probability $f(i,j) = p$. I believe that if ...
1
vote
0answers
24 views

One proof in Random graph Bela Bollobas about Hamiltonian Cycles

In Random Graph 2001 (Bela Bollobas), P209, the proof for lemma 8.7, it says that $\sum_{u=u_0-1}^{u_1}\sum_{w=1}^{\llcorner(\gamma - 1)u\lrcorner}(\log n)^w (\frac{e}{u})^u(\frac{eu}{w})^wn^{\gamma ...
-2
votes
1answer
77 views

Random graph of $4$ vertices is triangle-free

Consider an undirected random graph $G$ of $4$ vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the probability that $G$ is triangle-free? Thank ...
1
vote
1answer
85 views

Random graph is simple cycle or tree

Consider an undirected random graph $G$ of $n$ vertices. The probability that there is an edge between a pair of vertices is $p$. What is the probability that $G$ is simple cycle of $n$ vertices or ...
0
votes
1answer
23 views

Stochastic domination of the cluster size

I have troubles understanding the main idea used to prove the following theorem, which should be a coupling argument. My question refers to the following notes, at page 125. ...
1
vote
0answers
24 views

Expected number of vertex-pairs without any simple path in between

Consider a random undirected graph $G(n, p)$, with $n$ vertices and each edge is added independently with probability $p$. The goal is to find the expected number of vertex-pairs without any simple ...
0
votes
1answer
50 views

Expected degree of a vertex in a random network

In the paper "Finding and evaluating community structure in networks" by M. E. J. Newman and M. Girvan section 5a, when they construct random communities as a network, they state: Edges were ...
0
votes
1answer
32 views

CLT version for $ER_n(p)$ graphs

We defined the Erdôs- Rényi graph as follows: $ER_n(P)$ is the random graph with vertex set $[n]$ where each pair $\{u,v\}$ of vertices is added to the edges set $E$ independently with probability ...
1
vote
1answer
37 views

How can classical random graph theory be applied to real world networks?

In real world networks, we have no further information about the structure of the networks. For example, in the Facebook network, we assume each one has some known particular probabilities to ...
0
votes
0answers
19 views

About the Alon-Krivilevich-Vu result on concentration of eigenvalues of random matrices.

I am looking at the statement in theorem 5.4 in these notes, http://www.math.ucla.edu/~nickcook/talagrand.pdf I had a few questions about the statement of this theorem, Can someone kindly clarify ...
1
vote
0answers
29 views

Branching process - generating function

I report our definition of a branching process. Let $X$ be a random variable with $\mathbb{P}[X=j]=p_j$ and $(X_{n,i})_{n,i\geq 1}$ i.i.d. random variables with $X_{n,i}\overset{\mathcal{L}}{=}X$. ...
1
vote
2answers
96 views

Expected number of isolated vertices for random graph G(n, N)

For a random graph G(n,p), I can understand how to calculate the E(X) where X is the number of isolated vertices. However, in the case of fixed N edges (N = cn), I am not sure how to proceed in the ...
0
votes
0answers
24 views

Why is there an extra power of of g in this integral?

I'm trying to understand this paper: Betweenness Centrality in Large Networks. They are looking at the distribution of $g$ (betweenness centrality) and $k$ (degree centrality) in large graphs. They ...
0
votes
1answer
29 views

Probability that a random graph on countably many vertices is connected

Fix $0 < p < 1$ and let $G$ be a random graph on elements $\mathbb{N}$ where for $n,m \in \mathbb{N}$, the probability that there is an edge between $n$ and $m$ will $p$. What is the probability ...
1
vote
1answer
51 views

probability of having cycle in a random directed graph with a given in-degree distribution

Consider directed graph $G \left(V, E\right)$. Let random variable $N$ be the in-degree of a vertex. We assume that in-degree values are i.i.d random variables with PMF $f_N(n)$. 1- What is the ...
0
votes
0answers
19 views

Any graph $G$ has a $k$-colorable subgraph?

I'm trying to prove that, for each $k\in \mathbb{N}$ and each simple graph $G=(V,E)$, $G$ has a $k$-colorable subgraph $H=(V',E')$ such that $|E^\prime|\ge (1-1/k)|E|$. I think that i have to use ...
0
votes
0answers
32 views

Calculating the clustering coefficient in the configuration model

I want to calculate the limit of the clustering coefficient in a sequence of graphs $\{G_n\}_{n\in\mathbb{N}}$, where each $G_n$ is constructed by the configuration model ($n$ denotes the number of ...
2
votes
1answer
27 views

Big-O/Little-o with high probability (in the context of random graphs)

I'm getting in a muddle trying to understand statements which include both Landau symbols and the notion of "with high probability" (w.h.p.) in random graphs. Setting/Background Reading about ...
4
votes
2answers
128 views

Literature recommendation on random graphs

I'm looking for introductory references on random graphs (commonly mentioned as Erdős–Rényi graphs), having previous acquaintance with basic graph theory. I know that Bela Bollobas' book on random ...
0
votes
0answers
25 views

Probability of Path Existing between Vertices of a “General Random Graph”

Consider a "general random graph" G with vertices V. Each potential edge is present with some independent probability, described by a "probabilistic adjacency matrix" $A \in [0, 1]^{|V| \times |V|}$ ...
1
vote
1answer
29 views

Finite graphs forms Fraïssé Class with limit Rado/random graph

I was reading Peter Cameron's explanation of Fraïssé's Theorem in his book Permutation Groups (Chapter 5). He states the Fraïssé class of finite graphs has limit being the countable random/Rado graph, ...
1
vote
0answers
89 views

Cut distance between two random graphs

I am studying the cut metric from Large Networks and Graph Limits by Lovasz and need help proving one of the statements. On page 128, it says that the cut distance between two independent random ...
0
votes
1answer
27 views

Number of edges in randomly induced graph

If I have a simple graph $G$ with $n$ vertices and $m$ edges, then I want to create a randomly induced graph $G_x$ by selecting vertices with a probability of $n/2m$. The edges of $G_x$ are defined to ...
6
votes
0answers
75 views

Generating a Random Connected Graph

Given a graph G(V, E), with |V | = n and |E| = 0 (that is, the graph is empty), and a static set F containing all the possible edges. Consider the following algorithm for generating a random graph. ...
2
votes
1answer
69 views

How to estimate the conditional probability of node reachability on a random graph?

Let $G=(V,E)$ be an undirected random graph such that $V$ is the node set, $E$ is the edge set. Each edge $uv \in E$ is associated with a probability $p_{uv}$, i.e., $uv$ is kept with probability ...
0
votes
1answer
57 views

Dijkstra's algorithm, am I or the teacher mistaken?

Imagine that Dijkstra’s algorithm has been used to show the length of the shortest path from $a$ to $g$ in the graph in figure 1. Which of the following vertices is added first to the set $S$? It's ...
4
votes
0answers
26 views

terminology for a “forward flow” type of random digraph

I am trying to find a characterization of the probability that vertex $1$ is connected to an arbitrary large vertex $N$ in a random digraph. The difference from typical random digraphs is that if ...
0
votes
1answer
65 views

Diameter of random graph.

Basically I was given a random graph with fixed probability and I need to prove that the diameter of the random graph is asymptotically 2. See the following picture for the detail of the question. ...
2
votes
1answer
108 views

Expected maximum degree Erdős–Rényi graph

Consider an Erdős–Rényi random graph $\mathrm{ER}(N,p)$, where $N$ is the number of nodes and $p$ the probability of placing an edge between each distinct pair of nodes. I'm interested in finding ...
1
vote
0answers
17 views

Size of intersection of balls on non-ameanable graphs

Let $G$ be a vertex-transitive non-ameanable graph and let $B(x,n)$ be the ball of radius $n$ centered on the vertex $x$. I am interested in estimates on the cardinality of the following set, ...
1
vote
0answers
38 views

Number of same degree vertex pairs between two random graphs

I am considering the random graphs generated by the Erdős-Rényi model for this question. Random Graphs as Models of Networks by Newman is a reference on this topic. A random graph $\Gamma_{n,p}$ has ...
0
votes
0answers
33 views

Function/algorithm to generate a random walk on a graph

I'm looking for a graph function or an algorithm that can generate a random fluctuating random walk that will eventually converge between the value of y = 0 and y = 1, more or less after a number of ...
0
votes
1answer
51 views

Prerequisites for Random Graph Theory

I would dearly love to know the prerequisites for self-studying Random Graph Theory and Percolation Theory in Probability. My knowledge currently involves: Basic probability concepts: the axioms, ...