SCIENCE@home

Multicolor Ramsey numbers for triple systems

M. Axenovich,A. Gyárfás,Hong Liu,D. Mubayi

Published 2013 in Discrete Mathematics

ABSTRACT

Given an r-uniform hypergraph H, the multicolor Ramsey number r"k(H) is the minimum n such that every k-coloring of the edges of the complete r-uniform hypergraph K"n^r yields a monochromatic copy of H. We investigate r"k(H) when k grows and H is fixed. For nontrivial 3-uniform hypergraphs H, the function r"k(H) ranges from 6k(1+o(1)) to double exponential in k. We observe that r"k(H) is polynomial in k when H is r-partite and at least single-exponential in k otherwise. Erdos, Hajnal and Rado gave bounds for large cliques K"s^r with s>=s"0(r), showing its correct exponential tower growth. We give a proof for cliques of all sizes, s>r, using a slight modification of the celebrated stepping-up lemma of Erdos and Hajnal. For 3-uniform hypergraphs, we give an infinite family with sub-double-exponential upper bound and show connections between graph and hypergraph Ramsey numbers. Specifically, we prove thatr"k(K"3)@?r"4"k(K"4^3-e)@?r"4"k(K"3)+1, where K"4^3-e is obtained from K"4^3 by deleting an edge. We provide some other bounds, including single-exponential bounds for F"5={abe,abd,cde} as well as asymptotic or exact values of r"k(H) when H is the bow {abc,ade}, kite {abc,abd}, tight path {abc,bcd,cde} or the windmill {abc,bde,cef,bce}. We also determine many new ''small'' Ramsey numbers and show their relations to designs. For example, the lower bound for r"6(kite)=8 is demonstrated by decomposing the triples of a seven element set into six partial STS (two of them are Fano planes).

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-35 of 35 references · Page 1 of 1

CITED BY

Showing 1-24 of 24 citing papers · Page 1 of 1