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
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
2
votes
0
answers
212
views
Expansion of random subgraphs of a bi-regular bipartite graph
Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree.
We know $G$ is a good spectral expander. ...
- 225
3
votes
1
answer
164
views
making a random uniform hypergraph linear
Let $\mathcal{H}_{n,p,h}=(V,E)$ be a random $h$-uniform hypergraph on $[n]$, sampled according to the usual binomial distribution. We known that with high probability, the number of edges in $\mathcal{...
4
votes
1
answer
284
views
Structures for random graphs with structure
Background[You may skip this and go immediately to the Definitions.]
Crucial features of a (random) graph or network are:
the degree distribution $p(d)$ (exponential, Poisson, or power law)
the mean ...
- 9,720
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
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
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
186
votes
3
answers
96k
views
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
- 343
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
4
votes
2
answers
207
views
Fast uniform generation of random graphs with given degree sequences - any implementation?
The paper below presents a linear-time algorithm for uniform generation of random graphs with given degree sequences [1].
This is very interesting in practice, but I found no implementation. However, ...
- 1,444
0
votes
0
answers
445
views
The diameter of random regular graphs
In 1982, B. Bollobas and Vega in the paper gave the configurational model to generate $r$-regular random graphs. They gave the following theorem (Theorem 1 in the paper).
Theorem: Let $r\geq 3$ and $\...
- 640
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
6
votes
1
answer
421
views
Probability in Chromatic number upper bound of induced subgraph
Let $G=(V, E)$ be a graph with chromatic number $\chi(G)=1000 .$ Let $U \subset V$ be a random subset of $V$ chosen uniformly from among all $2^{|V|}$ subsets of $V$. Let $H=G[U]$ be the induced ...
- 61
1
vote
1
answer
192
views
Survey/references on random geometric $K$-NN – $K$-nearest-neighbour graphs?
[Edit:] Some related info on number of connected components of NN-graphs can be found here: https://cstheory.stackexchange.com/a/47037/2408
Sample $N$ points in $\mathbb{R}^d$ from some distribution $...
- 24.8k
-2
votes
1
answer
82
views
Ensemble averaging in a random graph (or network) in the large $N$ limit [closed]
I have a random graph/network described by the adjacency matrix $(a_{ij})_{N\times N}$ where $a_{ij}=1$ with probability $p$. Each node in the graph is associated with a continuous quantity $\eta_i=\...
- 137
4
votes
1
answer
1k
views
Critical probability for Erdos-Renyi digraphs to be strongly connected
Given $p \in [0,1]$, an Erdos-Renyi graph ${ER}(n,p)$ on $n$ vertices is constructed by defining, for each unordered couple of distinct vertices ${i,j}$ an edge between $i$ and $j$ with probability $p$...
- 147
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
11
votes
1
answer
370
views
Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?
Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
- 6,917
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 ...
1
vote
0
answers
140
views
Count shortest path with different lengths in random graph
Let $G(n,p)$ be an Erdos-Renyi random graph on $n$ vertices with probability $p$, i.e. for each pair of vertices, they are connected directly by an undirected edge with probability $p$. Suppose we are ...
- 1,495
1
vote
1
answer
381
views
An attempt to find expected value of clique number of special random graph
Let $G(n)=(V,\mathcal{E})$ be a random graph definded as follows:
$V=[n]=\{1,2, ... ,n\}$ and for all $i,j\in V$ so that $i\ne j$ we have $\{i,j\}\in\mathcal{E}$ with probability $p$. Where $p\in[0,1]...
- 123
0
votes
0
answers
101
views
4-cycles vs eigenvalue information on quasi-random graphs
My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.
The main purpose of the paper is to show ...
- 1,561
12
votes
1
answer
542
views
Distribution of degree in graphs: when is the friendship paradox the paradox it wants to be?
$\DeclareMathOperator\deg{deg}\DeclareMathOperator\ndeg{ndeg}\newcommand\abs[1]{\lvert#1\rvert}$The friendship paradox goes most people have fewer friends than their friends have on average. The ...
- 343
5
votes
1
answer
119
views
Attacking a network at minimum cost
A target system is modelled as a giant, undirected, simple graph $G$ (simple meaning no hyperedge) that can be scrutinized in adequate detail to budget and plan the attack: its topology changes slowly ...
- 347
2
votes
1
answer
900
views
Asymptotically tight concentration of norms of subgaussian random vectors with independent coordinates, as the dimension $n \to \infty?$
Let $X=(X_1 \dots X_n)\in \mathbb{R}^n,$ be a subgaussian random vector so that $X_i$'s are independent, $\mathbb{E}X_i = 0, \mathbb{E}X_i^2=1.$ Before we pose our question, let's state the following:
...
- 1,465
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
3
votes
1
answer
230
views
Unique maximum degree in tournament
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 $p(n)$ denote ...
- 1,209
1
vote
1
answer
435
views
Size of minimum cut in random graph
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$.) The score of each ...
- 1,209
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
1
vote
1
answer
104
views
Limit of normalized sum of Dirac measures at first $\lfloor p/2\rfloor$ eigenvalues of the sample covariance matrix, with Marcenko-Pastur assumptions?
Let $\lfloor{*}\rfloor$ denotes the nearest integer $\le *$. I'm asking myself the question what's the limit of the part of the empirical spectral distribution corresponding to the first $\lfloor{p/2}...
- 1,465
1
vote
0
answers
29
views
Bound on the number of bridges between vertices in a sampled subgraph
I am researching connectivity in sampled 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
10
votes
4
answers
528
views
When is a large graph with a given degree sequence likely to be connected?
Are there any results on whether a large random graph with a given degree distribution is likely to be connected?
In Erdős-Rényi graphs with $n$ vertices and $m$ edges, we have two sudden transitions ...
- 911
1
vote
1
answer
265
views
Continuum percolation in 1d
What is known about continuum percolation in 1d?
By this, I mean, for $d \in \mathbb{N}$, the Poisson-Boolean model of disks of radius $r_0 \in \mathbb{R}$ with centres arranged randomly in $[0,1]^{d}...
- 640
8
votes
1
answer
447
views
Graphons and Graphs
The situation is as follows: assume we have a sequence of simple weighted graphs $(G_n)_{n\in\Bbb{N}}$. For the terminology that follows I refer to Limits of dense graph sequences by László Lovász and ...
- 81
0
votes
1
answer
72
views
Small subgraphs of the random graph
If I look at the distribution of the number of small subgraphs in the random graph isomorphic to a connected graph $H$, this is asymptotically Poisson.
What proportion of these small subgraphs ...
- 640
4
votes
1
answer
245
views
Probability of a vertex being a "degree-celebrity" in a random graph
If $G(n,p)$ is a random graph of the Erdös-Rényi model,
what is the probability that $\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$
Please feel free to relate answers to other ...
- 13.2k
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
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
4
votes
1
answer
275
views
Probability of a subset of Bernoulli's being all 1's
Suppose we have $n$ iid Bernoulli's $X_1,\ldots,X_n$ with mean $p$, and a family $\mathcal{F}$ of subsets of $[n]$. The question is how to lower bound the probability that there is a set in the family ...
- 408
2
votes
0
answers
83
views
Zero-One law for Hamiltonian path subgraphs of Hamming Distance Graphs?
$(\alpha,\beta,d)$-Hamming Distance Graph $G_d(\alpha,\beta)$ for $\alpha,\beta\in(0,1]$ is a graph on $2^d$ vertices $v_0,\dots,v_{2^d-1}$ with edges $(v_i,v_j)\in\mathcal E(G_d)$ iff $0<\sum_{t=1}...
- 13.9k
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
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
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
4
votes
1
answer
158
views
Almost all simple graphs are small world networks
Two days ago it occurred to me that almost all simple graphs are small world networks in the sense that if $G_N$ is a simple graph with $N$ nodes sampled from the Erdös-Rényi random graph distribution ...
- 3,871
3
votes
1
answer
336
views
Eigenvalues of random graphs
At time $t=0$, let $G_n(V,E)$ be a graph with $n$ vertices and $m < n$ edges. Then there exists a unique symmetric adjacency matrix $A_n$ associated with $G_n(V,E)$, defined as follows: $a_{ij} = 1$...
- 101
2
votes
2
answers
224
views
Is there a way to generate a graph of specified treewidth
The treewidth is a parameter of the graph that describes its similarity to a tree. Treewidth is NP-hard to find. For the introduction please see wikipedia
The question is how to generate interesting ...
- 23
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
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
2
votes
0
answers
28
views
Edgeweight-Conditions for "Statistically Self-similar" Complete Weighted Graphs
Given a complete symmetric weighted graph with $n$ vertices, for such a graph there always exists a minimum spanning tree and, under the assumption of the uniqueness of that tree, the vertex degrees ...
- 13.2k
1
vote
2
answers
116
views
How to use probability to find a matching in a family of graphs?
In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...
- 57