9 problems

Let $G(n,p)$ be the binomial random graph, and let the local resilience of a graph $G$ with respect to Hamiltonicity be the largest integer $r$ such that, for every subgraph…

Ben-Shimon–Krivelevich–Sudakov conjecture. The constant $5/6$ in this minimum-degree condition might be improved to $1/2$. This conjecture was later confirmed, so the corresponding…

Long-cycle extension conjecture. For a suitable choice of $c_3$ and $C_3$, the same conclusion holds for all $L\in[c_3^{-1},n]$.

Shifted Chvátal-resilience conjecture. For every $\varepsilon>0$, there exists $C>0$ such that, for $p\geq C\log n/n$, a.a.s. the random graph $G_{n,p}$ is…

Let $G_{n,p}$ be the binomial random graph, and let the global and local resilience of the chromatic number measure, respectively, the minimum number of edge changes globally or th…

Let $G_{n,d}$ be the uniform random $d$-regular graph on $n$ labeled vertices, with $dn$ even. Its local resilience with respect to Hamiltonicity is the largest integer $r$ such th…

Let $K_n$ be the complete graph. For positive integers $r$ and $\Delta$, and a constant $\beta>0$, let $\mathcal{H}_r^{\beta n}(n,\Delta)$ denote the class of graphs relevant to th…

Let $\mathcal{G}(n,p)$ be the binomial random graph on $n$ vertices, let $\mathcal{HAM}$ denote the property of being Hamiltonian, and let $r_\ell(G,\mathcal{HAM})$ denote the loca…

Let ${\mathcal P}$ be a natural graph property, and consider the random graph model $G(n,p)$ with $p$ sufficiently large. A graph property has unbounded local resilience if the amo…