Abstract: In this talk, we will examine how large an s-colored k-connected subgraph one can find in every r-coloring of the edges of the complete graph K_n. We derive several sharp bounds for s =1, and asymptotically sharp bounds for s > 1. We also locate several phase transitions for s. We will highlight open problems and their possible, more algebraic, solutions. This is joint work with Robert Morris and Henry Liu.