pith. machine review for the scientific record. sign in

arxiv: 1009.3721 · v1 · submitted 2010-09-20 · 🧮 math.CO

Recognition: unknown

Long cycles in subgraphs of (pseudo)random directed graphs

Authors on Pith no claims yet
classification 🧮 math.CO
keywords directedgammarandomcyclecyclesedgesgraphsleast
0
0 comments X
read the original abstract

We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every $0 < \gamma < 1/2$ we find a constant $c=c(\gamma)$ 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+\gamma)|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+\gamma-o(1))|E|$ edges that does not contain a cycle of length at least $cn$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.