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

Date and Time: Thursday, February 17, 2005, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Reto Spöhel

Online graph avoidance games in random graph

Consider the following one-player game on a random graph: Starting with the empty graph on n vertices, the edges of K_n appear one by one uniformly at random, and the player has to color them immediately ('online') either red or blue. Her goal is to avoid creating a monochromatic copy of a fixed forbidden graph F as long as possible. How many edges can she typically color? For a large class of graphs F, in particular for cliques of arbitrary size, we show that the game length exhibits a threshold behaviour as n tends to infinity.

(This is joint work with Martin Marciniszyn 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