Combinatorics Seminar

When: Sunday, May 15, 10am Where: Schreiber 309 Speaker: Ido Ben-Eliezer, Tel Aviv U. Title: Local Rainbow Colorings (PhD defense talk)

Abstract:

Given a graph $H$, we denote by $C(n,H)$ the minimum number $k$ such that following holds. There are $n$ colorings of $E(K_n)$ with $k$-colors, each associated with one of the vertices of $K_n$, such that for every copy $T$ of $H$ in $K_n$, at least one of the colorings that are associated with $V(T)$ assigns distinct colors to all the edges of $E(T)$. We characterize the set of all graphs $H$ for which $C(n,H)$ is bounded by some absolute constant $c(H)$, prove a general upper bound and obtain lower and upper bounds for several graphs of special interest. A special case of our results partially answers an extremal question of Karchmer and Wigderson motivated by the investigation of the computational power of span programs.

This is the public presentation of (part of) the PhD thesis of the speaker conducted under the supervision of Prof. Noga Alon and Prof. Michael Krivelevich. The results described are based on joint work with Noga Alon.