## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, January 09, 2007, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Martin Marciniszyn

## Resilience of Random Graphs

We study extremal problems for random graphs. Suppose an adversary removes some fraction of the edges of a random graph $G_{n, p}$ with $p \gg 1/n$. What is the typical circumference of the remaining graph $G'$? We show that asymptotically almost surely there exists a cycle of length at least $(1 - \alpha)n$ in $G'$ if the adversary removes no more than roughly an $\alpha$-fraction of all edges. Moreover, if the adversary promises to leave at least approximately half of all edges at each vertex, $G'$ contains a cycle of length $(1 - o(1))n$ with probability tending to 1 as $n$ tends to infinity.

Joint work with Domingos Dellamonica Jr., Yoshiharu Kohayakawa, and Angelika Steger.

Information for students and suggested topics for student talks