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

706 questions
Filter by
Sorted by
Tagged with
0answers
10 views

### Find the number of times the machine needs to use to find your current location for x% surety. ( shower thoughts question )

Guess, you are situated in a n*n grid in a random position. You have a machine that every time you use it. It selects a new position randomly and you can ask one of the 4 questions each time. The ...
1answer
64 views

### Number of graphs isomorphic with $K_{3,3}$

Find the number of non isomorphic directed graphs that after making all edges undirected are isomorphic with $K_{3,3}$. I need to use Burnside's Lemma - which says that number of orbits (non ...
0answers
31 views

### Heat kernel bounds on graph

I'm studying the heat kernel of the continuous time simple random walk $X_t$ on $\mathbb{Z}^d$. I know of the carne varopoulos bound for the heat kernel. But I'm lookong for a similiar bound for the ...
1answer
69 views

1answer
34 views

### Largest component in an Erdos Renyi graph

I need to find a $p$ for an Erdos Renyi graph with $n$ nodes so that the largest component in the graph has a size of at least $0.25n$. With simulation we have come up with an answer that $p = c/n$ ...
0answers
33 views

### Probability of x edges in a G(n,p) model

(i) Define the two Erd ̋os–R ́enyi models, $G(n,m)$ and $G(n,p)$, of random graphs. (ii) For a fixed value of $n$, describe each of the two models as a probability distribution on the ...
1answer
71 views

### The largest component of G(n, p)

Below is an question related to largest /giant component : Let $p >> \frac{1}{n}$. Prove that, for every $ε > 0$, a.a.s. the largest component of $G(n, p)$ has a size of at least $(1 − ε)n$. ...
1answer
73 views

### Clarification regarding Branching Process

So the question I am trying to solve is given below: Find the extinction probability of the branching process generated by $ξ$ ∼ Bin$(2, p)$. So I saw various approach has been used to solve this ...
0answers
33 views

### Is there an algorithm for generating a periodic geometric graph from a set of degrees?

Apologies I am a layman with regards to graph theory and am curious about the problem here as it might relate to materials science (hence 2 or 3 dimensions). References and paper recommendations are ...
2answers
40 views

### Probabilities and expectations for paths of a certain length

If we are given a random graph G, where edges are made with probability $\frac{1}{2}$. A) What's the probability that $2$ different vertices have a path of length 2 between them. B) What is the ...
0answers
37 views

### Estimations and equivalences of binomial coefficients

I'm trying to understand a proof of a lemma in Erdos and Renyi's 1959 paper entitled "On random graphs I." I'll write what they've written first and then describe the quantities and my ...
1answer
34 views

1answer
42 views

0answers
29 views

### Erdös-Renyi-like hypergraphs: threshold for connectedness

Consider an $N$-element set $X$ and a fixed number $k \ll N$. How many $k$-element subsets $X_i$ (hyperedges) of $X$ do I have to choose (at random) such that (i) $\bigcup_i X_i = X$ and (ii) the ...
1answer
87 views

### Limit in distribution for a random graph

I am stuck with this problem: If $R=2K_{3}\sqcup C_{4}$ and $p=\frac{c}{n}$ and if $Z$ is the number of copies of $R$ in $G(n,p)$. What is the limit in distribution of $Z$ as $n\rightarrow\infty$. Any ...
0answers
128 views

### Number of Isomorphic Trees

Given $p = cn^{−1−1/m}(1 + o(1)), m ∈ N, c > 0.$ Prove that the number of components in $G(n, p)$ isomorphic to a tree on $m + 1$ vertices converges to a $Pois$($\frac{c^m(m+1)^{m−1}} {(m+1)!}$)...
1answer
55 views

### Lemma regarding Balanced Graph

I am trying to prove a lemma which states that if Let $G= G_1 \sqcup . . . \sqcup G_k$ be a disjoint union of $k$ connected graphs. Prove that $G$ is balanced if and only if $ρ(G_1) = . . . = ρ(G_k)$ ...
1answer
34 views

### Relation between $k$ and $n$ in Alon and Spencer, 4th Edition, Section 10.3

On page 184, in section 10.3 of Alon and Spencer (The Probabilistic Method, 4th Edition), line -8, it is written: "Then $$n = \sqrt{2}^{k(1+o(1))}, ..."$$ At this point in the text, what is this ...
2answers
54 views

### Graph Theory - Binomial Random Graphs [closed]

Hi, could anyone provide any assistance on this? I have a feeling there's going to be a question like this on the exam and I really have no idea how to approach this concept. Any help on either part ...
0answers
21 views

### a natural way to measure the importance'' of the shortest path between pair of vertex

Suppose we are considering a graph G which is connected, unweighted, and undirected. Let P be the space of shortest path G, i.e., P contain the shortest path of all possible pair of vertex from G. I ...
1answer
64 views

### Connectivity of a graph in the Erdős–Rényi model

In the lecture series on random graphs that I'm watching teacher has made the following statements: if the probability of a branch between any two vertexes to be present in a graph is this function of ...
0answers
48 views

### Sharp threshold Probability

I have studied that.. If for $cp (n), c < 1,$ the graph almost surely does not have the property and for $cp (n), c > 1,$ the graph almost surely has the property, then $p (n)$ is a sharp ...
1answer
113 views

### Calculating the number of increasing properties of subsets of $\Gamma = \{1, 2, 3, 4\}$

Calculate the number of increasing properties of subsets of $\Gamma = \{1, 2, 3, 4\}$. I understand what an increasing property is, but I have no idea how to do this. Any hints would be great. Thanks....
0answers
15 views

0answers
50 views

### Why supersingular isogeny graphs are expander graphs?

I'm studying isogeny graphs and in particolar isogeny graphs of supersingular elliptic curves. In a supersingular isogeny graph $\mathcal{G}_\ell(p)$ nodes are supersingular elliptic curvers $E$ over \$...