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.
907 questions
3
votes
0
answers
50
views
Planted Matching in Hypergraphs
I’m working on the planted perfect matching problem in random $k$-uniform hypergraphs $k \ge 3$, and I’m stuck on rigorizing the impossibility (lower bound) side of what looks like the information-...
- 31
1
vote
0
answers
46
views
The permutation model is an expander with high probability
In the book Computational Complexity: A Modern Approach you can find the following problem
this is actually a multi-graph with loops. Their definition of expander and a hint are attached below
My ...
- 5,452
5
votes
1
answer
157
views
Is the set of critical values for percolation dense in $(0,1)$?
Given a locally finite, countably infinite connected graph, define its critical probability as
$$p_c(G):=\inf\left\{p\in (0,1]: (V(G),E(G)_p) \substack{\text{ contains an infinite connected}\\ \text{...
- 5,452
1
vote
0
answers
41
views
Linking probability with 3D space filling complete graphs
Problem. Let $t$ hard-core spheres of diameter $D$ be placed i.i.d. uniformly in the unit cube. Every pair is joined by a rigid cylinder of the same diameter $D$. Spheres and cylinders are mutually ...
- 11
1
vote
1
answer
97
views
Concentration of the number of triangles in a random graph with fixed number of edges
Given parameters $n$ and $p$ of an Erdos-Reyni random graph $G(n,p)$, one can estimate parameters such as the number of edges or triangles of the realized graph and show concentration results for ...
- 91
1
vote
0
answers
95
views
Proof explanation: theorem 4.1 from the book Random graphs Bollobas
In the proof of Theorem 4.1 of the book Random Graphs by B. Bollobas. Where it is written that
Suppose the graph $A$ and $B$ are such that $B$ is an $H$-graph and it has exactly $t$ vertices not ...
- 1,236
0
votes
0
answers
22
views
The factor graph corresponding to the posterior distribution
I am reading this paper and have a question about the factor graph of the posterior distribution in Figure 1. It looks like the authors never really define what that distribution is, and explain why ...
- 11
0
votes
0
answers
89
views
Conditional expectation of number of visited nodes in a depth-first search on a Galton-Watson tree
I have the following problem:
Given a Galton-Watson tree $T$ where the offspring distribution is $p_0 = p_2 = \frac{q-1}{2q}$ and $p_1 = \frac{1}{q}$ for some prime number $q \geq 3$.
Consider depth-...
- 1
1
vote
0
answers
67
views
The random graph $G(n,p)$ attains the minimum of graph discrepancy
I have read this statement from various articles:
By considering random graphs in $\mathcal{G}(n,1/2)$, it can be seen that the discrepancy of a graph on $n$ vertices can be as small as $O(n^{3/2}).$
...
- 393
2
votes
1
answer
150
views
Probability (or asymptotics) that $G_{n, p}$ is a forest?
In the binomial Erdős–Rényi model of random graphs, we are interested in random graphs where there are $n$ nodes and where each of the $\binom{n}{2}$ possible edges is independently added to the graph ...
- 11k
5
votes
3
answers
2k
views
What is the probability that the graph remains connected?
Consider the complete graph $K_4$ with four vertices; all vertices are connected by an edge to all other vertices. Suppose now that we flip an unbiased coin for each edge. If heads comes up, we leave ...
- 366
0
votes
1
answer
63
views
Probability for 2 vertices to lie in the same component of a random graph $G(4,p)$
To determine the probability that vertices 1 and 2 lie in the same connected component in the random graph $G(4, p)$ https://math.stackexchange.com/a/1176529/745350 obtained an answer$$p + p^2 (1 - p) ...
- 6,087
2
votes
1
answer
82
views
Understanding the regularization lemma and what can be said about graphs representing the real word by applying this lemma?
For the most part I understand the mathematical statement of Szemerédi's Regularity Lemma: it states that any large graph's vertices can be partitioned into k parts (groups) of equal or nearly equal ...
- 175
3
votes
1
answer
137
views
Expected height of random tree formed by merging
Consider the following random process. Starting with n active nodes, at each step choose two active nodes uniformly randomly, making one inactive and creating an edge between the two nodes. After ...
- 488
1
vote
0
answers
37
views
Proof of Theorem 3 Handbook of Large Scale Random Networks - Bela Bollobas, Robert Kozma
As part of proving that $C_1 ( G\left(n, \frac{c}{n}\right)) \leq (\rho(c) + \eta) n$ whp for $c > 0$ and fixed $\eta$ with $\rho(c)$ denoting the survival probability of the Galton–Watson ...
- 11