239 problems

Kahn–Kalai conjecture. The threshold satisfies

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…

Let $X$ be a finite nonempty set, let $\mathcal{F}\subseteq 2^X$ be a nontrivial monotone property, and define … and … where $w(G,p)=\sum_{S\in G}p^{|S|}$ and…

Let $c_{i,j}$, for $i,j\in [n]$, be independent identically distributed positive random variables, and let $A_n$ be the minimum total cost of assigning $n$ faculty to $n$ slots, wi…

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 $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…

Benjamini–Häggström–Mossel range conjecture. If $f\in_r{\operatorname{Hom}}_{v_0}(Q_n)$, then

Let $P$ be a finite poset, let $w(P)$ denote its width, and let $\delta(P)$ be the maximum, over distinct $x,y\in P$, of $\min\\{p(x\prec y),p(y\prec x)\\}$. The Kahn–Saks conjectu…

Subquadratic conjecture.

Let $n$ denote the number of locations in the symmetric rendezvous problem, and let $\mathrm{AW}$ denote the Anderson–Weber strategy. Anderson–Weber's conjecture. An improvement ov…

Let $T$ be the random tree under consideration, let $t$ denote its size parameter, and let $\operatorname{cov}_\ell(T)$ be the minimum number of paths of length at most $\ell$ need…

Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ be graphs on the same vertex set, each of maximum degree $Delta$, and let $chi(G_1,G_2)$ be the minimum number of colors in a simultaneous prope…

Kahn's sharp range conjecture. The absolute constant in the bound $R(f)=O(1)$ with high probability can be taken to be $5$; equivalently,

For each integer $k\ge 2$, let $\boldsymbol{F}(k,\alpha)$ denote a random $k$-SAT formula with clause density $\alpha$. Sharp satisfiability threshold conjecture. For every…

Balanced-monotone-family conjecture. The success probability $p_{\mathrm{monotone}}(t)$ tends to $0$ as $t$ grows. This is stronger than the intersecting-family conjecture because…

Levine's conjecture. The success probability $p(t)$ tends to $0$ as the number of players $t$ grows. This is the original challenge posed by Levine and is the main hat-game problem…

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.

Komarov–Winkler's conjecture. The upper bound for the unknown gambler can be improved to

Connectivity conjecture. Setting $K_{\mathrm{avg},n}$ to any finite number larger than or equal to two should be sufficient to ensure that $\mathbb{H}(n; \pmb{\mu}, \pmb{K}_n)$ is…

For each positive integer $k$, consider random $k$-SAT on $n$ variables, and let its satisfiability threshold be the transition point between satisfiable and unsatisfiable instance…

Folklore conjecture. With high probability,

Let $Q_n$ be the $n$-dimensional hypercube, and let $p_c(Q_n,n/2)$ denote the critical probability for majority bootstrap percolation with threshold $n/2$. Sharp asymptotic conject…

Qualitative sharpness conjecture. For each of the ordinary and weak Bruhat orders, the upper bound on the number of comparable pairs is qualitatively close to the actual number of…

Simultaneous multipartite subhypergraph conjecture. There exists a partition of $V$ into $r$ classes $V_1,\dots,V_r$ such that, for every $i=1,\dots,\ell$, at least