41 problems

Random regular graph singularity conjecture. For every $3\leq d\leq n-1$, $A_{n,d}$ is nonsingular with probability $1-o(1)$.

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 $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…

Edge universality conjecture. We have

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 $\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 $\epsilon>0$,

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…

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