Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Thursday, December 17, 2009, 12:15 pm

**Duration**: This information is not available in the database

**Location**: OAT S15/S16/S17

**Speaker**: Lutz Warnke (University of Oxford)

For a given graph H let X_H denote the random variable that counts the number of copies of H in a random graph G_{n,p}. For subgraph counts Janson's inequality can be used to obtain upper bounds on the probability that X_H is smaller than its expectation. For the corresponding upper tail, however, such bounds are not obtained easily. As it turns out, this probability is simply not as small as the lower tail. In order to better control the upper tail of X_H, Rödl and Rucinski showed that by deleting a small fraction of all edges (or of all H-subgraphs, whatever is smaller) the number of copies of H can be reduced to at most (1+\eps)E[X_H] with probability similar to the lower bound.

In this talk we are interested in a strengthening of the previous result and focus on the case where H is a triangle; the general case is work in progress. Namely, with `very high' probability we want to find a `large' subgraph that on the one hand still contains at least (1-\eps)E[X_{K_3}] many triangles, and on the other hand has the property that every vertex and edge is contained in `not too many` triangles. Our proof is based on an application of the FKG-inequality which will allows use to link the probability of existence of a 'nice' collection of H-subgraphs to the probability that a certain number of H-subgraphs exists at all.

Joint work with Reto Spöhel 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