\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Domingos Dellamonica Jr, Yoshiharu Kohayakawa,  Martin Marciniszyn and Angelika Steger }
%
%
\medskip
\noindent
%
%
{\bf On the Resilience of Long Cycles in Random Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
In this paper we determine the local and global resilience of random
graphs $G_{n, p}$ ($p \gg n^{-1}$) with respect to the property of
containing a cycle of length at least $(1-\alpha)n$. Roughly speaking,
given $\alpha > 0$, we determine the smallest $r_g(G, \alpha)$ with
the property that almost surely every subgraph of $G = G_{n, p}$
having more than $r_g(G, \alpha) |E(G)|$ edges contains a cycle of
length at least $(1 - \alpha) n$ (global resilience). We also obtain,
for $\alpha < 1/2$, the smallest $r_l(G, \alpha)$ such that any $H
\subseteq G$ having $\deg_H(v)$ larger than $r_l(G, \alpha) \deg_G(v)$
for all $v \in V(G)$ contains a cycle of length at least $(1 - \alpha)
n$ (local resilience). The results above are in fact proved in the
more general setting of pseudorandom graphs.

\bye

.