Department of

July 2020 August 2020September 2020Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su MoTuWe Th Fr Sa 1 2 3 4 1 1 2 3 4 5 5 6 7 8 9 10 11 2 3 4 5 6 7 8 6 7 8 9 10 11 12 12 13 14 15 16 17 18 9 10 11 12 13 14 15 13 14 15 16 17 18 19 19 20 21 22 23 24 25 16 17 18 19 20 21 22 20 21 22 23 24 25 26 26 27 28 29 30 31 23 24 25 26 27 28 29 27 282930 30 31

Tuesday, August 11, 2020

**Abstract:** A $(p,q)$-coloring of a graph $G$ is an edge-coloring of $G$ in which each $p$-clique contains edges of at least $q$ distinct colors. We are interested in the function $f(n,p,q)$, first introduced by Erdos and Shelah, which is the minimum number of colors needed for a $(p,q)$-coloring of the complete graph $K_n$. The best-known general upper bound on $f(n,p,q)$ was given by Erdos and Gyarfas in 1997 using a probabilistic argument. Since then, improved bounds in the case where $p=q$ have been obtained only for $p = 4$ and $p = 5$. In this talk, I will introduce a general strategy for finding new constructive upper bounds and explain how to apply this technique to obtain improved bounds for $p=6$ and $p=8$.

This is joint work with Alex Cameron.

Please email Sean English at SEnglish (at) illinois (dot) edu for Zoom details.