On Multicolor Ramsey Numbers and Subset-Coloring of Hypergraphs

Seminar
Speaker
Chaya Keller (Ariel Univ.)
Date
17/10/2021 - 16:00Add to Calendar 2021-10-17 16:00:00 2021-10-17 16:00:00 On Multicolor Ramsey Numbers and Subset-Coloring of Hypergraphs   The multicolor hypergraph Ramsey number Rk(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 Rk(s,r): If Rk(s,r)>n, then Rk+3(s+1,r+1)>2n. 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 χ(H). In particular, we show that this number is O(log(r−1)(r⋅χ(H))+r), where log(m) denotes m-fold logarithm.  Joint work with Bruno Jartoux, Shakhar Smorodinsky, and Yelena Yuditsky.   zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
zoom
Abstract

 

The multicolor hypergraph Ramsey number Rk(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 Rk(s,r): If Rk(s,r)>n, then Rk+3(s+1,r+1)>2n. 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 χ(H). In particular, we show that this number is O(log(r−1)(r⋅χ(H))+r), where log(m) denotes m-fold logarithm. 

Joint work with Bruno Jartoux, Shakhar Smorodinsky, and Yelena Yuditsky.  

Last Updated Date : 17/10/2021