|Mittagsseminar Talk Information|
Date and Time: Tuesday, June 19, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Rajko Nenadov
On Counting Lemma for sparse graphs (Master thesis)
Szemeredi's regularity lemma, together with the corresponding embedding and counting lemmas, is an important tool in modern graph theory. However, because of the underlying definition of regularity it is only helpful when one is dealing with dense graphs, that is, graphs of density cn^2 for some constant c. In 1997, Kohayakawa and Rödl introduced a modification of regularity that makes it applicable to the certain class of graphs with density o(n^2), and Kohayakawa, Luczak and Rödl conjectured a corresponding embedding lemma. The embedding conjecture has been proven only recently, and using some stronger assumptions the counting version was derived. We show that the counting lemma for some special cases, namely K4, K5 and K6, can be proven using the same setup as the embedding conjecture without any additional assumptions.
Thesis supervised by Angelika Steger.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
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
Automatic MiSe System Software Version 1.3392 | admin login