Long cycles in subgraphs of (pseudo)random directed graphs

We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every $0 < γ< 1/2$ we find a constant $c=c(γ)$ such that the following holds. Let $G=(V,E)$ be a (pseudo)random directed graph on $n$ vertices, and let $G'$ be a subgraph of $G$ with $(1/2+γ)|E|$ edges. Then $G'$ contains a directed cycle of length at least $(c-o(1))n$. Moreover, there is a subgraph $G''$ of $G$ with $(1/2+γ-o(1))|E|$ edges that does not contain a cycle of length at least $cn$.

No reviews yet.

No comments yet.