Theory of Combinatorial Algorithms
Prof. Emo Welzl

 People Activity Report Previous Reports Research Mittagsseminar Teaching Workshops Social Activities Topics for Master / Bachelor Theses CGAL Geometric Algorithms Library
Mittagsseminar (in cooperation with A. Steger)

 Mittagsseminar Talk Information

Date and Time: Thursday, November 27, 2008, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Reto Spöhel

## Small subgraphs in random graphs and the power of multiple choices: The offline case

Consider the following problem: We are given a graph \$G_{n,m}\$ drawn uniformly at random from all graphs on \$n\$ vertices with \$m\$ edges, and a random partition of its edge set into sets of size \$r\$ called \$r\$-sets. Here \$r\geq 2\$ is a fixed integer, and we assume w.l.o.g. that \$m\$ is divisible by \$r\$. We want to select one edge from each \$r\$-set such that the resulting subgraph of \$G_{n,m}\$ does not contain a copy of some fixed forbidden graph \$F\$. How large can \$m=m(n)\$ be such that this is still possible with probability \$1-o(1)\$?

We prove an explicit threshold function \$m_0(F,r,n)\$ for this problem, valid for any graph \$F\$ and any integer \$r\geq 2\$.

Joint work with Michael Krivelevich and Angelika Steger.

Previous talks by year:   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