| Monday, November 28th, 2016 | 4pm-5pm | Burnside 1205 |
A conjecture of Bollobas and Erdos from 1976 states that any coloring of edges of an n-vertex complete graph such that at each vertex no color appears more than (n/2)-times contains a properly-colored Hamilton cycle. This problem was a motivation for the following more general question: Let c be a coloring of E(K_n) where at each vertex, no color appear more than k-times. What properly colored subgraphs does c necessarily contain? In this talk, I will be interested in spanning subgraphs of K_n that has bounded maximum degree or the total number of cherries, i.e., the paths on three vertices. I will also mention similar questions for hypergraphs, as well as analogous problems concerned with rainbow subgraphs in edge colorings of K_n, where the total number of appearances for each color is bounded. One of our main results is a confirms the following conjecture of Shearer from 1979: If G is an n-vertex graph with O(n) cherries and c a coloring of E(K_n) such that at each vertex every color appears only constantly many times, then c contains a properly colored copy of G. The talk is based on a joint work with Nina Kamčev and Benny Sudakov.