523 problems

Erdős–Rényi face conjecture. The expected number of faces is

Let $\Gamma$ be a random labeled graph on $n$ vertices, let $\operatorname{Aut}^{\pi}(\Gamma)$ denote its two-fold automorphism group, and let $\mathbb{E}$ denote expectation over…

Random embedding edge-type conjecture. The expected numbers of bad singular edges, good singular edges, and regular edges are respectively

Let $G$ be a random $d$-regular triangle-free graph on $n$ vertices, with $n\to\infty$. The claimed sharp transition is at $d=\frac{\sqrt{3}}{2}\sqrt{n\log n}$: if…

Fix $\alpha>1$. Let $G_n\sim G(n,\alpha/n)$, let $B_n$ be its non-backtracking matrix, and order the eigenvalues by nonincreasing modulus, so that…

Let $G_n^{\mathrm{geo}}$ be a random geometric graph generated by independent uniform points on a high-dimensional sphere, with connection function $K_n$ applied to endpoint inner…

Let $H$ be a fixed connected graph, let $G_{n,p}$ be the Erdős–Rényi random graph, and let $X_H$ denote the number of copies of $H$ in $G_{n,p}$. Define…

Let $G(n,1/2)$ be the Erdős–Rényi random graph on $n$ vertices, and let $G$ be controllable and minimally controllable when it has the corresponding controllability properties for…

Let $G$ be a random $\Delta$-regular bipartite graph, and let $Z_{G,q}(\beta)$ be the partition function of the anti-ferromagnetic $q$-state Potts model on $G$. Random-regular-grap…

Let $\mathscr{V}^\lambda$ be the hyperbolic Poisson–Voronoi graph. For $r>0$, consider a geodesic in $\mathscr{V}^\lambda$ connecting the Voronoi cells containing $-r$ and $r$, and…

Let $G$ be a finite graph, let $\lambda(G)$ denote the spectral radius of its adjacency matrix, and let $G_p$ be obtained from $G$ by retaining each edge independently with probabi…

Let $\mathcal{G}_{n,d}$ be the uniform model of random $d$-regular graphs on the vertex set $[n]=\{1,2,\ldots,n\}$. A $p$-orientation is an orientation of a $d$-regular graph in wh…

Cohomology-vanishing conjecture. If

Let $V\subseteq\mathbb{R}$ with $|V|=n$, and let the known distances be distributed as in $G(V,\lambda/n)$ for a parameter $\lambda>0$. Call a subset reconstructible if every injec…

Connectivity conjecture. If

Let $G_{n,p}$ be the random graph on $n$ vertices, let $G_{n,p}^r$ denote its $r$th power, and write $\chi(G)$ and $\alpha(G)$ for the chromatic and independence numbers of a graph…

Triangle-free graph discontinuity conjecture. The function

Let $G$ be a graph, and write $v(G)$ and $e(G)$ for its numbers of vertices and edges. For a subgraph $F\subseteq G$, define $p_E(G)$ to be the smallest $p$ such that … for every…

Bollobás–Pebody–Riordan conjecture. For the model with $p(n)=1/2$, the chromatic polynomial is almost complete.

Let $d$ be a degree parameter satisfying $d\gg\log n$. For sequences $p_1=p_1(n)\sim d/n$ and $p_2=p_2(n)\sim d/n$, consider a random $d$-regular graph $\mathbb R(n,d)$ and binomia…

Linear growth conjecture. There exists a linear function $\varphi$ such that, whenever

Let $H_1,\dots,H_r$ be graphs. For a graph $H$, write $m_2(H)$ for its 2-density, and, when $m_2(H_1)\geq m_2(H_2)$, define the mixed 2-density by … Let $G_{n,p}$ be the binomial ra…

Let $p=\omega(1/\sqrt n)$ with $p\leq 1/2$, and let $G$ be sampled from either $\mathbb{G}(n,p)$ or $\mathbb{G}(n,1-p)$. A graph is $k$-vertex-minor universal if every graph on any…

For a graph $H$, let $p_c(H)=p_c(n,H)$ be the unique $p$ such that … Define the expectation threshold by … The second Kahn–Kalai conjecture. There is a fixed $K$ such that for any…

Yuster's triangle-packing conjecture. If