119 problems

Let $C_n$ be the cycle with $n$ edges, and let $q(C_n)$ denote its consistency probability. Define … The cycle consistency probability conjecture. The consistency probability of…

Does there exist an absolute constant $C>0$ such that, for every positive integer $\ell$ and every $C\ell$-connected graph $G$, there is a partition $V(G)=S\mathbin{\dot\cup}T$ suc…

Let $\mathcal{I}(n,k)$ denote the set of intersecting families $\mathcal{F}\subseteq\binom{[n]}{k}$, and let a family be trivial if all its members contain a common element. Then,…

For every fixed $\varepsilon>0$, determine whether the random graph $G(n,p)$ has, with high probability, a fractional triangle decomposition precisely at the conjectured threshold…

There exists a universal constant $C>0$ such that, for every finite graph $H$, the fractional expectation threshold for containing $H$ satisfies…

For every finite multigraph $G$ of maximum degree at most $\Delta$, and every pair of vertices $x,y$ with graph distance $d_G(x,y)=t$, the number $n_G(x,y)$ of shortest $x$–$y$ pat…

Fix $d\ge 2$. Let $\eta=(\eta(x))_{x\in\mathbb{Z}^d}$ be an i.i.d. initial mass configuration for the divisible sandpile, with mean density $\rho$, and let…

For an integer $r\ge 2$ and a real number $0<\delta<1/r$, let $b_n(r,\delta)$ be the largest integer $b$ such that every graph $G$ on $n$ vertices satisfying…

Let $G_q$ be an alphabet of size $q\ge 2$, let $t\ge 1$ be fixed, and let $C\subseteq G_q^n$. For $X,Y\in G_q^{t\times n}$, define the column Hamming distance by…

For $0\leq\mu_1\leq\cdots\leq\mu_n$ and $\lambda>\sum_{i=1}^n\mu_i$, let $X_1,\ldots,X_n$ range over independent nonnegative random variables satisfying $\mathbb{E}X_i=\mu_i$. Defi…

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

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…

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…

Let $X$ be a finite set, let $k\in\mathbb{N}$ satisfy $k\leq\log_L|X|$, and let $g\colon{\mleft(\kern-.1em\genfrac{}{}{0pt}{}{X}{k}\kern-.1em\mright)}\to[0,1]$. Define…

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…

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…

Folklore conjecture. With high probability,

Optimal Power of Few conjecture. There is a function $f(x)$ such that $f(x)>1/2$ for $x>0$, $f(x)$ tends to $1$ as $x$ tends to infinity, and, in majority dynamics on $G(n,p)$ with…

Let $D70E_n$ be a uniformly random permutation in the symmetric group $D70E_n$, and let $D43E\operatorname{Pop}$ denote one step of Pop-Stack Sorting, which reverses every maximal…

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

Let $RH(r,s,A)$ be a Robin Hood game with resource functions $r,s$ and index set $A$. A random strategy is independent of the index set $A$ if its choices do not depend on $A$. Old…

Independent-set density existence conjecture. For every $c>0$ and $r\geq 3$, the limits

MAX-SAT limiting function conjecture. For every $k$ and every constant $c>0$, as $n\rightarrow\infty$,

Satisfiability threshold conjecture. For each $k$ there exists a threshold density $c_k$, such that for any positive $\varepsilon$, for all $c<c_k-\varepsilon$, $F(n,cn)$ is almost…