Department of

July 2020August 2020September 2020 Su Mo Tu We Th Fr Sa Su MoTuWe Th Fr Sa Su Mo Tu We 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 101112 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 28 29 30 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.

Thursday, August 13, 2020