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

289
questions

10
votes

1
answer

360
views

### (Asymmetric) matrix power series in closed form: $\sum_{i=0}^{\infty} A^i \left(A^i\right)^{\top}={?}$

Let $A\in \mathbb{S}^{N\times N}$ be a symmetric, real and stable matrix, i.e., $\rho(A)<1$, where $\rho(A)$ stands for the spectral radius of $A$. Then, $$\sum\limits_{i=0}^{\infty} A^{2i}=\left( ...

1
vote

2
answers

80
views

### Which infinite random graphs with percolation threshold $p_c=0$ are transient?

I am interested in long-range percolation models with heavy-tailed degree distributions such as DHH13, GLM21, Y6. The simplest example is scale-free percolation in which vertices are elements $\mathbb{...

1
vote

1
answer

89
views

### Hammersley-Clifford theorem

The paper spatial interaction and the statistical analysis of lattice systems by Besag (1974) presents an alternative proof for the Hammersley-Clifford theorem.
In order to prove the HM theorem, Besag ...

1
vote

0
answers

43
views

### Angles between edges of a geometric graph and graph invariants

Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph?
I'm interested to see what else is ...

5
votes

3
answers

187
views

### Probability of an edge in a random graph

Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence.
...

1
vote

1
answer

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

0
votes

0
answers

32
views

### Asymptotic probability of a short path in the LEAF problem

When reading about total NP search problems (specifically their oracle versions) I started analysing the computational problem $\text{LEAF}$:
An instance $(G,v_0)$ is given by an undirected graph $G$, ...

2
votes

1
answer

119
views

### Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?

A uniformly random $r$-regular bipartite graph on $n$ vertices is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular ...

2
votes

1
answer

59
views

### Are the eigenvalues of the 1D lattice with random weights known?

Consider the adjacency matrix $\mathbf{A}$ of a one dimensional lattice of size $N$. That is, $A$ is a $N\times N$ matrix with $A_{ij}=1$ if vertex $i$ adjacent to vertex $j$ (there exists an edge ...

1
vote

1
answer

105
views

### how to compute the probability that a random graph has two components? [closed]

This question is an example in the book Introduction to Probability Models 11th edition (Sheldon M.Ross). 3.6.2 A random graph:
A graph has $V$ nodes and a set $A$ of pairs of nodes in $V$ called arcs....

0
votes

0
answers

108
views

### Expected chromatic number of random subgraph

Let $G$ be a fixed graph and let $G_p$ be a random subgraph of $G$ where every edge is kept independently with probability $p$. According to [1] and [2] the paper [3] proves
$$
\mathbb{E}[\chi(G_p)] \...

1
vote

0
answers

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

1
vote

0
answers

45
views

### Canonical representation of the a probability distribution for Hammersley Clifford Theorem

I'm reading the following paper
http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/GibbsFieldEst/BesagJRSSB1974.pdf
On page 7 they give the result that
$$Q(\textbf{x}) = \sum_{1 \leq i \leq n} ...

4
votes

0
answers

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

1
vote

1
answer

70
views

### Empirical degree distribution of random $n$ vertices labeled rooted tree converges to Poisson distribution

I am reading Louigi's lecture note on random trees and graphs here. I get stuck on part (b), Exercise 1.2.3 on page 19, which says the following:
Let $T_n$ be uniformly drawn from $\mathcal{T}_n$, ...

6
votes

1
answer

413
views

### Graphs resembling the math genealogy graph must have concentration in a small number of families?

I was talking with a non-mathematician the other week at a workshop about the fact that many mathematicians, like myself, are indexed in the math genealogy database. We talked a little about how many ...

1
vote

0
answers

73
views

### Longest close common subsequence but for continuous random variables

We have two copied sequences of correlated continuous positive random variables that are independent of each other $(X_{n})\perp(Y_{n})$ and equal in distribution $X_{n}\stackrel{dis}{=}Y_{n}$ for ...

3
votes

0
answers

73
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 "...

1
vote

0
answers

78
views

### In percolation on a lattice, how is "infected" status correlated for points in a region around the origin?

Consider independent bond percolation on $\mathbb{Z}^2$, with $p>p_c$ so that the process is supercritical. For any site $x$ let $Y_x$ be the indicator of $x$ belonging to the infinite open cluster....

0
votes

0
answers

62
views

### Contiguity of uniform random regular graphs and uniform random regular graphs which have a perfect matching

Let us consider $\cal{G}_{_{n,d}}$ as the uniform probability space of d-regular graphs
on the n vertices $\{1, \ldots, n \}$ (where $dn$ is even). We say that an event $H_{_{n}}$ occurs a.a.s. (...

1
vote

0
answers

63
views

### Understanding the finale of the proof of Komlós' and Szemerédi's limit distribution of Hamiltonian random graphs

My question is about the end of the proof of Theorem 1 in [Komlós, Szemerédi (1983)], more precisely the arguments in Subsection 2.3. Let me state the beautiful theorem I am trying to understand in my ...

1
vote

1
answer

117
views

### Bound on $i$th largest eigenvalue in a large Erdos-Renyi graphs

Typical magnitude of $i$th largest eigenvalue of an Erdos-Renyi random graph seems to decay at least exponentially with $i$. Is there an analytic expression for the constant in the exponent, or a nice ...

4
votes

0
answers

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

1
vote

1
answer

64
views

### Does exponential degree distribution entail Log-normal distance distribution in large complex graphs?

We've been exploring the graph structure of a large genealogical data base (WikiTree) of which main connected component contains about 23 million nodes. The graph edges are defined by any direct ...

2
votes

1
answer

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

1
vote

0
answers

54
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

46
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

137
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

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

3
votes

1
answer

214
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

187
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

34
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

343
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

167
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

60
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

128
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

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

8
votes

1
answer

241
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

323
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

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

2
votes

1
answer

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

9
votes

1
answer

219
views

### Is there a 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

233
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

95
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

136
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

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

3
votes

1
answer

111
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

211
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

85
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

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