Return to Calendar

Photo of University Hall

University Calendar

Monochromatic Structures in Edge-Colored Random Graphs

February 26, 2018, 3:00 pm - 4:00 pm
Location Science Hall - 102 the Sokol Room
Posted InCollege of Science and Mathematics
Mathematical Sciences Seminar TypeDepartment Colloquium

Suppose the edges of a graph have been colored with red and blue by an adversary. Can you always find a large connected subgraph whose edges are all blue or all red (i.e. a large monochromatic component)? How about a long monochromatic path or cycle? Can you always find a collection of a few monochromatic components (or paths, or cycles) which covers all the vertices of the graph? What if the color palette has size r instead of just 2? In this talk we will discuss such questions, specifically when the underlying graph is a random graph.