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

Date and Time: Thursday, October 07, 2010, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Thomas Rast

Probabilistic one-player vertex-coloring games via deterministic two-player games - the probabilistic game

Consider the following one-player game: The vertices of an initially hidden instance of G_{n,p} (the binomial random graph on n vertices with edge probability p) are revealed one by one (together with all edges leading to previously revealed vertices) and the player, henceforth called Painter, has to color each vertex immediately and irrevocably with one of r>=2 available colors. Painter's goal is to avoid a monochromatic copy of some fixed graph F throughout the process.

It is known that for any fixed graph F and any fixed integer r this game has a threshold p_0(F,r,n) in the following sense: For any function p(n)=o(p_0) there is a Painter strategy that succeeds with probability 1-o(1) in coloring all vertices of G_{n,p}, and for any function p(n)=\omega(p_0) any strategy will with probability 1-o(1) fail to do so (all asymptotics are with respect to n tending to infinity).

We establish a general correspondence between this probabilistic one-player game and a deterministic two-player game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a value \gamma=\gamma(F,r) such that the threshold of the probabilistic problem is given by p_0(F,r,n)=n^{-\gamma}.

This is the second of two talks on the subject. In the first talk we will focus on the computation of \gamma(F,r), which is an interesting combinatorial parameter in its own right. The focus of the second talk will be on the connection between this parameter and the original probabilistic one-player game.

Joint work with Thomas Rast and Reto Spöhel (MPI Saarbrücken)

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