28 problems

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…

Let $L$ be a random Latin square of order $n$, and let $cmathbb{E}_a(n)$ denote the expected number of subsquares of order $a$ in $L$. For $2\leqslant a\leqslant n/2$, McKay and Wa…

A pseudorandom class of hypergraphs is a hereditary class whose sparse random model contains, with high probability, an induced subhypergraph on at least $(1-o_d(1))n$ vertices bel…

General conjecture. For every integer $d d45a 2$, there is a positive real number $C=C(d)$ such that, as the prime power $q$ tends to infinity, with high probability,

Let $D$ be an even natural number and let $G= obreakfrac{}{}\mathcal{L}(K{\frac{D}{2}+1,\frac{D}{2}+1})$ be the line graph of a complete bipartite graph. Thus $G$ has…

Let $k\geq 3$ be a positive integer and let $0<\delta,\varepsilon<1$ be positive real numbers. There is an $n_0$ such that, for every $n\geq n_0$, if $H$ is an $n$-vertex $k$-graph…

Let $L$ be a Latin square of order $n$, and let $\ell(L)$ denote the length of its longest row cycle. Longest row-cycle conjecture. As $n\to\infty$, asymptotically almost all Latin…

Let $\mathcal{U}$ be the Latin square representing a uniformly random 1-factorisation of $K_{2n}$. Let $\ell(\mathcal{U})$ be the length of its longest row cycle, and let…

Let $S$ be a Steiner quasigroup of order $n$ selected uniformly at random. Let $\ell(S)$ be the length of its longest row cycle, and let $m(S)$ be the size of its largest proper St…

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…

For $k\leq n$, let $\mathcal{LR}_{k,n}$ be the set of $k\times n$ Latin rectangles with symbol set $[n]$. A partial Latin rectangle is $\beta n$-sparse if each row and column conta…

For $k\leq n$, let $\mathcal{LR}_{k,n}$ be the set of $k\times n$ Latin rectangles with symbol set $[n]$, and let $\randLR$ be chosen uniformly from this set. 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 $\mathcal{P}(n)_p$ be the random subfamily of the Boolean lattice $\mathcal{P}(n)$ obtained by including each subset independently with probability $p$, and let a maximum antic…

Limit law conjecture. The following limit behavior holds:

Let $n\geq 3$ be odd, and let $ML(n)$ denote the maximal length of a solvable board of size $n$. The paper establishes the lower bound $ML(n)\geq 3n$ for all $n\geq 11$ and the tri…

Regularity-threshold conjecture. The condition on $k$ in Theorem 1 can be improved to

Let $w$ denote the writhe of a knot represented by an $n\times n$ grid diagram. The distribution is considered for knots encoded by two $n$-permutations recording the order of the…

For $d\geqslant 2$, a $d$-permutation of order $n$ is a $(d+1)$-array over $\{0,1\}$ of order $n$ in which every line contains a unique $1$. A $d$-pattern of order $k$ is a sequenc…

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

Latin-square threshold conjecture. The threshold for $M\sim\mathcal{M}(n,n,n;p)$ to contain a Latin square is $p=\log(n)/n$. The scale is suggested by the obstruction consisting of…

McKay–Wanless conjecture. The displayed concentration holds for every fixed $\varepsilon>0$. This predicts that a uniformly random Latin square has approximately $n^{2}/4$ intercal…

Let $B_n$ denote the set of binary trees with $n$ leaves. For a binary tree $T$, let $l(T)$ be its number of leaves and $k(T)$ its number of symmetries, meaning vertices with ident…