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

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)

A deletion method for local subgraph counts

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:   2025  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