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.
886
questions
0
votes
0
answers
24
views
Confusion regarding small-O notation in a graph theory paper
Let $G$ be an $n$-vertex $d$-regular graph, where $d = n^{0.25}$. Choosing $s$ to be a constant, consider the quantity
\begin{equation}
((n - d)d - s)^2.
\end{equation}
Expanding this out, we can ...
- 367
1
vote
0
answers
29
views
Expected depth of random tree which randomly select the parent node for every node.
Consider using the following method to generate a tree:
Set node $1$ as the root;
For node $i$ ($i \in [2,n]$), randomly select the parent node in $[1,i)$.
(The expression of the interval here is ...
- 19
-3
votes
0
answers
29
views
Writing the equation that makes the meta log [closed]
How to write the equation that will make me the meta logo ? An equation, if I put it in desmos or GeoGebra, it will make me the meta logo (the same company of facebook) ?
5
votes
1
answer
123
views
Number of choices of edges in a regular graph
Let $G = (V, E)$ be an $n$ vertex $d$ regular graph and let $\epsilon$ and $\epsilon'$ be a subset of edges such that
$$\epsilon \subseteq E,~~\epsilon' \not\subset E.$$
Let $(u, w) \in \epsilon$.
...
- 367
0
votes
2
answers
52
views
Expected number of edges required for a graph to have a triangle.
I am considering graphs on $n$ with edges added iid randomly with probability $p$.
I have come across this post for the expected number of edges for a graph to have a triangle. In the question, they ...
1
vote
0
answers
59
views
Watts-Strogatz model: no edge from $p = 0$ graph should exist in $p = 1$ graph?
I'm trying to implement the Watts-Strogatz model for small-world networks. My understanding is that the procedure is as follows:
1. Start with a Regular Graph:
Begin by creating a ring lattice where ...
- 4,300
0
votes
1
answer
32
views
Bound on Joint Discrete and Differentialy Entropy
I am looking at bounding the entropy of a graph ensemble, and have run into the following issue: Let $X = (X_{12},...,X_{(n-1)n})$ be a vector of $\{0,1\}$ dependent random variables, and $R = (R_1,......
- 105
0
votes
1
answer
29
views
Vertex deletion and reconstruction in MST: boundedness of new degrees
I came across the following question related to graph theory as part of a research in statistics that I am working on.
Consider an Euclidean minimum spanning tree $T$ in $\mathbb{R}^d$ made of $n$ ...
- 109
2
votes
1
answer
105
views
Is there an efficient algorithm to sample a connected DAG uniformly at random?
I would like to sample weakly connected DAGs on $n$ labelled vertices uniformly at random. Is there an efficient (polynomial time) algorithm for this?
I could sample a graph with some probability $p$ ...
- 483
1
vote
1
answer
28
views
$\epsilon$-regular almost surely
Let $G\sim G(n,p)$ and $\lambda>0$ a fixed constant. Let $V_n$ be the vertex set of $G$. Show that:
For all disjoint $A_n,B_n\subset V_n$ with $|A|,|B|\geq n\lambda$, $(A_n,B_n)$ is $\epsilon$-...
- 197
0
votes
1
answer
27
views
Find $K_r$-subdivisions in random graphs
I saw the following exercise in Shapira's note, page 22-23.
Prove that with high probability, $G(n,1/2)$ does not contain a $K_t$-subdivision (also called topological minor) with $t=10\sqrt n$, but ...
- 928
1
vote
1
answer
40
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
108
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,803
1
vote
1
answer
27
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
59
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,086
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,056
2
votes
2
answers
110
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
42
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
60
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 ...
- 702
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
22
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
50
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
26
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 ...
- 21
2
votes
1
answer
146
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 ...
- 107
1
vote
0
answers
34
views
Sharp thresholds in bipartite graphs
I have this problem:
A random bipartite graph $G(n, n, p)$ is constructed by taking two sets of nodes $L, R$, each of size $n$. For any $u \in L$ and $v \in R$, the probability that the edge $(u, v)$ ...
- 65
1
vote
1
answer
43
views
How many random bidirectional edges do we need to fully connect a graph with $V$ vertices?
Given an empty graph with $V$ vertices.
For each vertex we pick one random vertex and connect them with a bidirectional edge. (could also be connected to itself)
After done this for every vertex we ...
- 107
1
vote
1
answer
62
views
Expected number of connected components if a graph constructed out of two perfect matchings
Let $|V| = n$, an even number of vertices, and let $M$ be a perfect matching on these vertices. Suppose we choose uniformly at random a permutation $\pi$ from the symmetric group $\mathbb{S}_n$, and ...
- 479
1
vote
1
answer
45
views
Probabiltiy of colinear points for a matrix composed of vertices
I was hoping to get some help to not only solve the problem but also identify what branch of math this would fall under (and hopefully improve my tags). The problem goes like this:
Say there is some ...
- 33
0
votes
1
answer
36
views
Sampling variance of edge density of subgraphs
I would like to evaluate the mean and variance of the edge density for subgraphs obtained by repeatedly subsampling nodes.
Specifically, suppose we have an undirected graph $G$ with $N$ vertices and ...
- 765
2
votes
0
answers
54
views
In search of a model to describe worm behaviour
For my bachelors thesis I am working with tubifex worms, and trying to develop a graph theoretical model that can help explain some mechanical and dynamical properties of the worms once they have ...
- 95
1
vote
1
answer
63
views
How to solve following binomial equation to get the assortivity?
Proving Assortativity r from Symmetric Binomial Distribution
Consider the symmetric binomial form given by the equation:
$$e_{jk} = N \binom{j+k}{j} p^j q^k + \binom{j+k}{k} p^k q^j$$
where $p+q=1$, $\...
0
votes
0
answers
39
views
Sequence of degrees of a graph with two colors
With respect to the graph
Another concept central to an understanding of fractional isomorphism is that of the iterated degree
sequence of a graph. Recall that the degree of a vertex $v\in G$ is the ...
user208465
0
votes
2
answers
127
views
Number of triangles in Erdös-Renyi graph
For each ${n}$, let ${(V_n,E_n)}$ be an Erdös-Renyi graph on ${n}$ vertices with parameter ${1/2}$ (we do not require the graphs to be independent of each other).
If ${|T_n|}$ is the number of ...
- 1,111
0
votes
1
answer
45
views
Does this simple model have a name?
For my thesis I created a simple random graph model and studied some of its properties, and I was wondering if this model has a name so I can look into it further.
The model essentially takes the ...
- 95
0
votes
0
answers
13
views
Using graphs to quantify the structure/pattern or correlation among the elements of supposedly random matrix
Let's say I have a supposedly random real symmetric matrix. How to use graphs to quantitatively (with a numerical focus) examine any structure/pattern or correlation among its elements ?
- 33
0
votes
0
answers
44
views
Kullback-Leibler Divergence between a random variable and the product of its entries
Problem Statement
I'm currently working with a result about Kullback-Leibler divergence. Let $X$ be an discrete random variable taking values in $\mathcal{X} := \{0,1\}^p$, with $X = (X_1, X_2,...,X_p)...
- 105
0
votes
0
answers
62
views
Using Janson inequality to the probabillity that all vertex belongs a triangle
I am working on a random graphs problem, which is stated as follows:
Prove that there exists some positive constant $C$ such that with high probability (w.h.p.), every vertex belongs to a triangle in ...
- 419
1
vote
0
answers
74
views
Property of vertices in random graphs
For a random graph $G\sim G\left(n,p\right)$ with probability $p$, for every vertex $v$, I need to prove that with high probability, $X=\deg\left(v\right)$ satisfies the condition $\left|X-np\right|\...
- 33
0
votes
1
answer
57
views
How to compute the variance of the vertex degree in $G(n,1/2)$?
Consider the random graph $G(n,1/2)$ and let $d(v)$ be the degree of the vertex $v \in V(G)$. By considering the indicator RV $X_w$ for the evenet $\{v,w\} \in E(G)$ it is easy to see that
$$\mathbb{E}...
- 4,224
1
vote
0
answers
23
views
What is the expected distribution of sphere sizes in random graphs with constant degree?
Let $G=(V,E)$ be a random undirected, unweighted graph where each vertex $v\in V$ has degree $n>1.$ Let the $k$-sphere $S(v_0,k)=\{\,v\mid v\in V,\;d(v,v_0)=k\,\}$ of $v_0$ be the set of vertices ...
- 9,387
0
votes
1
answer
51
views
Question about analyzing greedy algorithm for the max cut problem in random graphs
In https://lucatrevisan.github.io/teaching/bwca17/lectures/lecture02.pdf (Lemma 6), the professor claimed that:
"With high probability over the choice of $G$ from $G_{n,\frac{1}{2}}$, the greedy ...
- 1
0
votes
0
answers
15
views
Analytical Proof of Random Failure Tolerance in Scale-free Network
I aim to demonstrate that scale-free networks exhibit greater resilience to random failures compared to random networks. Are there any analytical approaches available for proving this assertion? ...
- 1
1
vote
2
answers
121
views
A doubt about almost all graphs
I am currently trying to understand the paper “On the chromatic index of almost all graphs” by Erdős and Wilson. I have two doubts, I’d be grateful if someone could explain them to me. This is part of ...
- 125
2
votes
0
answers
86
views
Diameters of random bipartite graphs [closed]
Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
- 39
0
votes
1
answer
112
views
Probabalistic Method: Using Janson' inequality to estimate the probability of existence of a $4$-clique
Let $c > 0$ and set $p := \frac{c}{n^{2/3}}$. Use Janson's Inequality to find a function $q(c): \mathbb{R}_{>0} \rightarrow (0,1)$ such that
$$\mathbb{P}\left[ \text{$G(n,p)$ contains no clique ...
- 4,224
3
votes
1
answer
150
views
Probabilistic Method: Almost every random graph contains all graphs on $k$ vertices as induced subgraphs [duplicate]
Let $k_0 \in k_0(n) \subset \mathbb{N}$ be such that
$${n \choose k_0} 2^{-{k_0 \choose 2}} < 1 < {n \choose k_0 - 1} 2^{-{k_0 - 1 \choose 2}}$$
and let $k = k_0 - 4$. Show that
$$\mathbb{P}\...
- 4,224
0
votes
0
answers
127
views
When does a random geometric graph become connected?
Fix $n\in \mathbb N$ and let $X_1,\dots,X_n$ be i.i.d uniform random points in $[0,1]^2$. For $r\in \mathbb R$ consider the (random) geometric graph $\mathcal G _r(X)$ with vertices $X=\{X_i\}$ and ...
- 943
4
votes
1
answer
294
views
Expected graph edit distance between two random graphs
Consider Erdos-Renyi random graphs $G(n,p)$.
Let us independently sample two graphs $G_1$ and $G_2$ following $G(n,p)$.
What is the expected graph edit distance (GED) between $G_1$ and $G_2$?
Since ...
- 2,170