A near-linear Chvátal--Erdős condition for Hamilton cycles in digraphs

Abstract

For a digraph $D$, let ${\alpha }_2(D)$ be the largest size of a vertex set containing no directed $2$-cycle. Let $f_2(a)$ be the least positive integer $k$ such that every $k$-strongly connected digraph $D$ with ${\alpha }_2(D)\le a$ has a Hamilton cycle. Jackson and Ordaz conjectured that $f_2(a)\le a+1$. Towards this conjecture, we establish the near-linear bound $f_2(a)=O\left(\frac{a(\log a{)}^4}{(\log \log a{)}^2}\right),$ and hence $f_2(a)=O_{\epsilon }(a^{1+\epsilon })$ for every fixed $\epsilon >0$. We also disprove the pancyclicity conjecture of Jackson and Ordaz that every digraph $D$ with $\kappa (D)\ge {\alpha }_2(D)+1$ contains a directed cycle of every length from $2$ to $|V(D)|$.