1,373 problems

Alon's spectral-radius conjecture. For every $\varepsilon>0$,

Kahn–Kalai conjecture. The threshold satisfies

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…

Let $\mathcal{G}$ be a fixed $k$-regular graph and let $\mathcal{G}_p$ be a random lift of degree $p$. Denote by $\lambda_{\mathrm{new}}(\mathcal{G}_p)$ the maximum absolute value…

Let $(G,o)$ and $(H,o')$ be rooted graphs, with the space of isomorphism classes of rooted graphs equipped with the local metric. Restrict to transitive graphs satisfying…

Let $G^+$ and $G^-$ be two copies of a finite graph $G$ with vertex labels $[n]:=\{1,\ldots,n\}$. For $H\subseteq[n]$, form the bunkbed graph $G^\pm=(V^\pm,E^\pm)$ with…

Kohayakawa–Kreuter Conjecture for Families. For tuples $(\mathcal{H}_1,\ldots,\mathcal{H}_r)$ that avoid the pathological cases, a threshold for…

Triangle-free process independence-number conjecture. The triangle-free process has asymptotically the smallest independence number among all $n$-vertex triangle-free graphs.

Let $G(n,p)$ be the binomial random graph on $n$ vertices, where $0\leq p=p(n)\leq 1$, and let $\delta(G)$ denote its minimum degree. Frieze–Krivelevich conjecture. With high proba…

Let $(\Gamma_n)_n$ be a sequence of planted subgraphs in the recovery model, and suppose there is a gap between the information-theoretic limit and the performance of the proposed…

Fractional triangle decomposition threshold conjecture. For every $\varepsilon>0$ and $p \geq (1+\varepsilon) \sqrt{\frac{3 \log n}{2n}}$, w.h.p. $G(n,p)$ admits a fractional trian…

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

Erdős–Palka conjecture. For every $C>1$, with high probability $G(n,C/n)$ contains an induced tree of linear size.

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 $G$ be the adjacency matrix of the Erdős–Rényi graph $G(n,1/2)$. Babai's conjecture. The matrix $G$ has no repeated eigenvalues with probability $1-o(1)$. This conjecture conce…

Consider real-world networks whose degree distribution follows a power law, and let PageRank be the centrality measure assigned to their vertices. Power-law hypothesis. The PageRan…

For a fixed $k\geq 2$, let $G^k_{n,p}$ be the random $k$-uniform hypergraph, and let $H$ be a fixed $k$-graph. The $k$-graph analogue replaces graphs by $k$-graphs, $G_{n,p}$ by…

Let $Q^d$ be the graph with vertex set $\{0,1\}^d$ in which two vertices are adjacent if they differ in exactly one coordinate, and write $n:=2^d$ for its order. Let $Q^d_p$ be the…

Consider the planted clique problem in an Erdős–Rényi random graph on $n$ vertices, where the planted clique has size $k$. Planted clique conjecture. Recovery is computationally in…

Kohayakawa–Kreuter conjecture. There exist constants $c,C>0$ such that

A Hamilton cover of a graph $G$ is a collection of Hamilton cycles whose union contains all edges of $G$. Its size is at least $\left\lceil \frac{\Delta(G)}{2}\right\rceil$, where…

Yuster's conjecture. For every fixed $\varepsilon>0$, if

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…