# 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.

263
questions

**1**

vote

**0**answers

41 views

### Another betweenness centrality measure: neighbourhood centrality

Among the many centrality measures that I have heard of, I miss the following (but maybe I'm just blind).
Consider a graph $G$ with $k$ connected components $G_i$ of size $|G_i|$. The number of node ...

**2**

votes

**0**answers

38 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 ...

**2**

votes

**1**answer

90 views

### Probabilistic bound to the number of edge disjoint triangles in a random graph

Let $G$ be a random graph with $n$ vertices, and let $\delta(G)$ be the maximum number of triangles in $G$.
Question. How to prove the bound $$P(\delta(G)) \leq m - t \sqrt{f(m)}) \leq 2e^{-t^2 / 4}$...

**8**

votes

**1**answer

576 views

### What is the theory of the random poset?

$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...

**2**

votes

**1**answer

113 views

### Random graphs and Benjamini-Schramm convergence

I am looking for literature on the question whether a randomly chosen sequence of $k$-regular graphs converges in the Benjamini-Schramm sense to the universal covering with probability one.
There are ...

**2**

votes

**3**answers

176 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 ...

**1**

vote

**0**answers

30 views

### Eigenvalue bounds of a random graph with a clique

I'm looking into this paper and having some problems proving (ii) of proposition 2.1. I don't quite understand how the lemma is proved. I also read the original paper where the lemma comes from but ...

**4**

votes

**3**answers

297 views

### How to show that random graphs cannot be embedded with short edges

For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio
$$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between ...

**0**

votes

**2**answers

105 views

### How to define probability over graphs?

How can one formally define a random graph variable?
If G is a random graph variable, then any finite graph is a realization of G. Formally a r.v maps the set of outcomes to a measurable space (may be ...

**3**

votes

**0**answers

56 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 ...

**2**

votes

**0**answers

89 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 ...

**2**

votes

**0**answers

47 views

### Are two degree sequences compatible, for random simple graph generation?

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...

**6**

votes

**0**answers

136 views

### Does the random graph interpret the random directed graph?

The random graph is the Fraisse limit of the class of finite graphs, the random directed graph is the Fraisse limit of the class of directed graphs, a directed graph is just a set with a binary ...

**4**

votes

**3**answers

276 views

### Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...

**23**

votes

**4**answers

837 views

### What nodes of a graph should be vaccinated first?

Consider a graph, choose some "p: 0<p<1" (probability to infect the neighbor node).
Choose some random number "K" of nodes which are "infected" initially.
So we ...

**1**

vote

**1**answer

197 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 ...

**6**

votes

**0**answers

160 views

### Is there are good algebraic model of random n-hypergraphs?

Suppose $F$ is a finite field and $-1$ is a square in $F$. Let $E$ be the binary relation on $F$ where $(a,b) \in E$ iff $a - b$ is a square. Then $(F,E)$ is called a Paley graph. Paley graphs are ...

**5**

votes

**2**answers

212 views

### Triangle coloring in random graph

Given $m$ persons (men and women) and $n$ balls, each person randomly selects $3$ balls. Once all of them complete the selection process, we color the balls with $2$ colors, white and black, such that ...

**0**

votes

**1**answer

62 views

### Sources of information on algorithms for finding Hamiltonian cycles (Pósa)

I research various algorithms in complex networks and I am quite new in this field. I am currently focusing on random geometric graphs - Pósa's algorithm for finding a hamiltonian cycle. Can you ...

**5**

votes

**0**answers

105 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 ...

**2**

votes

**0**answers

103 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. ...

**2**

votes

**1**answer

83 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

183 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 ...

**3**

votes

**1**answer

68 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)...

**3**

votes

**0**answers

129 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 ...

**3**

votes

**1**answer

85 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. ...

**179**

votes

**3**answers

91k 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 ...

**3**

votes

**1**answer

116 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. ...

**4**

votes

**2**answers

99 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, ...

**0**

votes

**0**answers

95 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 $\...

**0**

votes

**1**answer

72 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 ...

**4**

votes

**1**answer

103 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 ...

**1**

vote

**1**answer

110 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 $...

**-2**

votes

**1**answer

46 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=\...

**0**

votes

**0**answers

51 views

### Average number of edges of an induced graph by using the edge-based node selection technique on a graph with arbitrary degree distribution

Let $G(U,V,E)$ be a simple, undirected, bipartite graph and $U=\{u_1,u_2,{\cdots},u_n\}$ and $V=\{ v_{1},v_{2},\cdots,v_{n}\}$. Let $d_k^l$ be the number of vertex with degree $k$ in $l$, where $l \in ...

**4**

votes

**1**answer

195 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$...

**5**

votes

**0**answers

214 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 ...

**11**

votes

**1**answer

316 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 ...

**1**

vote

**1**answer

95 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

55 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**

vote

**1**answer

60 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]...

**1**

vote

**0**answers

47 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 ...

**12**

votes

**1**answer

392 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 ...

**5**

votes

**1**answer

100 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 ...

**1**

vote

**1**answer

204 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:
...

**4**

votes

**0**answers

61 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$ ...

**3**

votes

**1**answer

116 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**

vote

**1**answer

108 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 ...

**2**

votes

**2**answers

106 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**

vote

**1**answer

83 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}...