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
3
votes
1
answer
454
views
Difference of pseudoinverse bound under assumptions
This seems like a standard problem, but unable to find a solution online.
Suppose we have two singular PSD matrices A and B with the following assumptions:
$ 0 < x \leq ||A|| \leq y$
$ 0 < ||...
- 33
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
3
votes
1
answer
761
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 ...
- 163
3
votes
1
answer
163
views
The most pseudorandom subgraph of a dense graph
A bipartite graph $(A,B)$ is $(p, \beta)$-jumbled if for all subsets $A'\subseteq A$ and $B'\subseteq B$ we have that $\left|\mathrm{E}(A',B')-p|A'||B'|\right|\leq \beta \sqrt{|A'||B'|}$. A easy ...
- 805
3
votes
1
answer
159
views
Hyper-degree sequences: How to count them and how to construct hyper-graphs from them?
From an answer to this question I have learned how to ask this question properly.
Consider a $k$-uniform hypergraph on $n$ nodes, i.e. a family of $k$-subsets of $[n]= \{1,2,\dots,n\}$ (the hyperedges)...
- 9,720
3
votes
1
answer
138
views
Degree sequences after vertex removals
Consider a graph $G=(V, E)$ with $|V|=n$ vertices. Let $(v_1, \dots, v_n)$ be an ordered list of its vertices. Let $G_i=G[\{v_{i+1}, \dots, v_n\}]$ be the induced subgraph on the last $n-i$ vertices. ...
- 565
3
votes
1
answer
166
views
Reference request - random regular graphs vs random graphs w/ degree sequence
There are some properties that are easily studied for random d-regular graphs, but that are very hard to extend to random graphs with a given degree sequence (e.g. whether a graph is w.h.p. ...
- 435
3
votes
1
answer
315
views
Relation between expected values of eigenvalues of Laplacian matrix of a graph and eigenvalues of expected Laplacian matrix of that graph?
Particularly, I am dealing with Erdős–Rényi random 𝐺(𝑛,𝑝), so the expected Laplacian matrix of 𝐺(𝑛,𝑝) is 𝑝(𝐽𝑛−𝐼𝑛), where 𝐽𝑛 and 𝐼𝑛 are one and identity matrices, respectively.
In ...
3
votes
1
answer
596
views
Asymptotic formula for the number of connected graphs
It can be shown that the set of graphs with $N$ vertices $G_N$ has cardinality:
\begin{equation}
\lvert G_N \rvert = 2^{N \choose 2} \tag{1}
\end{equation}
Recently, I wondered how much bigger $\...
- 3,871
3
votes
1
answer
206
views
Component properties in Euclidean graphs with distance threshold
In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...
- 649
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
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
3
votes
1
answer
1k
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.
...
- 383
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
2
answers
286
views
Finding an easy example applying the general Lovász local lemma
Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set $...
- 1,190
2
votes
3
answers
230
views
Random graphs defined by a set of tiles
Related to this question, which I asked at MSE, I'd like to ask this one here:
Consider a (large) graph $G$ and its multi-set of tiles $T$, i.e. the multi-set of its vertex-induced subgraphs, i.e. the ...
- 9,720
2
votes
2
answers
110
views
Difference between two largest degrees
Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) Let $S$ be the ...
- 1,209
2
votes
1
answer
237
views
Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$
Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that
the subgraph induced by $S$ in $G$ has minimum ...
- 393
2
votes
1
answer
154
views
Electrode assignment problem in resistive networks
Main question
In the context of resistor networks, and particularly purely from a graph theory point of view, is there a consistent way of assigning the two electrode nodes in order to compare the ...
- 649
2
votes
2
answers
255
views
Model for random graphs where clique number remains bounded
In the Erdös-Rényi model for random graphs,the clique number is seen to go to infinity as the number of vertices grows. Is anyone aware of models for random graphs with bounded clique number?
- 2,630
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
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
2
votes
2
answers
1k
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, ...
- 21
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
2
votes
1
answer
96
views
Lower bound on the number of balanced graphs
Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs
and ...
- 143
2
votes
1
answer
211
views
The complexity of expansion ratio (Cheeger constant) of a graph
Let $G=(V(G), E(G))$ be a graph on $n$ vertices and let $S$ be a subset of $V(G)$. The boundary of $S$, denoted by $\partial S$, is the set of edges $(i, j)$ such that $i \in S$ and $j \in V(G) \...
- 640
2
votes
1
answer
426
views
Random subgraph properties
Consider a graph $G$ of $N$ vertices and $M$ edges, and assume $G$ has typical complex network properties: it is not necessarily connected, but it has a high clustering coefficient and a giant ...
- 129
2
votes
1
answer
124
views
Relation between random graph models $G^{(B)}_{n,m}$ and $G_{n,m}$
In Frieze, Alan; Karoński, Michał, Introduction to random graphs, in Section 1.3 Pseudo-Graphs, there is a model of random multi-graphs, which is denoted as $\mathbb{G}^{(B)}_{n,m}$.
Def. A random ...
- 655
2
votes
1
answer
286
views
Behaviour of global clustering for common random graph models
In order to develop some intuition for some of the commonly used random graph models, I've been looking at the global clustering coefficient as a means of comparing them. In particular, for the ...
- 649
2
votes
1
answer
606
views
Component size distribution in small Erdos-Renyi networks
I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10.
I would like to know the probability a random node is in a component of size $m$.
It's ...
- 121
2
votes
1
answer
97
views
References on the structure of bond percolation on the (finite) 2D-grid in the sub-critical regime (e.g p=1/10)
Would appreciate references to the most up-to-date results for the structure of bond percolation on the (finite) 2D-grid in the sub-critical regime (e.g, $p=1/10$).
Thank you.
- 131
2
votes
1
answer
181
views
zero-one law in bipartite random model $G(n,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}...
- 683
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