***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Maria-Romina Ivan, U. Cambridge

Thursday 15th February, 3:00 in Fine Hall 224.

Tital: A Ramsey characterisation of eventually periodic words

A factorisation x = u_1 u_2 ... of an infinite word x on alphabet X is called 
`super-monochromatic', for a given colouring of the finite words X* on 
alphabet X, if each word u_{k_1} u_{k_2} ... u_{k_n}, where k_1 < ... < k_n, 
is the same colour. A direct application of Hindman's theorem shows that if x 
is eventually periodic, then for every finite colouring of X*, there exists a
suffix of x that admits a super-monochromatic factorisation. What about the
converse?

In this talk we show that the converse does indeed hold: thus a word x is 
eventually periodic if and only if for every finite colouring of X* there is a 
suffix of x having a super-monochromatic factorisation. This has been a 
conjecture in the community for some time. Our main tool is a Ramsey result 
about alternating sums. This provides a strong link between Ramsey theory and 
the combinatorics of infinite words.

Joint work with Imre Leader and Luca Q. Zamboni

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)