On anti-Ramsey numbers for complete bipartite graphs and the Turan function

Elliot Krop, Michelle York

Published 2011-08-25, updated 2015-11-18Version 2

Given two graphs $G$ and $H$ with $H\subseteq G$ we consider the anti-Ramsey function $AR(G,H)$ which is the maximum number of colors in any edge-coloring of $G$ so that every copy of $H$ receives the same color on at least one pair of edges. The classical Tur\'an function for a graph $G$ and family of graphs $\mathcal{F}$, written $ex(G,\mathcal{F})$, is defined as the maximum number of edges of a subgraph of $G$ not containing any member of $\mathcal{F}$. We show that there exists a constant $c>0$ so that $AR(K_n,K_{s,t})-ex(K_n,K_{s,t})<cn$ and $c$ depends only on $s$ and $t$, which implies $AR(K_n,K_{s,t})\leq cn^{2-\frac{1}{s}}$, for $s\leq t$ by a result of K\H ovari, S\'os, and Tur\'an.