44 problems

Optimal-scale conjecture. For each $C>0$ there is an $\varepsilon>0$ such that, for every monotone ${\cal F}$, there exists

For a non-empty partial Latin square $P$, define its density by … Let $\mathbf{L}$ be a random Latin square of order $n$. The density threshold conjecture. As $n\to\infty$, … When…

For the rainbow-connectivity game $\mathcal{C}_{s,n}$, let $b_{\mathcal{C}_{s,n}}$ denote its threshold bias. Assume that $s=\omega(\log(n))$. Rainbow-connectivity threshold conjec…

Let $\mathcal{G}^{(q)}(n,p)$ be the random $q$-uniform hypergraph on $n$ vertices, and let an $(n,q,r)$-Steiner system be a collection of $q$-sets containing every $r$-set exactly…

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…

For $q\in[0,1]$, call a graph $J$ $q$-sparse if … where $\mathbb{E}_qX_I$ is the expected number of copies of $I$ in $G_{n,q}$. Sparse-graph reformulation. There is a fixed $K$ suc…

VC-dimension–blowup threshold conjecture. For any graph $H$,

Homomorphism–blowup threshold conjecture. For any graph $H$,

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…

Let $G_r(n,p)$ be the random $r$-uniform hypergraph, and let $C^{(r)}_{n,\ell}$ be the $r$-uniform $\ell$-cycle on $n$ vertices. Write $Z(C^{(r)}_{n,\ell})$ for the number of copie…

Let $\delta^*_{\operatorname{3MIN}}$ denote the threshold for reliable computation with noisy circuits of 3MIN gates, and let $\delta^*(3)$ denote the threshold for reliable comput…

Let $G\sim G(n,n,p)$ be a random bipartite graph with two parts of size $n$, and let $\operatorname{tc}_3(G)$ be the minimum number of monochromatic trees whose vertices cover $G$…

Let $G_d(n,p)$ be the random geometric graph model, and let $\mathcal{F}$ be a non-trivial monotone graph property, where monotonicity means monotonicity under adding edges. Random…

For given $n$, $k\geq2$, and $p$, let $F_k(n,p)$ be the random $k$-SAT formula obtained by including each of the $\binom{2n}{k}$ possible $k$-clauses independently with probability…

For each $n$, independently include each symbol in each list $L_{ij}\subseteq\{1,\dots,n\}$ with probability $p$, and let $\mathcal{F}_{\mathrm{Latin}}$ be the property that there…

Let $G(n,p)$ be the binomial random graph on vertex set $[n]$, with each possible edge included independently with probability $p=p(n)$. A square of a Hamilton cycle is the second…

Let $t,k,\lambda\in\mathbb N$ with $k>t$, let $V$ be an $n$-element set satisfying the divisibility conditions $\binom{k-i}{t-i}\mid\lambda\binom{n-i}{t-i}$ for every…

For $d\in\mathbb N$, a $d$-dimensional order-$n$ Latin hypercube is a $d$-dimensional array indexed by $[n]^d$ with entries from $[n]$, such that every line contains each symbol ex…

Let $\kappa\geq4$ be even and let $2\leq j\leq\lfloor\kappa/2\rfloor$ be even. Let $\{\mathcal{E}_n\}$ be the sequence constructed in the two stated theorems. Upside-down-well limi…

Let $D$ be the discrete Molchanov–Vainberg Laplacian, let $\boldsymbol{\Theta}_{m,\kappa}(D)$ and $\boldsymbol{\Theta}_{\kappa}(D)$ be the threshold sets defined in the paper, and…

Fix $\kappa\geq4$ with $\kappa\in\mathbb{N}_e$, and let $\{\mathcal{E}_n\}$ be the sequence from the stated theorem. Let $A_{j\kappa}=\sum_{i=1}^{2}A_i(j,\kappa)$ be the conjugate…

Fix $\kappa\geq4$ with $\kappa\in\mathbb{N}_e$, and let $\{\mathcal{E}_n\}_{n=0}^{\infty}$ be the strictly decreasing sequence from the stated theorem, with limit…

Let $D$ be the discrete Molchanov–Vainberg Laplacian, let $\boldsymbol{\Theta}_{m,\kappa}(D)$ denote the threshold sets defined in the paper, and let $\mathbb{N}_e$ denote the even…

Let $X$ be a finite set and let ${\mathcal F}\subseteq2^X$ be increasing. Let $q({\mathcal F})$ be the expectation-threshold and $q_f({\mathcal F})$ the fractional expectation-thre…

Talagrand's fractional expectation-threshold conjecture. There is a universal constant $K$ such that