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 Seminarhttp://www.montclair.edu/csam/mathematical-sciences/seminars/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.