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

Date and Time: Thursday, March 10, 2016, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Nina Kamcev

Bounded colorings of multipartite graphs

Let c be an edge-coloring of the complete n-vertex graph K_n. The problem of finding properly colored and rainbow Hamilton cycles in c was initiated in 1976 by Bollobás and Erdős and has been extensively studied since then. We study multipartite analogues of such questions. We give (up to a constant factor) optimal sufficient conditions for a coloring c of the complete m-partite graph to contain a properly colored or rainbow copy of a given graph G with maximum degree d. Our bounds exhibit a surprising transition in the rate of growth, showing that the problem is fundamentally different in the regimes d>>m and m>>d. Our main tool is the framework of Lu and Székely for the space of random bijections, which we extend to product spaces.

This is joint work with Benny Sudakov and Jan Volec.

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