41 problems

Tracy–Widom and proportion conjecture. The distribution of $\lambda_\pm(G)$, normalized in this way, converges as $N\to\infty$ to the $\beta=1$ Tracy–Widom distribution rather than…

Let $G_{n,d}$ be a uniformly random simple $d$-regular graph, and write … for the maximum absolute value of its nontrivial adjacency eigenvalues. A $d$-regular graph is Ramanujan w…

Let $G_n$ be a sequence of finite 3-regular graphs with growing girth, converging locally to the 3-regular tree $T_3$, and assume that the thresholds $p^{G_n}$ remain bounded away…

Non-degeneracy conjecture. For every $c\in (\kappa h_{\min},\kappa h_{\max})$, $U_n$ given $\operatorname{Conset}_n(h,c)$ lies asymptotically in $\operatorname{Gibbsnondeg}(c)$.

Let $G$ be a random regular graph, and let the max-cut be a partition of its vertex set maximizing the number of crossing edges. Let the bisection width be the minimum number of cr…

Let $\mathcal{G}_{d,N}$ denote the space of random $d$-regular graphs on $N$ vertices, and let $T_N: \mathcal{G}_{d,N} \to \mathbb{R}$ be a sequence of statistics that distinguishe…

Minimum-degree diameter conjecture. For every $d\geq3$ and $\epsilon0$,

Let $d=d(n)\in[3,n-1]$, and let $G\sim G(n,d)$ be a random $d$-regular graph. An independent spanning tree (IST) family is a collection of spanning trees whose root-to-vertex paths…

Random matching decomposition conjecture. The event that the disjoint union belongs to $A_n$ holds with high probability if and only if the event that a uniform random $d$-regular…

Isaev–McKay–Southwell–Zhukovskii conjecture. If $d_2=\omega(1)$, then there exists a coupling of $G_{\oplus}\sim G(n,d_1)\oplus G(n,d_2-d_1)$ and $G\sim G(n,d_2)$ such that

Gao–Isaev–McKay conjecture. There exists a coupling such that

Let $d\geq 3$, let $\mathcal{G}_{N,d}$ be a uniformly random $d$-regular graph on $N$ vertices, and let $k_d^{\mathrm{ind}}=\lfloor\kappa_d(\alpha_d^\star)\rfloor$, where…

Majority Dynamics conjecture. For every $\varepsilon>0$, with high probability the number of oscillating vertices lies in

Let $H$ be a $d$-regular multigraph on $k$ vertices, and let $\varepsilon>0$. Write $\mathcal{L}_{m}(H)$ for an $m$-sheeted lift of $H$. The operators…

Yuster's triangle-decomposition conjecture. If $d\gg\sqrt{n\log n}$ and $d$ is even, then asymptotically almost surely $G_{n,d}$ has a $K_3$-decomposition provided $3\mid dn$.

Random 4-regular graph rigidity conjecture. A random $4$-regular graph with $n$ vertices is globally rigid in $\mathbb{R}$ with high probability.

Let $\mathcal{G}(n,d)$ denote the uniform random labelled $d$-regular graph. Let $0\leq d_1\leq d\leq n-1$ be integers, excluding $(d_1,d)=(1,2)$ and $(d_1,d)=(n-3,n-2)$. Gao–Isaev…

Let $\boldsymbol{G}_{d_1+d_2}\sim\mathcal{G}(n,d_1+d_2)$, and let $\mathcal{R}_{d_1}(G)$ be the set of $d_1$-regular spanning subgraphs of $G$. For $d_1,d_2>0$ with…

For $d_1,d_2\in\mathbb{N}$ with $d_1+d_2\leq n-1$, let $\mathcal{G}(n,d)$ denote the uniform random $d$-regular graph. Let $\mathcal{G}(n,d_1)\oplus\mathcal{G}(n,d_2)$ denote the d…

Let $d_1=d_1(n),d_2=d_2(n)\in\mathbb{N}:=\{0,1,\ldots\}$ satisfy … Let $\mathcal{S}_n(d_1,d_2)$ be the set of pairs of edge-disjoint graphs on $[n]$ whose respective degrees are…

Let $d\geq 3$ be fixed, and let $\kindactual{d}$ denote the largest positive integer $k$ such that, asymptotically almost surely, the random $d$-regular graph $\mathcal{G}_{n,d}$ c…

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…

Edge-universality regime conjecture. The assertion in (1.2) holds if and only if

Edge universality conjecture. We have

Normality conjecture. Suppose