SFU Discrete Math Seminar: Robert Samal

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.