Robert Samal from Charles University has successfully started his secondment at Simon Fraser University (Canada). He is going to hold a lecture on the binary paint shop problem. Details are below:
Date: Tuesday October 22, 2019
Time: 13:30 - 14:20
Place: SFU Burnaby, room K9509
Speaker: Robert Samal
Affiliation: Charles University
Title: The binary paint shop problem (aka necklace splitting problem)
Abstract: A double occurrence word w is a word (sequence of letters) in which each of its letters occurs exactly twice. Legal 2-coloring of w is a colouring of individual letters such that each letter occurs once red and once blue. Our goal is to find for a double occurrence word w a legal 2-coloring with minimal number of colour changes – neighbouring letters of different colour.
This question was motivated by an industrial application, however we approach it like a pure combinatorial question -- proving a lower bound (that disproved a conjecture), improving known upper bounds, proving tight concentration, etc.
(Joint work with J. Hancl, A. Kabela, M. Opler, J. Sosnovec, P. Valtr)
Posted on 2019-10-21