On multicolor Ramsey numbers and subset-coloring of hypergraphs

Abstract: 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 \chi(H)) + r), where log^{(m)} denotes m-fold logarithm.

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

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456