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.
876
questions
1
vote
1
answer
36
views
Bounding $ne^{-d}\left(\frac{ed}{K \log n}\right)^{K \log n}$
Apologies in advance for the nasty expression in the title. 😬
I'm working on Exercise 2.4.2 (p. 22) in Roman Vershinyn's High Dimensional Probability (not for a class; this is independent study). The ...
2
votes
0
answers
106
views
Large deviations for automorphisms of Erdős–Rényi
Let $p\ggg \frac{\log(n)}n$ and $1-p\ggg \frac{\log(n)}n$ and $G(n,p)$ be the Erdős–Rényi random graph. The parameter is chosen such that $G(n,p)$ and its complement don't have isolated vertices, and ...
- 1,853
1
vote
1
answer
21
views
Find a graph which is strictly balanced but not strongly balanced.
A graph G is called strictly balanced if all proper subgraphs H of G satisfies
$$\frac{|E(H)|}{|V(H)|}\ < \frac{|E(G)|}{|V(G)|}$$
A graph G is called strongly balanced if every subgraph H of G ...
1
vote
1
answer
55
views
Clarification about probability of critical threshold for cliques in random graphs.
I am reading these notes about finding cliques in $\mathcal{G}(n, 1/2)$ random graphs. The key result is that with high probability has size $2(1\pm o(1)) \log_2(n)$ with high probability. In order to ...
- 3,076
0
votes
0
answers
57
views
Probabilistic method, dependencies of triangles based at $x$
In the following notes
the author states, at page $64$, $4$th line of Theorem $8.10$, that
$$
\Delta=\sum_{\left(i,j\right):\ i \sim j}\mathbb{P}\left(B_{i} \wedge B_{j}\right) =
6{n-1 \choose 4}p^{9}
...
- 1,022
2
votes
2
answers
104
views
Proportion of vertices in components of size $k$ in Erdos Renyi
Consider $G(n,c/n)$ the Erdos-Renyi graph on $n$ vertices with the probability of having an edge between any two vertices is $c/n$. Let $X_{n,k}$ be the proportion of vertices in size-$k$ components. ...
- 104
0
votes
0
answers
12
views
Help understanding branching process result
Currently I am trying to understand the paper "Random Plane Networks" by E.N. Gilbert. In section 2 of this paper, he is deriving a lower bound for the expected number of points in the ...
- 95
1
vote
0
answers
18
views
How sensitive are maximum-size matchings to edge deletion in random graphs?
My question concerns the sensitivity of maximum-size matchings (and more generally maximum-size $k$-cycle collections) to deletion of an edge in the graph.
Given a graph $G$, let a $k$-cycle be a ...
- 11
0
votes
2
answers
41
views
Law of large numbers result for largest component in Erdos-Renyi
Let $G(n,\frac{p}{n})$ be the Erdos-Renyi random graph with $n$ vertices. Let $C(n,p)$ be the size of the largest component. It’s is known that when $p<1$ then $C(n,p)$ is of order $log(n)$ with ...
- 7
0
votes
1
answer
53
views
$G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges
I want to show that with probability converging to $1$, $G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges for some positive constant $C$. The hint for this is to use a greedy ...
- 448
0
votes
0
answers
19
views
Bounding probabilities of Indicator Variables in a Graph.
We have a graph G = (V, E). We look at a circle Ci with k edges. Each edge has a independent probability of 1/2 being marked.
I defined a indicator variable Xe which is 1 if marked and 0 else. So Xi ...
user1315096
1
vote
0
answers
21
views
Probability number of vertices in large component of Erdös-Renyi graph is close to survival probability
I am currently take a course on Erdös-Renyi graphs where we have the probability that two vertices are connected is given by $p = \lambda/n$ where n is the number of vertices of the graph G. Then one ...
- 114
1
vote
1
answer
42
views
General degree distribution of Soft Random geometric Graphs
I am interested in the degree distributions of Soft Random Geometric Graphs, and was wondering if anyone could give me some input. Soft RGG's are random graphs, which are constructed by first ...
- 95
0
votes
1
answer
22
views
Setting sampling probability when sparsifying a non-negative weighted graph
Given a set of $mn$ non-negative edges, with what probability should one keep every edge $w_{ij}$ if we want $\sim pmn$ non-zero weights in our sparsified and every edge is sampled with a probability ...
- 11
2
votes
1
answer
145
views
Can we do any better bijective mapping of a permutation series which is only bijective for a probabilistic subset of its input domain?
So we want to bijectively map one path to another. But depending on start and target node we can only choose from a subset of all transitions. It would look like this:
We also do not know where one ...
- 77