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, September 29, 2016, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Nemanja Skoric
In a classical paper, Erdos, Gyarfas and Pyber prove that there exists a function pc : N -> N such that for any r-coloring of the edge set of the complete graph K_n there is a covering (even partitioning) of the vertex set by at most pc(r) many monochromatic cycles. In particular, this means that if the number of colors is constant only constantly many monochromatic cycles are needed to cover K_n. Since the original paper there have been many improvements on the value of pc(r) and different generalizations of the problem. In this paper we initiate the study of the problem for the case of random graphs. We prove that for any constant eps > 0 and p >= n^{-1/2 + eps} w.h.p. G ̴ Gnp has the following property: for any 2-coloring of G the graph can be covered by constantly many monochromatic cycles. The bound on p can not be much improved as when p is significantly less than (log n / n)^{1/2} the number of monochromatic cycles needed to cover Gnp grows to infinity with n.
Joint work with Daniel Korandi, Frank Mousset, Rajko Nenadov and Benjamin Sudakov.
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