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

765 questions
Filter by
Sorted by
Tagged with
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?
1 vote
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 ...
39 views

• 43
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.
1 vote
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 ...
• 194
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 ...
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 ...
• 71
34 views

• 205
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 ...
• 693
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 ...
• 463
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 ...
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 ...
• 693
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 ...
• 571
1 vote
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 ...
• 2,015
1 vote
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 ...
• 2,858
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 ...
• 31
1 vote
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 ...
• 1,157
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 ...
1 vote
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}$. ...
• 195
1 vote
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 ...
• 195
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 ...
• 169
53 views

• 3,244
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 ...
• 526
93 views

• 927
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 ...
• 663
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 ...
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?...
• 663
1 vote
54 views

• 495
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$. ...
• 495
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$ ...