A random graph is a graph 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$.

learn more… | top users | synonyms

0
votes
0answers
30 views

Size of the connected components

Assume that we have a disconnected graph with a random number of connected components. Is there any bounds/distribution on the size of these connected components (the number of vertices). The degree ...
0
votes
0answers
11 views

Cardinality of maximum independent set for a given degree distribution

Consider undirected graph $G(V,E)$. Assume that $f_n(k)$ be the probability mass function of degree of a vertex in $G$. Further, assume that $f_n(k)$ is an strictly decreasing function of $k$ with ...
1
vote
1answer
25 views

Probability of dominating set in random balanced tournament

I'm trying to estimate some probability in a random tournament, and I know that what I have is false, as it leads to contradicting results published some 40 years ago. But I don't know where the ...
1
vote
1answer
19 views

Graph Theory: Conditional Expected Value of Product of two Random Variables

Consider a graph with $n$ vertices, where each edge between any two vertices is independently drawn with probability $p$. Let $D_i$ be the degree of vertex $i$. What is $E[D_i \cdot D_j]$? Here is ...
0
votes
1answer
61 views

Watts-Strogatz graphs

I'm stuck with this particular question. Can someone explain/help me? Suppose we construct a graph in $WS(n,k,p)$, starting from the n vertices in a ring, where each vertex is connected to its first ...
2
votes
0answers
54 views

ER graphs, expected number of triangles incident to one vertex

I'm really sorry for this question. I'm new to a graph theory, and I hope you will help me to understand one statement. Consider $ER(n,p)$ graph with $n \geq 3$ and $p \in [0,1]$. The statement ...
0
votes
1answer
24 views

Subgraph isomorphism in random graphs. What am I forgetting?

We are asked to calculate the expected number of embeddings of graph $H$ in graph $G$. $G$ is a graph on $n$ vertices. Between each pair of vertices, with probability $p$ there is a blue edge, and ...
1
vote
0answers
15 views

Scale-free property of random graphs

From this Wikipedia page, I gather that when the degree distribution of a graph obeys the power law, the graph is termed 'scale-free'. I would like to know the reason for this term. What has scaling ...
0
votes
0answers
16 views

How to find embeddings of 3-cycle in random graphs?

I'm not sure whether this is the correct place to ask, but we have an assignment for uni as posted below. Before I start searching the large space of papers that exist on embeddings in a random graph. ...
0
votes
0answers
36 views

Bond percolation probability on a Bethe lattice

I derived the bond-percolation probability for a Bethe lattice and my result disagrees with a seemingly reputable reference by Albert & Barabasi (see below). I would be happy if somebody could ...
3
votes
0answers
29 views

The probability of having a perfect matching in a bipartite graph

Say we have a bipartite graph $G$ with two sets, $\{x_1,\dotsc,x_n\}$ and $\{y_1,\dotsc,y_n\}$. For each pair $xy$, there is an edge with probability $p$. Then, what is the probability of having a ...
3
votes
2answers
27 views

Looking for information about a random graph model

I have the following random graph model, and I am looking for its name and/or any work done concerning it. Given $n$ nodes, $\{v_1,...,v_n\}$, and $n$ timesteps, proceed as follows: On the $k$th ...
0
votes
0answers
13 views

How to show a random matrix has large spectral gap?

If I know $Y$ is a random d-regular bipartite graph (tanner code in coding theory), can I show $Y^TY$ has large spectral gap with high probability? More specifically: If I know $Y=AX \in ...
1
vote
0answers
20 views

Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of: (A) a random graph (e.g., Erdos-Renyi graph), (B) a small-world graph ...
1
vote
0answers
102 views

Stochastic dominance of Binomial and Poission

In order to investigate the size of the cluster of a given vetex in a random graph I need to use a fact about stochastic dominance that I don't know how to prove. Namely, I am looking for a proof of ...
0
votes
0answers
20 views

Graph Theory: small-worldness

I have two groups, each including several networks. I calculate following three network measures for each network clustering coefficient characteristic path length small-worldness (by comparing 1 ...
0
votes
0answers
15 views

The minimum degree of G(n,p) with p=(1+o(1))ln(n)/n

It is not difficult to show, using standard concentration bounds, that for $G\sim G(n,p)$ with $p=f(n)\cdot\ln{n}/n$, $f(n)\ge 1+\varepsilon$, $\varepsilon>0$ constant, that $G$ is nearly regular. ...
0
votes
1answer
36 views

Question on the proof of the upper bound of girth in dense graph.

I have trouble understanding the proof of the following theorem from Upfal's Probability textbook pg 134 Theorem: For any integer $k \geq 3$ there is a graph with n nodes, at least ...
1
vote
2answers
22 views

Why is the maximum cut of an undirected graph at lest 1/2 the number of edges in the graph?

In Upfal's Probability textbook he claims in Theorem 6.3 Given an undirected graph G with n vertices and m edges there is a partition of V into two disjoint sets A and B such that at least m/2 edges ...
1
vote
1answer
37 views

Components in random graphs $G(n,p)$

My question involves two constants which I don't know how to compute, but it probably doesn't matter. The constant $C>0$ is rather small, say $C=e^{-1000}$. The constant $K$ is larger than $1$. I ...
2
votes
0answers
36 views

Large Random Graph is Surely Connected

I'm trying to prove that for a random graph on $n$ vertices with edge-probability $p \in (0, 1)$ is almost surely connected as $n$ grows large. I've tried making an argument using the probability of ...
0
votes
0answers
16 views

Statistics, distributions and graphing

Lets say that you have data containing one variable - the waiting time between each car passing from 1200 hours... so you have something like 23, 54, 26, 8, 2, 59 etc what is the best way to analyse ...
0
votes
1answer
31 views

Threshold for matchings in random bipartite graphs

In the calculation on pages 82-83 of the book on Random Graphs by Janson et al they calculate the threshold for matchings in the random bipartite graph $\mathbb{G}(n,n,p)$. They say that if ...
2
votes
3answers
36 views

Probability for 2 vertices to lie in the same component of a random graph

Consider $G(4,p)$ - the random graph on 4 vertices. What is the probability that vertex 1 and 2 lie in the same connected component? So far, I have considered the event where 1 and 2 do not lie in ...
0
votes
1answer
26 views

Generate random graph under centrality constraints

Is it possible to generate a random graph under centrality constraints? I am currently working on a project involving characterization of biological properties stemming from different centrality ...
2
votes
1answer
50 views

Probability of a cubic graph containing a perfect matching

Let $G_n$ be a uniformly random cubic graph on $n$ vertices (cubic=all vertices have degree 3). What's the probability $p_n$ that $G_n$ contains a perfect matching? Does it have a limit? Note that ...
0
votes
1answer
25 views

Attractors of a Random Boolean Network?

I need some direction on the topic of Random boolean networks (NK-boolean networks or Kauffman automata). I now some of the results like if K=1 the systems settles down to fixed points, if K=2 it ...
3
votes
2answers
51 views

Random walk on a tree

Consider a Cayley tree with coordination number 3 (http://en.wikipedia.org/wiki/Bethe_lattice). Consider two sites, $x$ and $y$, having a distance $k$ one from another. What is the probability that ...
5
votes
1answer
87 views

Almost every graph is asymmetric?

Here is a question: If i choose at random an isomorphism class of graph(no loops, undirected) on n vertices(with uniform probability on the set of such isomorphism classes), is the probability that ...
1
vote
0answers
46 views

Expected size of largest connected component in a random k-out digraph?

Given a digraph with n vertices and kn edges, where each vertex has k out-neighbors randomly chosen at uniform without loops, how would I go about figuring out the expected value of the size of the ...
1
vote
0answers
34 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
0
votes
0answers
56 views

A question on Chung-Lu model of random graph modeling

when I read this book chapter, I got confused on this statement on the first page: $$w_i=K\text{ when }i/n=BK^{-\beta+1}$$ Is $K$ a constant or a random variable? I guess it's a constant. What is ...
0
votes
2answers
65 views

What is the probability of a chain of a given length in a random graph?

Let $G$ be an undirected graph with $n$ nodes. An edge is randomly and independently drawn from each node to any of the other nodes. If some arbitrary node $a$ is chosen, what is the probability that ...
1
vote
0answers
21 views

Nearest node in a generation of a random graph

Assume I have a set of $n$ nodes that I want to define their pairwise distances. I also assume that a node $i$ is characterised by an exponential distribution with parameter $\lambda _i$ in the ...
1
vote
0answers
29 views

Deviation of number of cycles of length 4 in Erdős–Rényi random graphs.

I'm working on my homework and can't find any relevant information for this problem. Problem: Let $G(n, p)$ be Erdős–Rényi random graph. I need to find deviation of number of cycles of length 4 in ...
1
vote
1answer
69 views

Phase trasition of $f(x)$ on random graph $G(n,p(n))$

Random graph $G(n,p(n))$ and graph $H$, which shown below, are given. I'm in need to find $f(x) : f(x) > 0$, such as: if $lim_{n \to \infty}p(n)f(n) = 0$, then asymptotically almost surely G ...
0
votes
0answers
42 views

Nullifying columns of a matrix by nullifying rows

Let $A$ be a real rectangular matrix. Each column of $A$ is a nonzero vector. Now each row of $A$ is nullified with probability $p$, all independently of each other. What is the probability that ...
1
vote
1answer
78 views

Hypergraph rainbow colouring of $\{1 \dots n\}$ for $A = \{A_1, \dots A_k\} : A_i \subset \{1, \dots n\}$

We are given collection of sets $A = \{A_1, \dots A_k\}$, where each set $A_i \subset \{1,\dots n\}$. Colouring $\{1, \dots n\}$ into $s$ colours would be called 'rainbow' for given $A$, if $\forall ...
0
votes
1answer
34 views

Proof for k-connectedness of random graphs

I am really new to the theory of random graphs. It seems a lot of articles take for granted that: For $k\in\mathbb{N}\setminus\{0\}$ and $p\in(0,1)$ fixed, almost every graph in $G(n,p)$ is ...
0
votes
1answer
28 views

Bounds on the Neighborhood Size of a Random Vertex in $G(n,p)$

Let $G(n,p)$ be the Erdős-Rényi random graph model. I am interested in the regime $p = c/n$, where $c > 0$. Further, let $B_G(d)$ denote the neighborhood of depth $d$ of a randomly chosen vertex ...
1
vote
1answer
37 views

What kind of studies are this?

at this link there are quite a number of images reporting different patterns inside a circle: what kind of studies are this and does this belongs to a specific branch of the mathematics ?
0
votes
1answer
28 views

Question about consistency in the junction tree algorithm (graphical models

I have a question about consistency in graphical models. It is often stated that when running the junction tree algorithm on a clique (cluster) tree, the marginals of all nodes are locally and ...
1
vote
0answers
19 views

Random graphs: A random graph induces a distribution on each link. Do they uniquely determine the graph?

Let $G$ be a random graph with $n$ nodes, with the nodes numbered. $G$ induces a distribution in the set of all graphs of $n$ nodes and we can identify this distribution with $G$. Given the nodes ...
0
votes
1answer
27 views

How to calculate a line vector from a bunch of points.

I get a bunch of not really random points, which should be abled to formed a single line, the example looks like the following: In this sample, we could easily imagine there is a line formed by the ...
2
votes
0answers
38 views

How to compute the following sum?

How to compute the following sum? $$\sum_{k=1}^{\infty} \frac{k^{k-1} \cdot e^{-k}}{k!}$$ It is likely to be equal $1$ (there is an argumentation that goes back to random graphs). Moreover, i think ...
1
vote
0answers
19 views

Navigation in a graph

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. We define the graph metric $d$ for ...
3
votes
0answers
127 views

Extinction probability of binomial branching process tends to poisson one.

The folowing is stated and proved in the random graphs book by Luczak, Janson, Rucinski and this is on page 108 in the Giant component section. I can't understand why the conclusion follows from the ...
0
votes
1answer
75 views

Random Binary Search Tree, expected value of nodes with two children

In class, the professor showed that using a uniform random permutation $$ X_1,..., X_n$$ (each being i.i.d.) we can construct a Binary Search Tree by inserting the values in to the tree by their ...
1
vote
1answer
41 views

raBinomial distribution with dependent trials?

I need your help with following problem: String with n characters is given. For each character in string there is probability p that it is wrong. Now you take a sliding window of length k, k<= n, ...
1
vote
1answer
72 views

How to compute the average number of wedges and triangles present in the Erdős-Rényi random graph?

Let $ER_{n} (p)$ be the Erdős-Rényi random graph (see the second model in the link), where $p=\frac{\lambda}{n}$. Furthermore, let $W_{ER_{n}}$ be the number of wedges in the graph, and ...