When: Sunday, May 2, 10am
Where: Schreiber 309
Speaker: Chaya Keller, Ariel University
Title: On
Multicolor Ramsey Numbers and Subset-Coloring of Hypergraphs
The multicolor hypergraph Ramsey number $R_k(s,r)$ is the
minimal $n$, such that in any $k$-coloring of all
$r$-element
subsets of $[n]$, there is a subset of size $s$, all whose
$r$-subsets are monochromatic. We present a new "stepping-up
lemma" for $R_k(s,r)$: If $R_k(s,r)>n$, then
$R_{k+3}(s+1,r+1)>2^n$. Using the lemma, we improve some
known
lower bounds on multicolor hypergraph Ramsey numbers.
Furthermore, given a hypergraph $H=(V,E)$, we consider the
Ramsey-like problem of coloring all $r$-subsets of $V$ such
that
no hyperedge of size $>r$ is monochromatic. We provide upper
and lower bounds on the number of colors necessary in terms
of the chromatic number $\chi(H)$. In particular, we show
that
this number is $O(\log^{(r-1)} (r\cdot \chi(H)) + r)$, where
$\log^{(m)}$ denotes $m$-fold logarithm.
Joint work with Bruno Jartoux, Shakhar Smorodinsky, and
Yelena Yuditsky.