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
6 views

Function/algorithm to generate a random walk on a graph

I'm looking for a graph function or an algorithm that can generate a random fluctuating random walk that will eventually converge between the value of y = 0 and y = 1, more or less after a number of ...
0
votes
1answer
28 views

Prerequisites for Random Graph Theory

I would dearly love to know the prerequisites for self-studying Random Graph Theory and Percolation Theory in Probability. My knowledge currently involves: Basic probability concepts: the axioms, ...
0
votes
1answer
28 views

How to proove Hammer Split-graph Theorem?

Let $G=(V,E)$ be a Split Graph with $|V| \geq 4$. Then how to prove that: No induced sub-graph of G with 4 Vertices is a cycle with length 4 OR a pair of not incident edges? Well it must be from ...
0
votes
1answer
29 views

Degree distribution of the line graph of an Erdös-Rényi random graph

An Erdös-Rényi random graph is a graph, which consists of N nodes and where each link between them is present with probability p. It comes natural then that the pdf giving the probability of a node in ...
3
votes
0answers
21 views

Joint distribution of degrees of Erdös Renyi random graph

The marginal degree distribution of any particular vertex is $$Bin(n-1,p)$$ in an Erdös Renyi random graph G(n,p). Denoting the degrees of the n vertices as d1,d2,...,dn, can you please let me know ...
0
votes
0answers
38 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
15 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
28 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
26 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
73 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
60 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
27 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
17 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
44 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
30 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
30 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
14 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
22 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
111 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
23 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
19 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
38 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
24 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
39 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
39 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
35 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
39 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
30 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
52 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
34 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
52 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
89 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
50 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
59 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
67 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
32 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
44 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
79 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
35 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
31 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
30 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
29 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 ...