The random-graphs tag has no wiki summary.

**0**

votes

**0**answers

66 views

### Gromov-Hausdorff distance measure between minimum spanning trees

I am trying to compare minimum spanning trees through time. I have two questions:
1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...

**0**

votes

**0**answers

16 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 ...

**2**

votes

**2**answers

148 views

### Probability of relations in network

Imagine, i have a predicate $\text{friends}(x_1, x_2)$ and I know that $p(\text{friends}(x_1, x_2)) = p_2$. If I generate a world of $n$ people ($x_1$ to $x_n$), I expect there to be $\binom{n}{2}p_2$ ...

**1**

vote

**1**answer

171 views

### Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...

**8**

votes

**2**answers

584 views

### random category theory

This question is in some sense dual to the one asked in Is there an introduction to probability theory from a structuralist/categorical perspective? since contrary to the OP who asks for references ...

**3**

votes

**1**answer

103 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 ...

**7**

votes

**1**answer

196 views

### Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...

**4**

votes

**2**answers

192 views

### Statistics of strongly connected components in random directed graphs

I'm interested in the statistics of strongly connected components in random directed graphs. However, I'm unable to find any results on this, partly because I don't know the terminology to search for.
...

**4**

votes

**1**answer

75 views

### Probability of a giant component existing in a $G(n,p)$ random graph with $p=\omega(\frac 1n)$

Consider a random $G(n,p)$ graph where $p=\omega(\frac 1n)$, and let $x$ denote the probability that the graph has a connected component of size linear in $n$.
It is well known that $x$ tends to $1$ ...

**1**

vote

**0**answers

110 views

### Multiple Bipartite graphs and matchings

I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...

**1**

vote

**2**answers

264 views

### Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...

**1**

vote

**1**answer

198 views

### Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.
I know one way to prove the threshold of a perfect matching is ...

**1**

vote

**2**answers

184 views

### Proving a random bipartite graph contains a perfect matching

I have the following problem
consider a random bipartite with vertex classes $A$ and $B$ of size $|A|=|B|=\mathrm{log}^{2}(n)$ graph in which every possible edge is chosen independently with ...

**0**

votes

**0**answers

62 views

### Computation on Random Bipartite graphs

I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...

**1**

vote

**0**answers

67 views

### Matchings in random bipartite graphs

I was wondering if anyone could point me in the direction of a text or paper which would help deal with the following problem
Suppose i am given a $K_{\mathrm{log}(n)} \times K_{\mathrm{log}(n)}$ ...

**1**

vote

**1**answer

154 views

### Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let
$p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$.
I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...

**4**

votes

**0**answers

194 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$.
Assumptions about the graph: You may ...

**0**

votes

**1**answer

215 views

### Poisson approximation of random sub-graphs

I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...

**9**

votes

**5**answers

353 views

### Do there exist sparse graphs with large crossing number?

Does there exist a sequence of graphs $\{ G_n \}$ such that
$G_n$ has $n$ vertices,
the number of edges of $G_n$ is $O(n)$, and
the crossing number of $G_n$ is $\Omega(n)$?
In particular, do ...

**4**

votes

**1**answer

178 views

### Expectation of ratio of functions of i.i.d. Bernoullis: a concentration question

Consider the following $n \times n$ symmetric matrix of i.i.d. Bernoulli random variables, $X_{ij}$. For $i=1,...,n$ and $i<j\le n$. Let $X_{ij} \sim \text{Bernoulli}(p)$ when $i \ne j$ ($p$ ...

**2**

votes

**0**answers

37 views

### “drift” of a random graph $G(n,p)$ with $p=\alpha\ln{n}/n$

Suppose $G\sim G(n,p)$ with $p=\alpha\ln{n}/n$ for some large constant $\alpha$. I wish to show a certain "drift" property of $G$, which can roughly be phrased as follows: if $u$ is "not that far" ...

**3**

votes

**2**answers

153 views

### Independent Sets in random geometric graphs

I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent ...

**2**

votes

**1**answer

212 views

### Finding loops and double edges ASAP in configuration model random graph

A common approach (at least in theory) to generating a random $n$ vertex graph uniformly subject to having a given (feasible) degree sequence $(d_i)_{i = 1}^n$ is to use the configuration model, i.e. ...

**2**

votes

**1**answer

71 views

### Hamiltonicity of random graphs with high girth

We say that $G\sim G_{n,f}$ (for $f=f(n)$) if $G$ is chosen uniformly at random from all graphs on $n$ vertices with girth $g(G)\ge f(n)$. Is there any threshold function $F(n)$ such that when $f\ll ...

**11**

votes

**0**answers

361 views

### First passage percolation on a random geometric graph in the large connectivity limit

Let $V_\rho\subset\mathbb{R}^2$ be a point set in the plane obtained from a Poisson process of density $\rho$. The random geometric graph $G_\rho$ is obtained from $V_\rho$ by connecting points that ...

**3**

votes

**1**answer

114 views

### limiting empirical spectral distribution of the Laplacian matrix on an Erdos-Renyi graph?

Let $G$ be an Erdos-Renyi random graph (i.e. an edge ($ij$) exists with probability $0 < p < 1$ and all edges are independent). Let $L$ be the Laplacian matrix of this graph (i.e $L=D-A$, where ...

**3**

votes

**0**answers

94 views

### Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large.
An agent can move in the area at ...

**0**

votes

**2**answers

89 views

### different way of selecting a random graph

Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this ...

**6**

votes

**2**answers

150 views

### Convergence on a random graph

Assume a directed graph $G = (V,E)$ is drawn from a random graph distribution, for instance Erdős–Rényi's $G(n,p)$ (but with directed edges). Let $S:V\rightarrow\mathcal{P}(V)$ be the direct ...

**4**

votes

**1**answer

238 views

### Expected number of connected components in a random graph

For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value?
I'm specially interested in what happens for small values of p, ...

**1**

vote

**0**answers

54 views

### Simulation of disassortative random graphs

Recently I have been trying to find a succinct algorithm for generation of disassortative networks. The best I have found is the algorithm by Newman described in his paper "Mixing patterns in ...

**7**

votes

**0**answers

99 views

### Longest induced cycles in random geometric graphs near criticality

We make a random geometric graph $X(n;r)$ as follows. Choose $n$ points uniformly, independently, in the unit square $[0,1]^2$, for vertices, and then connect a pair of vertices $\{ p,q \}$ by an edge ...

**4**

votes

**0**answers

58 views

### Cycle removal process

Consider the following stochastic process for generating a forest: start from a complete graph on $n$ vertices and proceed to repeatedly remove the edges of uniformly chosen cycles. Formally, let ...

**3**

votes

**0**answers

177 views

### Hitting edges in graphs at random and let them die with honor

Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit ...

**7**

votes

**1**answer

191 views

### Erdős-Renyi graph restricted to largest connected component

Suppose we have an instance of Erdős-Renyi $G(n,p)$ graph with $p = d/n$. Thus the expected node degree is $d$ which we will fix, while letting $n \to \infty$. Then, there will be more than one ...

**5**

votes

**6**answers

445 views

### Random planar, bipartite graphs

I have a need to generate random planar graphs none of which have an odd cycle,
i.e., bipartite graphs.
I know there is a substantial two-decade literature on random planar graphs, little with which I ...

**3**

votes

**0**answers

69 views

### Using Crump-Mode-Jagers processes to get logarithmic bound on a random tree height

I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I ...

**3**

votes

**1**answer

337 views

### Expected Value for a Connected Graph

Consider a connected graph of N nodes.
Assign randomly to each node a distinct number from 1 to N.
For each node consider the maximum adjacent value or itself if all adjacent values are smaller.
...

**2**

votes

**3**answers

364 views

### random networks and prime numbers

I have been studying networks recently and accidentally came up with an heuristic approach towards the distribution of prime numbers. The prime number theorem states that
$\pi(n)\sim n/log(n)$ for ...

**4**

votes

**3**answers

179 views

### Tracking automorphism groups of graph processes

Start with an edgeless graph on $n$ labeled vertices, and note that the automorphism group is $\Sigma_n$, the symmetric group on $n$ elements. Now imagine that we randomly start throwing in all of the ...

**0**

votes

**0**answers

65 views

### Maximum Independent set of sparse graphs with few triangles

Notations used
$\alpha(G) = $ Max sized independent set of graph $G$.
$n(G) = $ Number of vertex in graph $G$.
Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being ...

**3**

votes

**0**answers

66 views

### Quasi-isometry of giant components in Erdos-Renyi graphs

Take two independent random graphs $G_1, G_2$ in the $G(n,p)$ model for $p = \frac{c}{n}$, $c > 1$ (the question probably makes sense also for $c=1$). Each of them will have a unique giant ...

**3**

votes

**0**answers

142 views

### Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, ...

**5**

votes

**0**answers

145 views

### Behavior of eigenspaces of adjacency matrices of random graphs (not via perturbation theory)

For the sake of discussion, let us say that we have the adjacency matrix $A$ of a graph, on $n$ nodes, from a stochastic block model with 2 blocks. Another name for this (usually used in computer ...

**7**

votes

**0**answers

134 views

### Can two random graphs be metrically embedded into one another?

Let $X, Y$ be two random graphs on $n$ vertices (say, in $G(n, p)$ model for some $p$). Can anything (expectation, value with high probabiity, ...) be said about $D(X, Y)$, where $D$ is the minimal ...

**1**

vote

**1**answer

598 views

### Probability of two vertices being connected in a random graph

Consider a random directed graph with $N$ vertices where each vertex $v$ has exactly one link to some vertex (maybe to itself) $u$ with known probability $a_{vu}$. What is the probability of ...

**-3**

votes

**1**answer

193 views

### adjacency matrix of random geometric graphs [closed]

Consider a graph with N nodes. All nodes are distributed as a Poisson point process with density of λ in a L*L area. There is an edge between two nodes if and only if the distance between them is less ...

**2**

votes

**0**answers

97 views

### Reachability in dynamic random graphs

There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. ...

**11**

votes

**3**answers

616 views

### What fraction of n-point sets in the unit ball have diameter smaller than 1?

This question is inspired by a recent talk by Matt Kahle on random geometric complexes.
Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean ...

**2**

votes

**2**answers

288 views

### Random graphs require O(n log(n)) edges until they are almost certainly fully connected - what are more concrete boundaries ?

As far as I understand my literature, the probability of a random graph being fully connected tends toward one as the number of edges approaches a value of size $O(n \log(n))$
The way I read this, ...