Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Wednesday, June 28, 2017, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Marlo Eugster (Master's thesis)

Vertex covering by monochromatic cycles

It was proven by Erdős, Gyárfás and Pyber, that the n vertices of a complete graph, whose edges are coloured in t colours, can be covered by f(t) many monochromatic cycles. The focus of my Master Thesis is the case where we are restricted to choose monochromatic cycles of at most s < t different colours.

The main result of my thesis is that we need at most O(n^{1/r}) many cycles, where r = 2s - t + 2, to cover all vertices if t/2 < = s < t. This result is asymptotically optimal. In case s < t/2, there exist colourings such that we need a linear (in n) amount of cycles. This talk will mainly focus on the proofs of these results. I will also shortly talk about the same problem for graphs other than the complete graph.

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