# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**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