TITLE: Anti-Ramsey and Canonical Ramsey type problems
SPEAKER: Tao Jiang, Miami University, Oxford, OH
WHEN: 4-5pm, October 20
WHERE: PPB 300
We discuss a collection of problems that deal with color patterns in edge-colorings of the complete graph under various constraints. A subgraph $H$ in an edge-colored host graph $G$ is monochromatic if all edges of $H$ have the same color, rainbow if all the edges of $H$ have different colors, and properly colored if no two incident edges have the same color.
Here are some examples of the problems to be discussed.
(1) Given a graph $H$ and a positive integer $n$, what is the maximum number $R^*(n,H)$ of colors in an edge-coloring of $K_n$ that does not contain a rainbow copy of $H$? This maximum number is called the anti-Ramsey number of $H$. Anti-Ramsey numbers are closely related to the Turan numbers.
(2) Given two graphs $G$ and $H$, what is the smallest $n$ such that in every edge-coloring of $K_n$ (using any number of colors) there must exist either a monochromatic copy of $G$ or a rainbow copy of $H$? This problem is motivated by the Erdos-Rado Canonical Ramsey Theorem and has been studied by various researchers in different contexts.
(3) Given a graph $H$ and a positive integer $n$, what is the maximum $k$ such that in every edge-coloring of $K_n$ in which each color appears at most $k$ times at each vertex there must exist a properly colored copy of $H$? a rainbow copy of $H$?
We will give a brief history of these problems, their connection to each other, and mention some results and open problems.
