17 problems

Limiting-constant conjecture. There is some constant $C>0$ such that

Sharp-threshold conjecture. In the language of thresholds, $RPS(n)$ exhibits a sharp threshold.

Creignou–Daude conjecture. Hypothesis A holds for random constraint satisfaction problems with domain size two.

Bounded-degree spanning tree threshold conjecture. For any such sequence $\{T_n\}$, its threshold function is of order $\frac{\log n}{n}$.

Krauth–Mézard's sharp threshold conjecture. A sharp threshold occurs at $\alpha^*_{\kappa}$: for constraint densities below $\alpha^*_{\kappa}$, solutions exist with high probabili…

Let $H_{n,s,p}$ be the random $s$-uniform hypergraph obtained from the complete $s$-uniform hypergraph on $n$ vertices by retaining each edge independently with probability $p$. Co…

Let $k\geq 3$ be fixed, and let $H_k(n,m)$ be the random $k$-uniform hypergraph on $n$ vertices obtained by selecting $m$ edges uniformly, independently, and with replacement from…

Consider graph database alignment with correlation parameter $\rho$, where exact recovery has threshold … Almost exact recovery means finding an estimator that coincides with the p…

Let $q\geq 3$, let $d>0$, and let $\mathbb G(n,d/n)$ be the binomial random graph with edge probability $d/n$. Write $\chi(\mathbb G(n,d/n))$ for its chromatic number. Sharp-thresh…

Let $\Gamma$ be a random graph in $G(n,p(n))$, and let $\mathcal{CFS}$ denote the graph property used to characterize quadratic divergence of the associated right-angled Coxeter gr…

Friedgut's narrow DNF conjecture. Every monotone function that has a coarse threshold is approximable by a narrow DNF.

Let $J(n,q)$ be the random $(n,q)$-jigsaw, and let reconstructibility mean that the jigsaw is uniquely determined by its deck. Write … Critical-window conjecture. As $n\to\infty$,…

Threshold convergence conjecture. The sequence $d_n$ converges to a limit $d_c$.

Sharp-threshold characterization conjecture. There are constants $K,\epsilon,\delta>0$ such that, for large $n$, every $\alpha\in(\delta,1-\delta)$ and every $p$ satisfying

Let $X$ be the random flag complex on $n$ vertices. For fixed $k\geq 0$, define … Then the positive lower-threshold constant conjecture. One has … This asserts that the lower thres…

For the Coloring, K-SAT and NAE-K-SAT models, let $p(N,M)$ be the probability that an instance with $N$ variables or vertices and $M$ edges or clauses is colorable or satisfiable.…

For each of the Coloring, K-SAT and NAE-K-SAT models, let $p(N,M)$ denote the probability that an instance with $N$ variables or vertices and $M$ edges or clauses is colorable or s…