Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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

Duration: This information is not available in the database

Location: OAT S15/S16/S17

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login