Combinatorics Seminar
Alex Cameron
UIC
A variation of the Ramsey problem: (p,q)-colorings
Abstract: For fixed integers $p$ and $q$, let $f(n,p,q)$ denote the minimum number of colors needed to color all of the edges of the complete graph $K_n$ such that no clique of $p$ vertices spans fewer than $q$ distinct colors. Any edge-coloring with this property is known as a $(p,q)$-coloring. In this talk I will present a recent result showing that $f(n,5,5) \leq n^{1/3 + o(1)}$ as $n \rightarrow \infty$ by giving an explicit $(5,5)$-coloring. This improves upon the best known probabilistic upper bound of $O\left(n^{1/2}\right)$ given by Erdos and Gyarfas, and comes close to matching the best known lower bound $\Omega\left(n^{1/3}\right)$.
Monday March 27, 2017 at 2:00 PM in SEO 612