Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 04, 2016, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Nina Kamcev
Answering a question of Erdős and Brown, Keränen constructed an infinite anagram-free sequence on four symbols, that is, a sequence which contains no consecutive symbols r1r2...rkrk+1...r2k such that rk+1...r2k is a permutation of the block r1...rk. Motivated by the work of Alon, Grytczuk, Hałuszczak and Riordan, we study a natural generalisation of anagram-free sequences for graph colourings. We touch upon results for paths, trees, minor-free graphs and bounded-degree graphs. Surprisingly, there are bounded-degree graphs (such as random regular graphs) in which anagrams cannot be avoided unless we basically give each vertex a separate color.
Joint work with Tomasz Łuczak and Benny Sudakov.
Automatic MiSe System Software Version 1.4803M | admin login