CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  Eventssee all events
Events        
next up previous
Next: Jason Brown - The Up: Extremal Combinatorics / Combinatoire Previous: Richard Anstee, Ron Ferguson

Aart Blokhuis, Ralph Faudree$^\ast$, András Gyárfás and Miklós Ruszinkó - Anti-Ramsey colorings in several rounds



TEX2HTML_WRAP_INLINE$^$, András Gyárfás and Miklós Ruszinkó, Department of Mathematics and Computer Science, Technical University of Eindhoven; Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee  38152, USA; Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary and Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, Hungary
Anti-Ramsey colorings in several rounds


For positive integers $k\le n$ and t let $\chi^t(k,n)$ denote the minimum number of colors such that at least in one of the tcolorings of edges of Kn all $k\choose 2$ edges of every $K_k\subseteq K_n$get different colors. Generalizing a result of Körner and Simonyi, it is shown in this paper that $\chi^t(3,n)=\Theta (n^{1/t})$. Also two-round colorings in cases k>3 are investigated. Tight bounds for $\chi ^2(k,n)$ for all values of k except for k=5 are obtained. Conversely, let t(k,n) denote the minimum number of colorings such that--having the same $k\choose 2$ colors in each coloring--at least in one of the total t colorings of Kn all $k\choose 2$ edges of every $K_k\subseteq K_n$ get different colors. It is also shown, that for k=n/2t(k,n) is exponentially large. Several related questions are investigated.


next up previous
Next: Jason Brown - The Up: Extremal Combinatorics / Combinatoire Previous: Richard Anstee, Ron Ferguson
 

© Canadian Mathematical Society, 2017 : https://cms.math.ca/