Questions tagged [random-graphs]
The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.
345 questions
1
vote
0
answers
372
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 $(k+...
- 529
1
vote
1
answer
129
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.
- 11
6
votes
1
answer
2k
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 (...
- 656
3
votes
1
answer
2k
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 ...
- 6,962
3
votes
1
answer
394
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).
...
- 7,853
0
votes
1
answer
161
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,229
4
votes
2
answers
675
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, $p_n=\frac{(...
- 103
6
votes
1
answer
981
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 ...
- 63
4
votes
0
answers
617
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 edge-...
- 1,414
0
votes
0
answers
188
views
Graph theory meta-question
If property (P) holds for perfect graphs and almost all graphs does it hold for all graphs?
- 6,962
10
votes
0
answers
669
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 ...
- 501
7
votes
4
answers
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 ...
- 1,302
0
votes
0
answers
161
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 ...
- 1
2
votes
1
answer
203
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 ...
- 201
6
votes
1
answer
571
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 ...
- 2,581
1
vote
0
answers
188
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 ...
- 4,952
9
votes
1
answer
1k
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 (...
- 1,846
5
votes
0
answers
179
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 ...
- 7,145
12
votes
3
answers
3k
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?
- 123
3
votes
2
answers
336
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 ...
- 73
5
votes
1
answer
750
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 ...
- 4,229
13
votes
2
answers
383
views
Comparing two measures on trees on $n$ vertices
A standard measure on trees on $n$ vertices is the Uniform Spanning Tree (UST) on the complete graph. This is the measure where every tree has equal probability, $1 / n^{n-2}$ by Cayley's formula.
...
- 7,857
4
votes
2
answers
335
views
Can you randomly sample graphs with quadratic growth?
Let $\mathcal{G}$ be the set of all infinite connected graphs with the following properties:
Every vertex has $4$ neighbors
For every vertex, there are $8$ vertices that have distance exactly $2$ ...
- 8,688
29
votes
3
answers
2k
views
Growing random trees on a lattice $\rightarrow$ Voronoi diagrams
Imagine growing trees from $k$ seeds on a square $n \times n$ region
of $\mathbb{Z}^2$.
At each step, a unit-length edge $e$ between two points of
$\mathbb{Z}^2$ is added.
The edge $e$ is chosen ...
- 151k
10
votes
3
answers
4k
views
Random bipartite graphs
Consider the following situation: I have a set $A$ of $n$ vertices and a set $B$ of $N = n^2$vertices. I consider the bipartite graph $(A, B)$ and put at random $M = n^{1 + \varepsilon}$ edges (or I ...
- 2,449
10
votes
2
answers
2k
views
Probability of Generating a Connected Graph
$N$ points are generated randomly within a unit square, with a uniform distribution.
What is the probability that the points form a connected graph, given that two points are connected if the distance ...
- 103
4
votes
1
answer
781
views
Prime number density vs. connectedness threshold: coincidence?
(1) $\pi(n)$, the number of primes at most $n$, is asymptotic
to $n / \ln n$.
(2) In the Erdős-Rényi random graph model, $p = \ln n / n$
is a sharp threshold for the connectedness of the graph $G(n,p)...
- 151k
10
votes
3
answers
1k
views
Eigenfunctions of random graphs
Consider a random $d$-regular graph on $n$ vertices. What can be said about its nontrivial (i.e. orthogonal to the constant) eigenfunctions? For example, I'm interested whether there are "nodal zones",...
- 2,449
9
votes
1
answer
448
views
Two-cardinal models of the random graph
For a first-order theory $T$ and cardinals $\kappa < \lambda$, we say that $M$ is a $(\kappa,\lambda)$-model if it is of size $\lambda$ and has a definable (with parameters) subset of size $\kappa$....
- 341
0
votes
1
answer
359
views
How many graphs with given average degree and average number of outgoing nodes?
Hi,
does anyone know if it is known what is the number of undirected graphs with the following properties:
Number of nodes: $N$, a big number,
Average degree: $z_1$,
Average number of outgoing ...
- 923
8
votes
1
answer
630
views
Change in the average geodesic distance of a graph when flipping a single edge
Is there a way to determine how the average geodesic distance between nodes of a graph will change just by flipping (1) a single edge without having to traverse the whole graph like in the Djikstra ...
- 923
5
votes
4
answers
337
views
Finite graphs that realize all types over $n$-element sets
Call a graph $G$ $n$-saturated if for every set $A$ of size $n$ of vertices and all $B\subseteq A$ there is a vertex $v\not\in A$ that forms an edge with all $w\in B$ and
does not form an edge with ...
- 16.2k
7
votes
2
answers
417
views
Dynamics of a random "quadratic" directed graph
Let G be a directed graph on N vertices chosen at random, conditional on the requirement that the out-degree of each vertex is 1 and the in-degree of each vertex is either 0 or 2. The "periodic" ...
- 19.2k
1
vote
1
answer
223
views
PR[$\lambda_2 > x$] in $G_{np}$ model
Hi!
Does anyone know of any statement relating the probability that the second largest eigenvalue of a random graph is bigger than $x$ to the parameter $p$ in the $G_{np}$ model?
- 239
3
votes
0
answers
156
views
Large Deviation Bounds for Number of Forests (or Tutte polynomial) in G(n,p)
Does anyone know of results/references related to large deviation bounds on the number of subforests (or the Tutte polynomial) in G(n,p) (Erdos-Renyi random graphs)?
- 53
14
votes
2
answers
988
views
Properties of Some Random Graphs
Working in a problem the following family of graphs appears naturally. Consider the set $A_{n}=\{1,2,3,\ldots,n\}$ and let $\mathcal{C_{n}}$ be the set of all permutations of $A_{n}$ of order $n$ (...
- 3,626
57
votes
4
answers
15k
views
Connectivity of the Erdős–Rényi random graph
It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...
- 7,857
4
votes
2
answers
2k
views
Probability, that a graph G does not contain a cycle
Hello, given graph $G=(V,E)$ with $n=|V|$ and $k=|E|$, what is the probability that it does not contain any cycle $C_l$ for $l\geq3?$
The requested clarification:
My intention was to form the ...
- 175
10
votes
4
answers
3k
views
"sparse graphs are locally tree-like"
I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree ...
- 101
4
votes
0
answers
124
views
What is known or conjectured regarding three dimensional random triangulations?
Uniform measure on random triangulations of the two dimensional sphere and their limits are rather well understood. Are there any results or heuristics regarding three dimensional analogues?
- 41
6
votes
2
answers
3k
views
Max cut value in a random graph
Let $G = G(n, 1/2)$ be an Erdos-Renyi graph in which each edge $e = (u,v)$ is present in the graph independently with probability $1/2$. For a subset of the vertices $S$, the cut value $c(S)$ is equal ...
- 794
5
votes
1
answer
1k
views
Self Avoiding Walk Enumerations
Let $c(n)$ be the number of Self avoiding walks (SAW) of length $n$ on an infinite lattice $L$. Are there any known non-geometric interpretations of $c(n)$?. For example, is there a number theoretic ...
- 4,952
11
votes
3
answers
743
views
Rainbow matchings (in random graphs)
Suppose we have an $(n,n)$-bipartite graph with edges colored with $k$ colors. Is anything known about the existence of rainbow matchings (i.e. a matching that uses each color exactly once, for $k=n$) ...
- 3,323
8
votes
2
answers
986
views
Spectrum of the Laplacian on G(n, p) and G(n, M)
A random graph in $G(n, p)$ model is a graph on $n$ vertices in which for each of the $n\choose{2}$ edges we independently flip a coin, then take the edge with probability $p$ or remove it with $1 - p$...
- 2,449
9
votes
1
answer
1k
views
Vertex connectivity of random graphs?
Consider simple, undirected Erdős–Rényi graphs $G(n,p)$, where $n$ is the number of vertices and $p$ is the probability for each pair of vertices to form an edge. Many properties of these graphs are ...
- 383