Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
34 views

Expected number of connections in a random graph

knowing that: "It is called pure random graph to a graph of n nodes in which between each pair of nodes there is a connection with probability p and there is no such edge with probability 1-p." How ...
1
vote
0answers
26 views

Random Graphs - Planarity

If I take a Random planar graph with $V$ vertices and $E$ edges, I would like to know the probability that it remains planar if I add in another random edge, I realise that there is probably no simple ...
-2
votes
0answers
18 views

The Expected Value of a Random Graph [on hold]

My question is as follows: Proof that the expected value of a graph with $n $ Vertices is equal to $(n - 1)p$ $E[D] = (n-1)P $ $D$ = Random Variable
1
vote
2answers
47 views

Probability of getting from one point to another given probability that path is open

The points Woodstock and Tunbridge (W and T) are connected above in 3 different scenarios. p and q are the probability that the path is open. The question is what is the probability one can get from W ...
1
vote
1answer
25 views

Chromatic number of a subgraph of a random graph

Suppose that we have a random graph G(n,p) with $n$ vertices and each edge exists with probability $p = n^{-\alpha}, \alpha>\frac{5}{6}$. Prove that with high probability, say $1-\delta$, every ...
2
votes
2answers
40 views

Definability of subgraphs of random graphs

I'm new to model theory and I'm trying to solve this problem. Let $N$ and $M\subseteq N$ random graphs, is there a $\phi \in L(N)$ (where $L(N)$ is the language of graphs with a constant symbol for ...
1
vote
1answer
39 views

Expected number of vertices of a given degree in a random graph

How many vertices of degree exactly $\lfloor n/2 \rfloor$ does the random graph $G(n,1/2)$ contain? My calculations show that asymptotically this number is around $n^{1/2}$ but I feel like I have ...
1
vote
1answer
23 views

Can non-monotone properties of random graphs have a sharp threshold?

I'm working with a random variable on a random graph $G_{n,p}$ that has to do with the number of verticies of degree $1$, but it's not a monotone property (since adding edges can both make a vertex ...
1
vote
1answer
10 views

Specific subset of verticies are degree 1 in random graph probability

On a random graph $G_{n,p}$, I want to know the probability that some subset of verticies is degree one. Take it to be the verticies $A = \{1,2,\dots,k\}$. My approach for this is to notice that if ...
0
votes
1answer
44 views

Alternative to standard Erdos-Renyi random graphs that have better clustering and degree distributions?

Is there a widely accepted alternative to Erdos-Renyi random graphs that addresses their issues with 1) degree distributions not having heavy enough tails and 2) clustering coefficients being too low? ...
0
votes
0answers
8 views

Joint Distribution of graph-distances between vertices in Uniform Spanning tree

Let T be uniform spanning tree on complete graph $K_n$ (Or equivalently, uniform tree on n-vertices.) Suppose, I choose two vertices, say $u$ and $v$, and look at the graph distance between them in T. ...
1
vote
0answers
28 views

Probability of random graph being connected - block model

Let $n\in \mathbb{N}$ be given. Let us assume that the set of vertices is $V=[n]=\mathcal{C}^+ \cup \mathcal{C}^- \cup \mathcal{D}$, where the sets $\mathcal{C}^+$ and $\mathcal{C}^-$ stand for the ...
1
vote
1answer
13 views

How do I choose a set of numbers from a PMF with a specified total?

So basically I'm choosing a set of numbers from a probability mass function, (say binomial or scale-free). By which I mean I'm performing a weighted choose operation using the PMF as weights. However ...
2
votes
1answer
46 views

Number of Hamiltonian cycles in a random graph

I want to show that $\mu_{n}(p)$, the expected number of Hamiltonian cycles in the random graph $G(n,p)$, is given by $$\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$$ We can easily show that the number of the ...
1
vote
1answer
36 views

Limiting behavior of the expected number of Hamiltonian cycles in the random graph $G(n, p)$.

So we have that the expected number of Hamiltonian cycles in the random graph $G(n,p)$ is given by: $\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$ for $n \geq 3$. We now want to find lim$_{n\to \infty}\mu_{n}(...
0
votes
0answers
29 views

Generate a random bi-connected graph

I am trying to find an algorithm which will generate a random graph G, where G is a bi-connected graph too. An efficient algorithm is appreciated but I am looking for a brute force algorithm which ...
1
vote
1answer
49 views

How to show the small component is likely to be a tree in a random graph

I was just looking a book and the book said For a graph in supercritical regime (np > 1). For the small component (size s) not a part of giant component, it is a tree (which means the number of edges ...
0
votes
1answer
10 views

Bound on the tail of a Poisson branching process

I'm trying to understand this argument from "The Probabilsitic Method" book: Let $T_c$ be the time of extinction for a Poisson branching process with parameter $c$. The authors prove that $$P[T_c=k] =...
1
vote
1answer
29 views

There is probability $O(p^k)=O(n^{-k})$ that $C(v)$ has more than $k-1$ edges?

In this proof from "The Probabilistic Method" by Alon and Spencer, p.206, they argue that if $v$ is an aribtrary vertex with connected component of size $k$, then there is probability $O(p^k)=O(n^{-k})...
1
vote
1answer
58 views

Sparse random graph property

I'm taking a course which follows the book: High-Dimensional Probability by Roman Vershynin. There is an exercise (2.4.4) in the book which I have trouble with: Consider a random graph $G \sim G(n,p)$...
1
vote
1answer
12 views

Binomial converging to Poisson in branching process view of $G(n,p)$

I'm trying to understand this claim on page 205 of "The Probabilistic Method" by Alon and Spencer: Set $p=c/n$. A key observation is that $Z_1 \sim Bin[n-1, c/n]$ approaches (in $n$) the Poisson ...
1
vote
1answer
53 views

Cardinality of sets in a random graph generated from block model

Let $n\in \mathbb{N}$ be given. Let us assume that the set of vertices is $V=[n]=\mathcal{C}^+ \cup \mathcal{C}^- \cup \mathcal{D}$, where the sets $\mathcal{C}^+$ and $\mathcal{C}^-$ stand for the ...
2
votes
2answers
21 views

Probability graph will have some nodes with full-mesh connectivity.

There is a graph with $n$ nodes. This makes for $n \choose 2$ edges. We know for sure $l$ of these $n \choose 2$ edges are present and the rest are absent. What is the probability that for some $k<\...
12
votes
1answer
209 views

Random walk on thin ice?

My Question: Is the stochastic process which is described below a (special case of a) well-studied model? What kind of properties are known under which assumptions? Let's think of a random walker on ...
3
votes
3answers
118 views

Probability of segments connecting six points

Question: You can draw edges between any two vertices of an empty graph with $6$ vertices and you have the same chance of drawing each edge. Find the probability that "there exists three vertices that ...
0
votes
2answers
24 views

Determine conditions on pn such that the probability that a random graph has at least one triangle goes to zero as n increases

I'm currently struggling with an exercise about random graphs where is requested to determine the conditions on $p_n$ such that the probability that $G(n, p_n)$ has at least one triangle goes to zero ...
1
vote
1answer
20 views

Almost every graph has every vertex in a triangle?

I am looking at the random graph model $G(n,p)$ (i.e., the random graph on $n$ vertices where each edge appears independently with probability $p$). A property of almost every graph is a property $A$...
0
votes
1answer
12 views

Expectation of degree in Bernoulli graphs

Let $\mathcal{G}(n,p)$ be the Bernoulli graph ditribution of $n$ verteces with edge probability $p$. It is known that the degree distribution of such graphs is the binomial distribution. My question ...
1
vote
2answers
57 views

Generate random graphs with specific mean degree and mean edge weight

I need to generate random undirected graphs with the following characteristics: 24 nodes mean degree ranging between 1 and 23 mean edge weight ranging between 1 and 5 (weights must be integers) I ...
2
votes
1answer
36 views

Distribution of $(\langle X_i,X_j\rangle)_{i,j=1}^n$ for $X_k\sim\operatorname{Unif}(S^d)$

For two independent random variables distributed uniformly on a $d$-sphere surface ($X_1,X_2\sim\operatorname{Unif}(S^d)$), it is obvious that $$\langle X_1,X_2\rangle\sim -\langle X_1,X_2\rangle$$ by ...
1
vote
0answers
44 views

Is it true that a random graph's degree gives Poission distribution?

In many documents, it is said that a random graph's degree follows Poisson distribution. However, my numerical calculation contradicts with the fact. Assume a random graph whose number of nodes $N = ...
1
vote
1answer
26 views

How many independent even cycles in $G(n,m)$

In the random graph model $G(n,m)$, how many independent even cycles are there ? More precisely, let $C$ be a random variable which counts the independent even cycles. What is $$P(C=c)$$ for $c=0,1,\...
3
votes
1answer
49 views

Isoperimetric constant on random graph

I have the following problem. Show that there is a constant $c=c(p) > 0 $ such that almost all graphs in $\mathcal{G}_{n,p}$ verify the following property : for each subset $X \in V(G)$ with ...
0
votes
0answers
44 views

expected number of in- and out-going links in random PA graph

I am looking at an altered directed random graph of the preferential attachment model. Initial starting configuration is: $t=1,$ one node $v_1$. At each time step $(t+1)$ either we create a new node ...
6
votes
1answer
88 views

Probability that a graph is bipartite

Given the empty graph on $n$ vertices, we add $m$ of the $\binom{n}{2}$ possible edges, uniformly at random. What is the probability that the resulting graph is bipartite (equivalently, contains no ...
1
vote
1answer
45 views

Largest size of a complete bipartite sub-graph in a random graph

Let $G\in G(n,\frac{1}{2})$ be a random graph. What is the maximum number of edges of a complete bipartite graph that can appear as a subgraph in $G$ almost surely? Let's give an estimate in the ...
0
votes
0answers
20 views

Sampling probabilities for half-sparsification algorithm

https://dl.acm.org/citation.cfm?id=2948062 In their article(simple parallel and distributed algorithms for spectral graph sparsification 2016), Koutis and Xu gave a combinatorial algorithm for ...
2
votes
1answer
85 views

Perfect matching in random bipartite graph - with fixed probability

as a follow up from this question : Suppose that we have a simpler problem, where the probability $p$ is fixed. Of course we could use the above result to proove that almost every graph in the model ...
2
votes
0answers
59 views

Probability of being in same connected component

I would like to answer the following basic question: Let $V$ be a collection of $n$ vertices and fix $x$ and $y$ in $V$. Let $G$ be a random graph on $n$ vertices and $M$ edges. What is the ...
3
votes
1answer
55 views

Random graph with $p \ll n^{-1+\epsilon}$ a.a.s has no subgraph with $k$ vertices with at least $k+1$ edges

Let $G=(n,p)$ with $p \ll n^{-1+\epsilon}$ for all $\epsilon >0$. Then for each $k\in \mathbb{N}$ there are a.a.s no $k$ vertices with at least $k+1$ edges. Proof: We want to show $$\Pr(\...
1
vote
1answer
49 views

Binary trees constructed from the bottom up

I'm dealing with a set of random binary trees which I can't find referenced anywhere in literature. Computer scientists seem to prefer "random search trees" which is a different ensemble than mine (...
0
votes
0answers
23 views

Graph properties along trajectories in $G(n,m)$

I consider a graph that changes randomly over (discrete) time denoted by $(G_t)_{t=0}^{\infty}$ where I call $G_0=(V_0, E_0)$, $V_0$ being the vertex and $E_0$ the edge set my initial condition where $...
0
votes
0answers
22 views

Farkas lemma and matrix spectrum

I am currently looking at a problem of the following type : I have a matrix $\mathbf{M}\in\mathbb{R}^{N \times N}$ such that it's general term is given by $(\mathbf{M})_{ij}=z_i \delta_{ij} - A_{ij}...
0
votes
1answer
69 views

Clustering coefficient in a random graph model with transitivity

Reading the book Networks, by Mark Newman I found this exercise and I have some question about it: "We can make a simple random graph model of a network with clustering or transitivity as follows. We ...
1
vote
1answer
32 views

Connectivity of random network

I'm interested in the following (pretty open-ended) problem : Say we have some network of $n$ nodes, labeled by integers $i\in\mathbb{Z}/n\mathbb{Z}$. Each node $i$ chooses a random subset $\mathrm{...
2
votes
0answers
38 views

Are the eigenvectors of real Wigner matrices made of independent random variables with zero-mean?

I am trying to understand a portion of this paper [p. 3] and got stuck in the following statement, which sounded kind of trivial, but has been deceiving me for a while. Would you help me understand? ...
0
votes
0answers
12 views

Family of graphs that have approximation ratio = 2

My question today is about the approximation algorithms. Well, for Approx-Vertex-Cover problems , we know we can get ratio of 2 just by picking an edge and taking 2 endpoints of the same and ...
1
vote
1answer
72 views

Probability of an edge in directed random configuration graph

I am considering Bollobas' directed random configuration graph of size $N$, constructed by the following random algorithm: Draw a sequence of $N$ node-degree pairs $(j_1,k_1),...,(j_N,k_N)$ ...
3
votes
1answer
39 views

Variance of subgraph counts

I try to calculate the variance of the number of triangles in the uniform model $G_{n, m}$ where $m = \lfloor tN \rfloor$ for $t \in (0,1)$ fixed. I think the variation is $O(n^3)$, but I can not show ...
0
votes
1answer
44 views

Regularity of Erdos Renyi graph

I am interested to find out what’s the probability that an Erdos-Renyi graph $\mathcal{G}(n,p)$ is a regular graph? I believe this is a really hard question whose non-asymptotic results are probably ...