The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
0answers
45 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
1answer
75 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
0answers
83 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
2answers
77 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 ...
2
votes
0answers
55 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
1answer
105 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
0answers
46 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
0answers
92 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 ...
3
votes
0answers
48 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
0answers
161 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
1answer
125 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
6answers
408 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
0answers
48 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
1answer
217 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
3answers
351 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
3answers
164 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
0answers
56 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 ...
2
votes
0answers
56 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 ...
0
votes
0answers
93 views

Adjacent matrix of undirected graph with a giant component

Assuming there is a undirected random graph $G=(V,E)$, $|V|=N$ and its adjacent matirx is $A$. What is the sufficient and necessary conditions of A for that there is a giant component of graph $G$? ...
3
votes
0answers
116 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
0answers
107 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
0answers
120 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
1answer
416 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
1answer
165 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
0answers
87 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
3answers
597 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
2answers
231 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
0answers
60 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
1answer
241 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
1answer
58 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
1answer
494 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
1answer
172 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
0answers
65 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
1answer
99 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 ...
2
votes
2answers
245 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
1answer
234 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
0answers
180 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
1answer
96 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
1answer
221 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
1answer
318 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
1answer
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
1answer
122 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 ...
4
votes
2answers
273 views

between “giant-component” and “fully connected”

This is a request for reference. Where can I find discussion of the Erdős–Rényi random graph in the regime between "giant-component" and "fully connected"? e.g. a detailed picture for say, ...
4
votes
1answer
240 views

Cut-distance between two Erdos-Renyi random graphs

Consider two Erdos-Renyi random graphs $G_1,G_2$ on $n$ nodes, with the edges in each graph generated independently at random with probability $1/2$. My question is about the cut-distance between ...
4
votes
0answers
205 views

Expected number of components with multiple cycles in a subgraph of a square lattice

Short version Is there an understanding of the emergence and subsequent disappearance of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the ...
0
votes
0answers
136 views

Graph theory meta-question

If property (P) holds for perfect graphs and almost all graphs does it hold for all graphs?
9
votes
0answers
262 views

Minimum spanning tree of a random graph

Consider $n$ points arbitrarily located on the plane. Consider a random graph $G$ drawn from $G(n, \frac12)$ on these points (i.e. the Erdos-Renyi random graph where every edge is selected with ...
7
votes
4answers
1k views

Recent impressive combinatorial developments in probability theory

In the preface to the second edition of Daniel Stroock's book "Probability Theory: An Analytic View", there is this striking claim (on p. xv) ... I suspect that, for at least a decade, the most ...
0
votes
0answers
137 views

T. Lyons Criterion

Hello all, I want to prove that any flow on the following tree must have an infinite energy. The structure of the graph is (taken from R.Lyons and Y.Peres book) "We’ll construct a tree $T$ embedded ...
2
votes
1answer
158 views

matchings in hypergraphs

I have been reading Pippenger and Spencer's paper "Asymptotic behavior of the chromatic index for hypergraphs" and they comment that their result is applicable to the family of random k-uniform ...