Mathematical Colloquium Restricted subgraphs of edge-colored graphs and applications

An edge-colored graph is a graph with a coloring of its edges such that no vertex is incident to two or more edges of the same color. A subgraph is called a rainbow if all its edges have different colors. The problem of finding rainbow subgraphs or other restricted structures in edge-colored graphs has a long history, dating back to Euler's work on Latin squares. It has also proven to be a powerful method for studying several well-known questions.

In this lecture, we will provide a brief introduction to this topic, discuss several questions in this area, and demonstrate their applications to problems in graph decomposition, additive combinatorics, theoretical computer science, and coding theory.