Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Tuesday, May 07, 2024, 12:15 pm

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Kalina Petrova

A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 2006, asks whether for every pair of integers s, t ≥ 1 there exists a finite number F(s, t) such that the vertex set of every digraph of minimum out-degree at least F(s, t) can be partitioned into non-empty parts A and B such that the subdigraphs induced on A and B have minimum out-degree at least s and t, respectively. We prove that if F(2, 2) exists, then all the numbers F(s, t) with s, t ≥ 1 exist and satisfy F(s, t) = Θ(s + t). In consequence, the problem of Alon and Stiebitz reduces to the case s = t = 2. Moreover, the numbers F(s, t) with s, t ≥ 2 either all exist and grow linearly, or all of them do not exist. This is joint work with Micha Christoph and Raphael Steiner.

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