Questions tagged [random-graphs]

A random graph is a graph - a set of vertices and edges - 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$. Use (graphing-functions) instead if your question is about graphing or plotting functions.

Filter by
Sorted by
Tagged with
0 votes
0 answers
18 views

Aut(G) of the random graph

Is there anyone who could explain me why the automorphism group of the random graph (the one studied by Erdös and Rényi) has the cardinality of the continuum?
user avatar
1 vote
0 answers
55 views

Discrepancy of random bipartite graphs

Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$). Define a random bipartite graph on $X \sqcup Y$ in an Erdos-Renyi fashion ...
user avatar
2 votes
1 answer
39 views

Smooth transition from Euclidean plane to hyperbolic plane

If I have a Poisson point process $\mathcal{X}$ of density $\lambda$ on the Euclidean plane $\mathbb{R}^2$, with the Euclidean metric taking pairs of points to the Euclidean distance, $$ \operatorname{...
user avatar
  • 2,411
2 votes
1 answer
29 views

What kinds of graphs are known to exhibit sharp threshold for bernoulli percolation?

What kinds of graphs are known to exhibit sharp threshold for independent bernoulli percolation? Here, sharp threshold stands for exponential decay of the probability of the cluster range below the ...
user avatar
  • 663
0 votes
0 answers
18 views

Vershynin's High dimensional probability exercise 2.4.5: Very sparse graphs are far from being regular [closed]

I don't know how to deal with the $\mathrm{log}(n)/\mathrm{log}(\mathrm{log}(n))$ since it is great than the $d=O(1)$, it's not doing concentration. I have an idea: using Pois approx to get an lower ...
user avatar
1 vote
0 answers
19 views

Uniform Spanning Tree on $\mathbb{Z}^2 \oplus \mathbb{Z}^2$

Suppose $T$ is a uniform spanning tree on the graph $G=\mathbb{Z}^2 \oplus \mathbb{Z}^2$, and $T_1$ and $T_2$ are the induced subgraphs of $T$ on the two copies of $\mathbb{Z}^2$. I am trying to show ...
user avatar
  • 194
1 vote
1 answer
29 views

Find a bound for the probability that a random simple graph with p = 1/2 + \alpha does not contain a Hamilton cycle

So I had a reasonable seeming solution using a Chernoff bound, but then realized I'd forgotten to add 1 when calculating my Delta and now my solution just seems off, any input would be welcome. Let Xi ...
user avatar
0 votes
0 answers
25 views

Probability of dependent random variables on random graph model

I am doing a research on fixed trees in random graph as uniform recurrent model. example of tree $\displaystyle T\ -\ $ tree with fixed root, $\displaystyle \ell \ =\ |T|-1,\ n\ \in \mathbb{N} :\ n\ \...
user avatar
1 vote
0 answers
16 views

Probability of having K isolated subgraphs in a graph with M one edged nodes [closed]

I need to compute the probability of having K isolated subgraphs in a graph with M nodes, each one of the M nodes is randomly linked to another node. Is there any formula that could be used to compute ...
user avatar
2 votes
1 answer
63 views

Random graph is not r-colorable w.h.p.

I need to prove that for fixed integer $r \geq 3$ and for any constant $c > 2r\ln{r}-\ln{r}$ random graph $G\left(n, \frac{c}{n}\right)$ is not r-colorable with high probability, i.e. $$ P\left(\...
user avatar
  • 43
0 votes
0 answers
9 views

What is the difference between sparse and dense random graphs?

Iam understanding not clear about difference between this two types random graphs, do they have definition? or On what basis do people classify these two types of graphs? Thank for your help.
user avatar
1 vote
0 answers
22 views

k-Cliques in the Random 3-Uniform Hypergraphs

Question: Let $H(n,p)$ be the random 3-uniform hypergraph on $n$ vertices where every hyperedge (of which there are $\binom{n}{3}$) is present with probability $p$. What is the approximate order of ...
user avatar
  • 194
0 votes
1 answer
27 views

Example of a locally finite graph without a uniform degree bound

We call an infinite graph locally finite if every vertex of it is of finite degree. A locally finite graph is said to have a uniform degree bound if the degree of every vertex of it is bounded by some ...
user avatar
0 votes
0 answers
15 views

Probability of connectedness in a deterministic graph with some random edges

Consider a graph $\mathcal{G}$ with $n$ nodes and $k$ vertices. The graph $\mathcal{G}$ is undirected and connected. Let us assume we add $n_0<n$ nodes to the graph randomly such that each node has ...
user avatar
  • 71
2 votes
0 answers
34 views

distribution of lengths for two cycles in constrained random mapping

Let $f$ be a uniform random endomorphism on $\{1,2,...,n\}$. We say $f$ is connected if its functional graph possesses exactly one connected component. The unique cycle in this component has length $...
user avatar
  • 103
0 votes
0 answers
30 views

Coupled incomplete graph cost estimation

I have this very specific problem and I didn't find anything searching, so I apologize if the question is trivial. Also, graph theory is not really my thing so I could miss important points. That ...
user avatar
  • 1
2 votes
0 answers
32 views

Why is the spectrum of Erdős-Rényi random graph approximately symmetric? Graphically what is symmetric spectrum?

I am recently self-learning random matrix theory and made some simulations about the spectrum of Erdős-Rényi random graph $G(n,p)$ when $np\to\infty$, and $np\to c=2,3$. Plots above is already ...
user avatar
  • 927
0 votes
1 answer
31 views

Calculation for the entropy of binomial random graph

In my classes, we found that for a graph $\mathbf{a}\in G(n,p)$, where we have labelled the graphs by their adjacency matrices, $P(\mathbf{a}) = \prod _{i<j}p^{a_{ij}}(1-p)^{(1-a_{ij})}$ We define ...
user avatar
  • 2,947
1 vote
1 answer
34 views

Decomposition of a Bernoulli Random Variable into a sum of Random Variables

I am having trouble understanding a seemingly simple decomposition of a Bernoulli random variable. This is a question arising from random graph theory. Data For context, $A_{ij}$ is an entry in the ...
user avatar
  • 47
1 vote
1 answer
20 views

Homomorphism densities for kernels generalizes the simple graph case

I am studying the well-written book Large networks and Graph Limits by László Lovász (you can find it here). If $F$ and $G$ are two simple graphs, then their homomorphism density is defined as $t(F,G) ...
user avatar
  • 205
5 votes
1 answer
118 views

Finding number of edges in giant component of a Uniform Random Graph

I had previously asked for help in clarification of use of Chebyschevs inequality in relation to a proof of the number of edges in the unique giant component $C_0$ in an uniform random graph. Thanks ...
user avatar
  • 693
0 votes
0 answers
17 views

Probability of randomly choosing identical graph from $G(500,2980)$

Let $G(500,2980)$ be the set of all graphs with $500$ vertices and $2980$ edges in the Erdos-Renyi model. We are given a specific graph (the details do not matter, but it is supposed to be the US air ...
user avatar
  • 463
2 votes
1 answer
33 views

What is the probability that these two edges share exactly one vertex?

Let $G_{n,m}$ denote an uniform random graph with $n$ vertices and $m$ vertices. Take two edges $e,f$ in $G_{n,m}$. What is the probability that these two edges share exactly one vertex? I was ...
user avatar
3 votes
1 answer
85 views

Incorrect proof: Number of edges in the unique giant component in an uniform random graph

I am working my way through a Random Graphs using the book "Introduction to Random Graphs" by Frieze and Karonski (which is available here: https://www.math.cmu.edu/~af1p/BOOK.pdf) I have ...
user avatar
  • 693
0 votes
0 answers
42 views

Randomly matchable and bipartite class

I am curios to know at least one example of the following graphs: i) an infinite class of bipartite graphs that is randomly matchable; ii) an infinite class of non-bipartite graphs that is randomly ...
user avatar
  • 571
1 vote
1 answer
43 views

Let $k \geq 3 .$ Show that there exists a graph on $n$ vertices with $\Omega\left(n^{1+\frac{1}{k-1}}\right)$ many edges and no cycle of length $k$.

Let $k \geq 3 .$ Show that there exists a graph on $n$ vertices with $\Omega\left(n^{1+\frac{1}{k-1}}\right)$ many edges and no cycle of length $k$. I’d like to ask some questions about the following ...
user avatar
  • 2,015
1 vote
1 answer
34 views

Expectation and variance of homomorphism density into Erdős–Rényi

I am reading "Large deviations for Random Graphs" by Sourav Chatterjee. The exercise (6.3) asks the following question. Let $G_{n, p}$ be the Erdős–Rényi random graph on $n$ vertices with ...
user avatar
  • 2,858
0 votes
0 answers
18 views

Looking for information of a random graph model (described as follows)?

I have the follwing random graph model, and looking for any work done concerning it. Given $n$ nodes $U=\{u_1,...,u_n\}$ and $m$ nodes $B=\{b_1,...,b_m\}$ randomly located at a 2-D plane (can be seen ...
user avatar
  • 31
1 vote
0 answers
41 views

What does large node mean?

I am reading "Social and Economic Networks" by M.Jackson. It is about random graphs. On Chapter 4, it says [...] the degrees of two neighbors [i.e. neighboring nodes in a graph] are ...
user avatar
  • 1,157
3 votes
0 answers
59 views

Probability of dense subgraph in a random graph

What is the probability that a random graph with $n$ vertices and degree sequence $\left(d_i\right)_{i=1..n}$ has a subgraph of $k$ vertices and density $\delta$? The random graph is typically ...
user avatar
1 vote
1 answer
59 views

Counting $P_k$ on random graphs

Let $n \in \mathbf{N}$ and $p \in [0,1]$. I want to compute the expected value of a random variable that counts the number of copies of $P_k$ in a random graph for some given $k \in \mathbf{N}$. ...
user avatar
1 vote
2 answers
69 views

Random graph contains no $C_4$ a.a.s.

Let $\epsilon>0$ as well as $n \in \mathbf{N}$ and $p=n^{-(1+\epsilon)}$. I want to show that a random graph in $G(n,p)$ a.a.s. does not contain a $C_4$ (I hope this is true?). My attempt was the ...
user avatar
0 votes
0 answers
14 views

Number of edges influenced (created or deleted) by inserting a point in a geometric graph

Let $\varphi$ be a locally finite configuration in $\mathbb{R}^d$ and let $G(\varphi)$ be any kind of geometric graph. Usually I would let $\varphi$ be the realisation of a Poisson Point Process. I am ...
user avatar
2 votes
1 answer
53 views

Probability that vertex is isolated

I just read about random graphs and the $G(n,p)$ model which has the following probabilistic properties. The probability space is given by $\Omega:=\{G \in \text{Graph} \ | \ G \ \text{has} \ n \ \...
user avatar
0 votes
0 answers
31 views

Number of errors in a sequence of ordered random variables (with application to density-threshold graphs)

Given $n$ real-valued random variables $X_1,\dots,X_n$ with expected values $\mu_1 \le \mu_2 \le \dots \le \mu_n$ and covariance matrix $\Sigma$ of their joint distribution. If we look at the ordered ...
user avatar
  • 41
1 vote
1 answer
41 views

how to compute the probability that a random graph has two components?

This question is an example in the book Introduction to Probability Models 11th edition (Sheldon M.Ross). 3.6.2 A random graph: A graph has $V$ nodes and a set $A$ of pairs of nodes in $V$ called arcs....
user avatar
  • 151
2 votes
1 answer
48 views

Is a uniformly random $r$-regular bipartite graph $r$-edge connected with high probability?

A graph is $r$-edge connected if the number of edges in a minimum cut is at least $r$. It is known that a random $r$-regular graph is $r$- vertex connected (which implies $r$-edge connected) with high ...
user avatar
3 votes
1 answer
51 views

The random graph $\mathbf{G}_{n,p}$ contains a cycle a.a.s. when $p=\frac{1-\theta}{n}$, $\theta\ll 1$

Consider the binomial random graph $\mathbf{G}_{n,p}$ and let $P=P_{n,p}$ denote the probability that it contains a cycle. When $p=\frac{c}{n}$ for a constant $0<c<1$, there exists a constant $q=...
user avatar
  • 3,244
2 votes
0 answers
34 views

Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?

A uniformly random $r$-regular bipartite graph is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular bipartite graph ...
user avatar
0 votes
1 answer
93 views

Approximation of combination $\binom{n}{k}k!$

Let $G$ be a graph with $k$ vertices and $e$ edges and let $X$ be the number of copies of $G$ in $G(n,p)$. The expectation of $X$ is $$ {n \choose k}\frac{k!}{|aut(G)|} p^e = \Theta \left( n^kp^e\...
user avatar
  • 507
3 votes
1 answer
62 views

Standard deviation of number of triangles in Erdos-Renyi uniform random graph G(n,m)

Erdos-Renyi $G_{n,m}$ random graph means that the graph is uniformly drawn from all graphs with $n$ nodes and $m$ edges. Let $X(e)=1$ if $e\in G_{n,m}$ and 0 otherwise. We write $$N(G_{n,m}):=\sum\...
user avatar
  • 927
0 votes
0 answers
69 views

Average degree of a connected graph

Quoting from this wikipedia article , "As connections are added to a network, there comes a point when $\langle k\rangle = \log N$, and the giant component absorbs all nodes, so there are no ...
user avatar
  • 663
4 votes
0 answers
46 views

The asymptotic formula on Poisson Branching Model

Consider the Poisson branching model with mean $c = 1$ and root Eve. For $n ≥ 3$, let $A_n$ be the event where Eve has precisely two children, Dana and Fan, and that the total tree size $T = n$. Let X ...
user avatar
2 votes
1 answer
52 views

Average degree of graph and degree

Let $G$ be a graph on $n$ vertices on which we impose that the average degree is a constant $d$. Is it true that as $n \to \infty$ the degree of each node will be a Poisson-distributed random variable?...
user avatar
  • 663
1 vote
0 answers
54 views

Connectivity of Random Geometric Graphs understanding the derivation

In the paper "On the Connectivity of Dynamic Random Geometric Graphs" ( https://arxiv.org/pdf/cs/0702074.pdf ) the authors state that the expected value for a node being isolated is $$E[X]=N\...
user avatar
  • 243
3 votes
1 answer
71 views

expectation value - box and balls

Problem: A box contains 2 green, 4 blue and 2 yellow balls, one ball is chosen $n$ times (independently, with repetitions). Let $X$ be the total number of chosen green balls, $Y$ be the total number ...
user avatar
0 votes
0 answers
23 views

How do Bayati manage to bound the following equation in his paper.

The paper in question can by found on https://web.stanford.edu/~bayati/papers/algorithmica.pdf. The equation in question is found on page 889 or pg51 of the paper. So let $\xi_r = O(\frac{rd_{max}^4}{...
user avatar
1 vote
0 answers
60 views

Minimum degree of a Random Graph

How do I find the limit distribution of the minimum degree of $G(n,p)$. Given that: $$p = \frac{\ln n + \ln \ln n + \ln \ln \ln n}{n}$$ Any hint or solution is very much appreciated. Thanks in Advance
user avatar
  • 495
4 votes
1 answer
101 views

The Expectation and Variance of the number of $k$ size sets containing exactly $m$ edges in $G(n, p)$

Let $X$ be the number of sets of size $k$ containing exactly $m$ edges in $G(n,p)$. Find $EX$ and $Var X$. My Attempt Given some indicators $X_1, \dots, X_{\binom{n}{k}}$ we have that $X = \sum X_i$. ...
user avatar
  • 495
2 votes
0 answers
151 views

Maximum Degree of random graph

Let ∆ be the maximum degree of $G(n, p)$. Find the limit distribution of ∆, where $p = n^{−1−1/m}, m ∈ N$. Something that I have studied regarding maximum degree for a random graph is that given $p$ ...
user avatar
  • 997

1
2 3 4 5
16