The random-graphs tag has no wiki summary.
3
votes
0answers
143 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
107 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
379 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
36 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
192 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
333 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
156 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
51 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
52 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
89 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
105 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
86 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 ...
6
votes
0answers
106 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
299 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
158 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 ...
0
votes
0answers
56 views
problem about Matrix multiple
Assuming a series of random geometric graph G1,G2,...,Gn. For each Gi, |V|=N, and nodes are distributed as a possion point process. If the distance between a pair of nodes is less than or equal to ...
2
votes
0answers
80 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
579 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
209 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
55 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
214 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
46 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
450 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
144 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
62 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
84 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
222 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
210 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
152 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
95 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.
2
votes
0answers
134 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
271 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
321 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
118 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
240 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, ...
3
votes
1answer
216 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
184 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
247 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
150 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 ...
5
votes
0answers
220 views
How does the distribution of Erdős number evolve over time ? How to build a model to fit the real data ?
Let $E(n,t)$ be the number of mathematicians with finite positive Erdős number $n$ at time $t$. As old mathematicians leave, and new mathematicians come, how does $E(n,t)$ change over time ?
We can ...
0
votes
0answers
106 views
Generating Conditional Random Graphs
Let $G(n,p)$ be the usual random graph on $n$ vertices with each edge existing independently with probability $p$ (no self loops , or double edges not are allowed). I would like to simulate the ...
8
votes
1answer
562 views
Correlation-Function for Random Graph Ising Model
For non-Ising'ers: Given a graph, we study the probability-distribution on the set of colorings ("Spin-up" and "-down") generated by a given correlation ("force to equality") between adjacient nodes ...
5
votes
0answers
157 views
Small Configurations in Random Hypergraphs
I have a somewhat technical question regarding the distribution of small hypergraphs in randomly chosen hypergraphs. (My hope is that this is something that can be done using standard ideas about ...
9
votes
3answers
983 views
Area Enclosed by the Convex Hull of a Set of Random Points
Consider $n$ points generated randomly and uniformly on a unit square. What is the expected value of the area (as a function of $n$) enclosed by the convex hull of the set of points?
3
votes
2answers
237 views
Question on Sparse Random Graphs
I saw stated in a paper the following result but without a reference or a proof.
Let $G$ be an Erdos-Renyi random graph with $n$ nodes and probability of connection $c/n$ with $c>1$. Let $H$ be ...
1
vote
1answer
235 views
Connectivity of a graph with fixed number of vertices and edges
Hi,
first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge.
So this is the ...
5
votes
1answer
261 views
A more efficient way to generate random graphs with a given degree sequence?
In graph data mining it is often useful to generate random (simple) graphs with a given degree sequence (e.g. in searching for network motifs), and ideally these would be uniformly at random.
[For ...
