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

319 questions
Filter by
Sorted by
Tagged with
63 views

### Connected components in random regular graphs

Suppose we take a random regular graph $G_{2n, r}$, where $n$ is large. Let us also assume that $r$ is fixed, (not dependent on $n$). Let's say that half of the vertices of the graph are colored black ...
1 vote
83 views

1 vote
249 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
54 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 ...
453 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. ...
139 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 ...
142 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 ...
79 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
117 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....
139 views

278 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
91 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$, ...
429 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
84 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 ...
111 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
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....
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. (...