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
4
votes
2
answers
263
views
Colorability of random regular graphs?
I have the following experimental results on random regular graphs. I would like to know current theory on colorability of random regular graphs.
Almost all 5 regular graphs are 3 colorable.
Almost ...
2
votes
2
answers
110
views
Volume doubling implies that the degree is uniformly bounded above?
Let $G=(V,E)$ be a connected graph. Here $V$ is the set of all vertices of $G$, and $E$ is the set of all edges of $G$. Suppose that $G$ is locally finite, i.e., $\sharp\{y\sim x:y \in V \}$ is finite ...
- 169
0
votes
1
answer
3k
views
How to compute the clustering coefficient of a random graph?
How is the clustering coefficient defined for random graphs? For example, a first definition could be calling clustering coefficient of a random graph the expected value of the clustering coefficient ...
- 23
0
votes
0
answers
69
views
Quasi-stationary measure on a finite graph equals stationary measure?
Assume the simple random walk $X$ on the graph $G(V,E)$, s.t. $G$ is simple, undirected, finite, connected and let $B \subset V$, s.t. $V\setminus B$ is connected. Let $\sigma_B$ be the quasi-...
- 71
12
votes
1
answer
526
views
Spectrum of induced subgraphs of Paley graph
Let $G_q$ be a Paley graph on $q$ vertices, where $q=1 \text{ (mod 4)}$, i.e., the vertices of $G_q$ are the elements of the finite field $\mathbb{F}_q$, and there is an edge between vertices $a,b \in ...
- 171
2
votes
1
answer
238
views
On lower bounds for harmonic functions on $\mathbb{Z}^d$
Consider a non-constant harmonic function $f$ on $\mathbb{Z}^d$ (meaning this that $f(x)$ if the average of the $2d$ values $f(y)$ such that the distance between $x$ and $y$ is one). Let $M_n$ denote ...
- 153
3
votes
0
answers
105
views
Finding large bicliques in random bipartite graph
I want to find a $k$ by $r$ biclique hidden in an $M$ by $N$ random bipartite graph where edges are present with probability $p \in [0,1]$. I am specifically interested in $p \ll 1$, and large values ...
3
votes
0
answers
151
views
Sequential generation of any random graph
The high-level question is: can we generate any random graph with size $d$ using a Markov chain?
For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
- 1,127
2
votes
0
answers
228
views
expected number of edges for fixed min cut
It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges.
Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...
- 21
6
votes
5
answers
1k
views
Generate random graphs that satisfy the triangle inequality
I would like to generate random graphs that might be geometric graphs in some
(unknown) dimension. So I would like every triangle in the graph to satisfy the
triangle inequality on its (random) edge ...
- 151k
4
votes
0
answers
95
views
Counting 2-factorizations
Suppose I have a $2k$-regular graph. By Petersen's theorem this has a $2$-factorization. The questions are:
Is there some nice way to count $2$-factorizations, or is it a hard problem?
Are there any ...
- 96.4k
2
votes
1
answer
727
views
When an Erdos-Renyi graph is locally tree like?
I would like to know when an ER graph is locally treeing like. In this post.
I found this comment:
I think $N$ is $\log2|V|$, or something like that, in that paper.
They consider binary vectors ...
- 21
12
votes
2
answers
621
views
Eliminating constant in Rado graph
Let $R$ denote the Rado graph, and let $c$ be a fixed vertex.
Question 1. Is the structure obtained by extending $R$ by the constant $c$ interpretable in $R$ without parameters?
By interpretable I ...
- 618
1
vote
0
answers
109
views
Number of $H$-free graphs
Sorry if this is basic for MO. But the people at SE couldn't help me.
I'd like to get an estimate on the number of (labeled) $H$-free graphs on $n$ vertices, i.e. graphs in which no set of $|V(H)|$ ...
- 11
3
votes
0
answers
258
views
Distribution of the k-core of a random graph
A k-core of a graph is the maximal subgraph with minimal degree k. For example, the 2-core would emerge by subsequently deleting degree-1 vertices of a graph.
I've seen a lot of work on existence of ...
- 255
1
vote
0
answers
68
views
Almost all graphs have an induced path on four vertices [closed]
Is this statement true? If yes, I would like to be pointed to references containing its proof.
- 327
0
votes
1
answer
166
views
Length of longest directed circuit in random tournament
Build a random tournament $T=(V,E)$ on $V=\{1,\ldots, n\}$ in the following fashion: for $i < j\in \{1,\ldots, n\}$ let the probability be $0.5$ whether $(i,j)\in E$ or $(j,i)\in E$ (in a ...
- 48.8k
2
votes
1
answer
186
views
Existence of a Connectivity Polynomial for a simple graph?
I try to find a polynomial for an arbitrary simple graph $G$ that tells whether the graph is connected or not. A graph is st-connected if you can find a path between a vertex $s$ and a vertex $t$ -- ...
- 143
11
votes
1
answer
378
views
Question on a paper by Benjamini/Kozma/Wormald about a “well known fact”
In "The mixing time of the giant component of a random graph" by the aforementioned authors, in the last proof on page 19 it says something along the lines of
"It is well known and easy to verify ...
- 255
2
votes
0
answers
76
views
How are Polynomials of Toric ideals Studied with Exponents as ST-cuts?
Topic: Toric ideals on Expected value of Structure Functions in Random Graphs
Goal: to understand the toric ideal where the exponents $h_i$ and $s_j$ are st-vertex-cuts of a digraph
\begin{equation}
...
- 143
5
votes
0
answers
216
views
Fraction of vertices in ER random graphs not in giant or tiny components
ER random graphs in $G(n,m)$ model are known to have a giant component when $m>n/2$ which grows to a value of $\Theta(n)$ very abruptly. Also the size of the second largest component is known to ...
- 51
3
votes
1
answer
276
views
Zero-one law in binomial random graph model $G(n,p)$
Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $\lim\limits_{n \rightarrow \infty} ...
- 39
1
vote
0
answers
166
views
Expected number of perfect matchings in bounded degree bipartite graphs
Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$.
What is the expected number of perfect matching a graph in $\mathcal C_{n,n,\...
- 13.9k
2
votes
1
answer
168
views
Random Walk 2D with dependent weights [closed]
I have spent a lot of time trying to solve this problem but have had no luck so far! Any help would be highly appreciated!
Suppose I have a 3x3 grid as shown below.
(3,1) (3,2) (3,3)
(2,1) (2,2) (...
- 23
0
votes
1
answer
1k
views
Vertex cover of regular graph
(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on ...
user76479
4
votes
2
answers
254
views
first order languages over graphs (and other discrete models)
A lot of research has been devoted to the study of first order language of graphs (FO). Formulas in this language are constructed using variables $x, y,\dots$ ranging over the vertices of a graph, the ...
- 1,561
4
votes
1
answer
388
views
Proofs of inequalities used by Erdos-Renyi in their Random Graphs Paper 1
Please refer to this, it is Erdos-Renyi 1959 paper 1 on Random Graphs. I am currently working on this, but I am stuck on the fifth page, where they use two estimates. More specifically, here's the ...
- 319
6
votes
3
answers
434
views
Repository of graph classes that are tough to test non-isomorphic pairs from isomorphic pairs
(1) Which graph classes are extremely tough to test for graph non-isomorphic pairs from isomorphic pairs?
(2) Is there a repository of adjacencies from such classes?
- 13.9k
5
votes
2
answers
845
views
Database of adjacency matrices on cospectral non-isomorphic graph pairs
Is there a repository of cospectral non-isomorphic graphs available somewhere?
I am looking for list of $0/1$ adjacency matrix pairs that can be input data in tools such as MATLAB.
- 13.9k
6
votes
2
answers
657
views
In a random graph which one is more probable, $k$-clique or $k$-core?
Recall that the $k$-core of a graph $G$ is the unique maximal subgraph of $G$ with minimum degree at least $k$.
In an Erdos-Renyi random graph, where the edge selection is independent with ...
- 177
2
votes
0
answers
69
views
What is the gap between the two defined distances from node to node in a random graph?
Give a sparse random graph $G=(V,E)$, every edge $(u,v)\in E$ is associated with a weight $w(u,v)$. We assume each $w(u,v)$ is geometrically distributed with parameter $p_{u,v}$. The weight of a path ...
- 321
5
votes
0
answers
353
views
Edit distance vs. canonical adjacency matrix distance
Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...
- 83
5
votes
0
answers
66
views
Full distribution of FPTs in random walks on graphs
There is a lot of published research on the mean passage passage time (FPT) for random walks on various types of graphs. How about the variance of the FPT and higher momenta? In fact, I would be ...
3
votes
2
answers
479
views
Number of nodes in a given distance in (random) regular graph
Given a d-regular graph $G=<V,E>$ (connected, unweighted & simple), and a node $v$.
denote all nodes with distance $k$ from $v$ $$L_k=\{u\in V : dis(v,u) = k\}$$
Let's call it "the k-th ...
- 31
1
vote
1
answer
132
views
Probability of having no cycles of fixed length in $d$-regular graphs
According to this paper, the probability that a random $d$-regular graph of order $n$ has no cycles of length $c_1,c_2,\ldots,c_t$ is $$P=\exp\left(-\sum_{i=1}^t\mu_i+o(1)\right)$$ as $n\rightarrow\...
- 239
14
votes
2
answers
387
views
What are some useful invariants for distinguishing between random graph models?
Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as:
The Erdős-Rényi model
The Stochastic Block model
The Watts-Strogatz model
The Barabasi-Albert model
...
- 29.2k
3
votes
1
answer
376
views
Good broad review of agent-based modeling? [closed]
Trying to find some good review of agent-based models and networks, specifically models that are defined by a graph of interacting nodes, that covers analysis of collective behavior based on model of ...
- 93
1
vote
1
answer
312
views
Can we estimate the probability $\mathbf{P}(a-k|a - b) $ on a random graph?
Let $G=(V,E)$ be an undirected random graph such that
$V$ is the set of nodes, and $E$ is the set of edges
Assume the ground graph $G$ is sparse enough, for example, $\frac{|E|}{|V|}= c \in [10, 40]$ ...
- 321
3
votes
1
answer
338
views
Modularity in a graph - definition of the random component
This question concerns the definition of modularity in a graph.
Consider a simple, undirected, unweighted graph $G$ with vertices in set $V$ and edges in set $E$ . Between any two vertices there is ...
- 31
6
votes
0
answers
149
views
Does squaring a directed random graph more than double its out-degree?
As far as I know, it is an unsolved question
whether or not this is true:
If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least
double that of its ...
- 151k
1
vote
0
answers
75
views
Weak law for component count of Erdos-Renyi random graphs
Penrose and Yukich derive a weak law for functionals of binomial point processes, which implies a law of large numbers for the component count of random geometric graphs. Do similar results exist for ...
- 11
6
votes
1
answer
200
views
Modification of matching
Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...
- 903
0
votes
0
answers
320
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 ...
- 1
2
votes
2
answers
413
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$ ...
- 21
1
vote
1
answer
298
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 ...
- 338
10
votes
2
answers
2k
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 ...
- 6,976
4
votes
1
answer
365
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 (e....
- 355
12
votes
1
answer
509
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, ...
- 175
8
votes
2
answers
2k
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.
...
- 1,344
5
votes
1
answer
358
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$ ...
