SFU Discrete Math Seminar: Robert Samal

  • Date: 10/22/2019
Robert Samal, Charles University

Simon Fraser University


The binary paint shop problem (aka necklace splitting problem)


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.

Other Information: 

This event is also accessible remotely. For those who cannot attend in person, the seminar will be broadcasted by visiting: https://bluejeans.com/1200009509 (You may be prompted to install the Bluejeans software either for the browser or the application.)