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.

496 questions
24 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 ...
17 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
43 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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? ...
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. ...
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 ...
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 ...
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 ...
35 views