Speaker: Chris Cox
Title: Algorithmic re-proofs of some Ramsey numbers
Abstract: 
We give new proofs of some Ramsey numbers relating to matchings and trees which additionally provide efficient algorithms to locate these structures. Consider a two-player game between players Builder and Painter. Painter begins the game by picking a coloring of the edges of $K_n$ which is hidden from Builder. In each round, Builder points to an edge and Painter reveals its color. Builder's goal is to locate a particular monochromatic structure in Painter's coloring by revealing the color of as few edges as possible. Here we consider the situation where this ``particular monochromatic structure'' is a large matching or a large tree. We show that in any $t$-coloring of $E(K_n)$, Builder can locate a monochromatic matching of size ${n-t+1\over t+1}$ by revealing the color of at most $O(n\log t)$ edges. We show also that that in any $3$-coloring of $E(K_n)$, Builder can locate a monochromatic tree on $n/2$ vertices by revealing the color of at most $5n$ edges. (Joint work with Joe Briggs)