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.
123 questions with no upvoted or accepted answers
13
votes
0
answers
509
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 ...
- 3,927
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
8
votes
0
answers
240
views
Stepanov phase transition in random graph
Consider the classical random graph model G(n,p), with p=c/n, as proposed by Erd\"os and R\'enyi.
At this scaling, the most prominent feature is arguably the abrupt change of the topology that the ...
- 468
8
votes
0
answers
181
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 ...
- 3,323
6
votes
0
answers
164
views
Hamilton cycles in random graphs with just enough connectivity
What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
- 7,525
6
votes
0
answers
301
views
Probability that a random multigraph is simple
Question.
Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
- 1,444
6
votes
0
answers
116
views
The properties of almost all directed graphs
A mathematician on the forum previously requested a reference on human brains modelled as directed graphs. This makes sense as neurons are mostly unidirectional and I have been thinking about similar ...
- 3,871
6
votes
0
answers
105
views
Long loops in critical random graphs
A simple calculation seems to show that the expected number $X_k$ of loops of length $k$ in a critical Erdös-Renyi random graph $G(n,n^{-1})$ is approximately given by
$$ \mathbb{E} X_k=\frac1{2k}{e^...
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
6
votes
0
answers
302
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 ...
- 1,731
5
votes
0
answers
577
views
Spectral norm bound on adjacency matrix from an Erdos-Renyi graph
Let $G(n,p)$ be an Erdos-Renyi graph, where $p \sim \log^k(n) /n$ for small fixed integer $k$. If $A$ is the adjacency matrix, then I am looking for a sharp upper bound on $\|A-\mathbb{E}[A]\|$ that ...
- 3,217
5
votes
0
answers
190
views
Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph
This question is very important for my research, which is why I ask it here.
I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...
- 51
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
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 ...
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
4
votes
0
answers
351
views
Research on graph theory
I am interested in graph theory. My background is mainly algebraic. I have been researching algebraic geometry for five years so I assume that the transition to the graph theory realm shouldn't be so ...
- 439
4
votes
0
answers
82
views
Expected number of bridges in a random subgraph
I am researching connectivity in random subgraphs and have come across the following problem.
A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
- 175
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
4
votes
0
answers
220
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 ...
- 323
4
votes
0
answers
94
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 $G_0$...
- 221
4
votes
0
answers
158
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 ...
- 41
4
votes
0
answers
183
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$, i....
- 163
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
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
3
votes
0
answers
81
views
Can we remove the restriction on a parameter in Talagrand concentration inequality?
Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
- 1,190
3
votes
0
answers
87
views
Is the probability distribution of a graphon given as a graph limit computable?
Let $G_i$ be a sequence of finite graphs that is Cauchy in the space of graphons. That is, for every $\epsilon \in \mathbb Q_+$ there is a $N \in \mathbb N$ such that $$\forall n, m > N. \delta_\...
- 6,353
3
votes
0
answers
151
views
Smallest dominating set
Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...
- 3,499
3
votes
0
answers
59
views
Minimum induced subtree cover number of a graph
For an arbitrary simple finite graph $G$, without multiple edges between any two nodes and without any loop, the minimum induced subtree cover number, which is denoted by $stc(G)$, is defined to be ...
- 4,784
3
votes
0
answers
147
views
Random graph - probability threshold for any linear size set to contain a fixed clique
Let $t\geq 3$ and $0<\varepsilon<1$ be fixed. Denote by $K_t$ the clique on $t$ vertices, and by $G_{n,p}$ the binomial random graph.
Question:
Is the threshold for the probability that "...
3
votes
0
answers
107
views
Random graphs with prescibed degrees and triangles
In short: a random graph model generates (multi-)graphs with prescribed number of edges and minimal number of triangles for each vertex. Questions arise about the actual number of triangles and the ...
- 1,444
3
votes
0
answers
209
views
Two kinds of generating functions
Sorry for a possibly off-the-topic question, but I am afraid to gain the necessary overview to give an answer (supposed the question is not ill-posed) is beyond my capabilities.
In the course of ...
- 9,720
3
votes
0
answers
94
views
Largest component and number of components of random mappings with bounded in-degree
Let $S$ be a finite set of size $n$ and consider all functions $f$ from $S$ to itself, such that the preimage $f^{-1} (k)$ obeys $0 \leq |f^{-1} (k)| \leq m$.
Let $F$ be chosen uniformly at random ...
- 131
3
votes
0
answers
151
views
Largest eigenvalue divided by $n$
Let $X$ be an $n\times n$ symmetric random matrix whose diagonal is fixed as $1$, and every element in the upper triangle (excluding the diagonal) is drawn from Bernoulli($p$). The elements in the ...
- 272
3
votes
0
answers
77
views
Eigenvalue Spectrum density for a simple non-iid matrices
As a part of research, I am studying the eigenvalues spectrum of adjacency matrices. My adjacency matrices are symmetrical. However, their elements are following multivariate gaussian distribution. ...
- 31
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
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
3
votes
0
answers
122
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 ...
- 367
3
votes
0
answers
199
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 ...
- 424
3
votes
0
answers
83
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 ...
- 2,449
3
votes
0
answers
102
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 (\...
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
2
votes
0
answers
51
views
Subgraphs of random graphs with a given degree sequence
Let $\mathbf{d}=(d_1,\dots, d_n)$ be a given degree sequence with $3\leq d_i\leq \Delta$ for every $i$, where $\Delta$ is constant. Let $G(n,\mathbf{d})$ denote the random graph uniformly distributed ...
- 143
2
votes
0
answers
145
views
Average number of cycles in a directed regular graph?
A directed random regular graph is a graph where all vertices have exactly $d_{\rm in}$ edges going in and $d_{\rm out}$ going out. If the graph is undirected, i.e. all vertices have degree $d$, then ...
- 109
2
votes
0
answers
87
views
Do Fagin's zero-one laws hold on stochastic block model?
Let $n$ be a positive integer (the number of vertices), $k$ be a positive integer (the number of communities), $p = (p_1, . . . , p_k)$ be a probability vector on $[k] := \{1, . . . , k\}$ (the prior ...
- 131
2
votes
0
answers
91
views
Graphon convergence of uniform weighted graphs
I have a question that I need at some point my research. Suppose that the upper-triangular entries of an $n\times n$ symmetric matrix $A$ are i.i.d. Uniform$(0,1)$. Does the weighted graph with ...
- 241
2
votes
0
answers
36
views
Is homomorphism density of partially labeled graph continuous with respect to cut metric
Let $F=(V, E)$ be a finite simple graph on $n$ vertices with two labelled vertices, say $x, y$. Let $W:[0, 1]^2\to [-1, 1]$ be symmetric function. Lov'asz's book (Large Networks and Graph Limits) ...
- 371
2
votes
0
answers
74
views
Cycle statistics of random endomorphism
Let $S$ be a set with $n$ elements and let $f:S\to S$ be a random function, chosen uniformly among the $n^n$ possibilities. Considering $f$ as a directed graph of constant outdegree $1$, i. e. with ...
- 3,017
2
votes
0
answers
281
views
Generating a random graph with bounds on degree and diameter
What would be a way to generate a random simple graph with diameter lesser than a given number, and in which there are given lower and upper bounds (bounds being uniform across vertices) on the degree ...
- 1,216