6 problems

Let $N$ be the number of vertices, let $d=d(N)$, and let $\bm{G}_{N,d}$ denote a uniformly random $d$-regular graph. For edge probabilities $p_*$ and $p^*$, let…

Let ${\mathcal G}(n,d)$ denote the random $d$-regular graph on $n$ vertices, and let ${\mathcal G}(n,p)$ denote the Erdős–Rényi random graph with edge probability $p$. For…

The homogeneous Erdős–Rényi significance conjecture. The friendship paradox is significant for every $\lambda\in(0,\infty)$:

Let $L_n(t)$ denote the size of the largest component of the critical dynamical Erdős–Rényi graph on $n$ vertices at time $t\in[0,1]$. Maximum component-size conjecture. As…

Let $G$ be drawn from the Erdős–Rényi random graph $G(n,d_n/n)$, and let $X_t(i)$ denote the opinion of vertex $i$ at time $t$ under majority dynamics. Write $\lim_t X_{2t}(i)$ for…

Connectivity-threshold conjecture. The results established for denser Erdős–Rényi graphs, in particular $H_j=N+o(N)$, are true already when