The random-graphs tag has no wiki summary.

**1**

vote

**1**answer

136 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

175 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

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

**7**

votes

**4**answers

266 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

132 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

31 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

**1**answer

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

**1**

vote

**1**answer

178 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

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

**9**

votes

**0**answers

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

**2**

votes

**1**answer

83 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

91 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

84 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

137 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

149 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

50 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

95 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

55 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

168 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

149 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

419 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

53 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

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

**3**

votes

**3**answers

357 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

173 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

59 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

60 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

129 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$, ...

**4**

votes

**0**answers

113 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

124 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

496 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

169 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

89 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

603 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

245 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, ...

**1**

vote

**0**answers

61 views

### Can this application of the moment closure method to epidemics on networks be made rigorous?

Short version: Consider the SI model of infectious disease spread on a random graph $G$ with a given degree sequence. Let $j$ be a vertex and let $i$ and $k$ be two of its neighbors. If $G$ ...

**2**

votes

**1**answer

258 views

### Removing edges from Erdős–Rényi graph to make two nodes disconnected

Consider a Erdős–Rényi graph on $n$ nodes, say $1,2,\ldots,n$, ($n\geq 3$) such that the probability of edge between any two nodes is $c/n$. I wish to know if there is a result that says
"There ...

**0**

votes

**1**answer

61 views

### Degree of a node by geometric random undirected graph

suppose nodes with radius R are distributed randomly in Area of size A, then how can we calculate the degree of each node by geometric random graph.

**4**

votes

**1**answer

525 views

### How many distinct eigenvalues does a random graph have?

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.
But what is known about the ...

**5**

votes

**1**answer

188 views

### The structure of small components in random graphs with a given degree sequence

Background and definitions
Consider a random graph on $n$ vertices with a nicely behaved degree sequence. That is, letting $d_i(n)$ denote the number of vertices of degree $i$, suppose that for all ...

**3**

votes

**0**answers

66 views

### Is there precedent in the literature for a variant of a random geometric graph where vertices are the centroids of discs placed by random sequential adsorption (RSA)?

Imagine I form a random graph by simulating random sequential adsorption (RSA) of discs (each with the same radius $r$) on $[0,1]^2$ until I cover the plane at a density $\leq U$, where $U \leq ...

**0**

votes

**1**answer

110 views

### Is there a proper way to define a threshold vertex density for a random graph s.t. the graph is fully connected?

Imagine one generates some form of random graph (e.g. a random geometric graph) and via simulation, calculates the probability that there exists an edge-wise path between all vertices in the graph as ...

**3**

votes

**2**answers

267 views

### The probability distribution for vertex degree in a unit disc graph generated from random points on a plane

Imagine I cover an arbitrarily large plane with randomly placed points at some density $\rho$ s.t. the number of points in any randomly sampled area $A$ (of arbitrary shape and size) is $\approx ...

**0**

votes

**1**answer

257 views

### Two different definitions of Erdos-Rényi random graph

There are two or more ways to define an Erdos-Rényi random graph. Let consider the following two:
1) $G_n=(V_n,E_n)$ with vertex set $V_n=(1,\dots,n)$ and edge set $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ ...

**0**

votes

**0**answers

204 views

### counting k-cliques not also (k+1) on random graphs

consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges.
looking for a formula that counts the number of these graphs that have a $k$-clique but not a ...

**1**

vote

**1**answer

99 views

### how rare random bipartite graphs in all random regular graphs

i read a note talking about this fact, bipartite graphs are rare in regular graphs. but it do not state how rare it is? just curious about it. thank you very much.

**5**

votes

**1**answer

236 views

### Probability of two vertices to be connected in G(n,p)

A question I asked at math.SE without elliciting an answer.
Let $G(n,p)$ be an Erdős–Rényi graph on $n$ vertices. Is there an explicit expression for the probability $P_{n,p}(u,v)$ that two fixed ...

**3**

votes

**1**answer

352 views

### How random are random spanning trees?

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices ...

**2**

votes

**1**answer

325 views

### small hyperworlds ?

The theory of random graphs, after the pioneering classic work of Erdős & Rényi, has come to prominence with many further refinements, most notably the small world theory (Barabási, Watts, etc).
...

**0**

votes

**1**answer

126 views

### Generating spatially-aware degree-preserving random graphs?

In the study of biological neural networks, researchers sometimes compare hypotheses vs. a degree-preserving random null model. One major criticism against this approach is that connections in neural ...