18 problems

Kohayakawa–Kreuter Conjecture for Families. For tuples $(\mathcal{H}_1,\ldots,\mathcal{H}_r)$ that avoid the pathological cases, a threshold for…

Pebbling-threshold spectrum conjecture. There is a graph sequence $\mathcal G$ such that

Let $f$ be a threshold Boolean function depending on $n$ variables, and let its specification number be the minimum number of Boolean points that uniquely determine $f$ within the…

For fixed $l$, let $\mathcal P_l^n$ denote the sequence of $n$-fold Cartesian powers of the path $P_l$. Let $\tau$ denote the pebbling threshold and $N$ the number of vertices in t…

Let ${\cal G}=\{G_1,\ldots,G_n,\ldots\}$ and ${\cal H}=\{H_1,\ldots,H_n,\ldots\}$ be graph sequences, and let $f(G_n)$ denote the pebbling number of $G_n$. Assume that…

Let ${\cal G}=\{G_1,\ldots,G_n,\ldots\}$ be a graph sequence, and let $th({\cal G})$ denote its threshold when one exists. Threshold existence conjecture. Every graph sequence…

Let $t_1$ and $t_2$ be functions such that $t_1\in\Omega(n^{1/2})$, $t_2\in O(n)$, and $t_1\ll t_2$. Threshold-range conjecture. There is a graph sequence…

Lozin's fourth-operation conjecture. The image of any $f_{n,k}$ under this operation again has minimum specification number, that is, belongs to $df_{n+2}$.

Lozin's fourth-operation conjecture. Applying this operation to any $f_{n,k}$ produces a member of $df_{n+2}$.

Nested-function characterization. The nested functions should be the only functions $f e?$ in $dan$ satisfying

Let $G$ be a random graph, and consider $k$-colourings of its edges satisfying the Gallai property, namely, containing no rainbow triangle. Let the threshold function for the prope…

Bollobás–Thomason threshold conjecture. The property $\mathcal{P}$ has a threshold in $\mathbb{G}(n,p\,; \,\binom{[n]}{k})$.

A threshold function is a map $f:\Sigma^N\to\Sigma$, where $\Sigma$ is the binary state space. A function is strongly neutralizable when it has the property that its associated Isi…

Let $f535^n$ denote the Boolean cube, let $f539_n$ be the class of threshold Boolean functions on $n$ variables, and let $f539_{f539_n}(f)$ denote the specification number of $f$ w…

Let $H$ be a graph with a color-critical edge $e$, meaning that $\chi(H-e)<\chi(H)$. For a graph $G$, let $t_H(G)$ and $b_H(G)$ be the maximum values of $|K|$ over, respectively,…

Let $\mathcal{G}(n,p)$ be the Erdős–Rényi random graph, and let $\text{Comb}_{n}$ be the tree formed from an $\sqrt{n}$-vertex path together with disjoint $\sqrt{n}$-vertex paths b…

Let $H$ be a fixed graph. In the Avoider-Enforcer game on the edge set of $K_n$, let ${\mathcal K}_H$ be the family of all copies of $H$, and let $f^-_{{\mathcal K}_H}$ and…

Let $t(m,n)$ denote the number of threshold functions on an $m\times n$ rectangular grid, with $m\le n$. The established asymptotic formula is … For the one-dimensional case, write…