113 problems

Let $G$ be a random $\Delta$-regular graph, and fix an activity parameter $\lambda>0$. The hard-core model on $G$ is the distribution on independent sets $I$ with probability propo…

Kim–Vu sandwich conjecture. With high probability, $G_d(n)$ can be sandwiched between two random binomial graphs $G(n,p)$ whose edge probabilities are asymptotically equal to…

Let $A$ be the adjacency matrix of a uniformly random simple $d$-regular graph on $N$ vertices, let $H=A/\sqrt{d-1}$, and consider the bulk eigenvalues of $H$. Fixed-degree random-…

Let $\mathbf G_d(n)$ be a random $d$-regular graph on $n$ vertices, and let the max-cut and min-bisection of $G$ be measured by the numbers of edges in the respective cuts. Zdeboro…

For an integer $q\geq 3$ and real $\beta>0$, let $G$ be a random $d$-regular graph and let $c\mu_{G,\beta}$ be the ferromagnetic Potts-model distribution on configurations $[q]^V$,…

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 conjecture. We have

First-order phase transition conjecture. The phase transition on random $\Delta$-regular graphs is of first order, and

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…

Let $\Delta\geq 3$ and $q>2$, and consider the random cluster model on a random $\Delta$-regular graph. Denote its critical point by $\beta_c(q,\Delta)$. Critical-point formula con…

Fix an integer $d$ and choose a $d$-regular graph uniformly at random from the graphs on $n$ vertices. The random walk is said to have cutoff when its distance from equilibrium dro…

Let $\mathbb{T}_d$ be the infinite $d$-regular tree, and consider processes on it that are factors of independent identically distributed labels. A random $d$-regular graph is a gr…

Let $\mathcal{G}_{n,r}$ be a random $r$-regular graph with independent exponential edge weights, and let $\operatorname{Diam}_w(\mathcal{G}_{n,r})$ denote its weighted diameter. Se…

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 $Q_{n,d}$ be the adjacency matrix of a uniformly random simple $d$-regular graph on $n$ vertices. Random regular nonsingularity conjecture. For every $d\ge 3$, $Q_{n,d}$ is alm…

Let $G_{n,d}$ be a uniformly random simple $d$-regular graph, and let $\lambda(G)$ denote the maximum absolute value of its nontrivial adjacency eigenvalues. Assume that $d\le n/2$…

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 a random $d$-regular graph be percolated by deleting each edge independently with probability $1-p$, and suppose that $p>1/(d-1)$ is fixed. Let $T$ denote the mixing time of th…

Let $k$ be the degree of a random $k$-regular graph, and consider bond percolation on it. Critical-component-size conjecture. At the threshold parameter … the largest critical comp…

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…

Tree-likeness conjecture. The conclusion of Theorem can be improved to this value of $r$, and the tangle with parameter $m$ already causes $g_r$, or a lower-indexed $g_i$, to fail…

Let $G$ be a random $5$-regular graph, and let w.h.p. mean with high probability as the number of vertices tends to infinity. A proper $3$-coloring assigns one of three colors to e…

Let $k>2$, let $d$ be an integer, and let ${{\mathcal G}_{n,d}}$ be a random $d$-regular graph. Here, $k$-colorable means that the vertices can be colored with $k$ colors so that a…

Let $G_{n,k}$ be the uniform random $n$-vertex $k$-regular graph. Random-regular rigidity conjecture. For every $d\geq 2$ and $k\geq 2d$, the random graph $G_{n,k}$ is a.a.s. $d$-r…

Oriented Kesten–McKay conjecture. The ESD of $M$ converges in probability, as $n\to\infty$, to the oriented Kesten–McKay law on $\mathbb{C}$ with density