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

339 questions
Filter by
Sorted by
Tagged with
1 vote
29 views

• 149
75 views

• 43
60 views

• 11
136 views

### Example of random walk in a random environment (RWRE) saying things on the environment

I was wondering if anyone is aware of works/articles/examples where random walks in a random environment (RWRE) are actually used for obtaining information on the random environment. To clarify a bit, ...
• 59
1 vote
69 views

### Benjamini-Schramm convergence: convergence on metric balls implies weak convergence?

In the famous paper by Benjamini-Schramm 2001, they consider the space of rooted graphs with uniformly bounded degrees, this space modulo rooted graph isomorphism is denoted by $\mathcal X$. This ...
• 492
46 views

### A question related to contiguity of random regular graphs

I am looking for a reference for the following fact. Let $r\geq 3$ be constant, let $G(n,r-2)$ be a random (simple) $(r-2)$-regular graph and let $H(n)$ be an independent random Hamiltonian cycle (on ...
• 123
29 views

• 131
75 views

### Random walks on randomly evolving graphs

I am interested in analyzing a random walk on a growing tree with vertices labelled on a tree with following properties. The number of nodes at depth $k$ is a an exponential function of $k$. One can ...
• 121
298 views

### Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$

Let $G = (V, E)$ be a uniform random graph on $2n$ labeled vertices and let $S \subseteq {V}$ be the set of vertices with degree $\ge n$. Then what happens to $\mathbf{P}(|S|=n)$ as $n \to \infty$? ...
1 vote
46 views

### Diameter of component graph of uniform spanning forests on the amenable transitive graph with super polynomial growth

According to the paper Benjamini, Kesten, Peres, and Schramm - Geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12 (Annals, 2004), the diameter of the component graph of the ...
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,748
145 views

### Union of two copies of uniform spanning forest on $\mathbb{Z}^3$ is transient? [closed]

Let $G$ be the (random) graph which is the union of two independent copies of the uniform spanning forest on $\mathbb{Z}^3$. Question: Is (the simple random walk on) $G$ transient almost surely?
1 vote
71 views

### Probability of randomly finding a loop in a (directed) Bernoulli random graph

This problem is inspired by an activity at work, where each person was tasked with introducing another person in the onboarding class, sequentially. Problem Statement Given $N$ people. For each pair ...
381 views

### What is this Ramsey problem?

Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
• 3,413
1 vote
468 views

### Vertex degree on random graphs

Let $p = d/n$ with $d$ constant. How do I prove that, with high probability, $G_{n,p}$ contains a vertex of degree at least $(\log n)^{1/2}$, where $G_{n,p}$ is a graph with $n$ vertices and the ...
• 21
1 vote
112 views

### Probability of (single) connecting paths in Erdos-Renyi graphs

In an Erdos-Renyi graph with labeled vertices in $(1, ..., N)$, and for any pair of vertices $(r, s)$ with $r < s$ and a length $l$ in $(1, ..., s-r)$, I am looking for the probability of there ...
• 129
194 views

### Quasi-random vs pseudo-random graphs

My question is somehow concerning terminology on extremal graph theory. Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...
• 1,543
240 views

### Expected doubling constant of a random Erdős–Rényi graph

Consider the $G(n,p)$ random graph model where $n$ is a large'' positive integer and $p\in (0,1)$. We may equip every realized random graph $G$ with its shortest path distance, making it into a (...
• 4,809
44 views

### Hyperbolic random geometric graphs with less clustering

The hyperbolic random geometric graph $G_{\mathbb{H}}$ consists of a $N$ uniformly random points (within a disk of radius $R$ centred at the origin) of the hyperbolic plane $\mathbb{H}$, connected ...
• 612
1 vote
75 views

### Concavity of expected size of a maximum matching (in a bipartite graph) w.r.t. edge probability

Given a n*n bipartite graph where each edge (between any two nodes on the opposite side) is formed i.i.d. with probability $p$, can we show a concavity result on the expected size of a maximum ...
• 53
1 vote
91 views

### Limit of alternating sum of factorial moments which diverge

Consider the non-negative, integer valued random variable $X$, and its $i^{\text{th}}$ factorial moment $E_{i}[X]$. Then we have that $$P(X=0) = \sum _{i=0}^{\infty} \frac{(-1)^i E_{r}[X]}{ i!}$$ ...
• 612
95 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 ...
• 123
Consider a square lattice (random) graph $G$ embedded on a toroidal surface. Each edge $(i, j)$ of the graph has an associated likelihood probability $p_{ij}$. The probabilities $p_{ij}$ come from a ...