On the resilience of long cycles in random graphs (Q1010740): Difference between revisions

Summary: 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.