On multicolor Ramsey numbers and subset coloring of hypergraphs

DOI10.1137/21M1462003zbMATH Open1495.05187arXiv2103.12627OpenAlexW4291011623MaRDI QIDQ5096590FDOQ5096590

Authors: Bruno Jartoux, Chaya Keller, Yelena Yuditsky, Shakhar Smorodinsky 

Publication date: 18 August 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: For $ngeqs>rgeq1$ and $kgeq2$, write $nightarrow(s{)}_k^r$ if every hyperedge colouring with $k$ colours of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by extcite{AGLM14} and extcite{EHMR84} we show that [ ext{if } r geq 3 ext{ and } n

rightarrow (s)_k^r ext{ then } 2^n

rightarrow (s+1)_{k+3}^{r+1}. ] This yields an improvement for some of the known lower bounds on multicolour hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of colouring all $r$-subsets of $V$ such that no hyperedge of size $geqr+1$ is monochromatic. We provide upper and lower bounds on the number of colours necessary in terms of the chromatic number $chi(H)$. In particular we show that this number is $O(lo{g}^{(r-1)}(rchi(H))+r)$.

Full work available at URL: https://arxiv.org/abs/2103.12627

Recommendations

• Lower bounds for hypergraph Ramsey numbers
• Multicolor Ramsey numbers for triple systems
• New lower bounds for Ramsey numbers of graphs and hypergraphs
• Multicolored subsets in colored hypergraphs
• Hypergraph Ramsey numbers

zbMATH Keywords

hypergraph Ramsey numbersmulticolor Ramsey numberssubset coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Cites Work

• On the structure of linear graphs
• Title not available (Why is that?)
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Small Ramsey numbers
• Shift graphs and lower bounds on Ramsey numbers \(r_ k(l;r)\)
• Combinatorial set theory: Partition relations for cardinals
• An improved bound for the stepping-up lemma
• Partition relations for cardinal numbers
• Symmetric sum-free partitions and lower bounds for Schur numbers
• On Neighbourly Triangulations
• A survey of bounds for classical Ramsey numbers
• Heawood inequalities
• On coloring manifolds
• Multicolor Ramsey numbers for triple systems
• Title not available (Why is that?)
• Constructive Methods in Gallai-Ramsey Theory for Hypergraphs
• Lexicographic products of \(r\)-uniform hypergraphs and some applications to hypergraph Ramsey theory

Cited In (7)

• Ramsey properties of algebraic graphs and hypergraphs
• Ramsey-type results for Gallai colorings
• A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs
• Lower bounds for hypergraph Ramsey numbers
• Set-coloring Ramsey numbers via codes
• A note on two multicolor Ramsey numbers
• Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs

This page was built for publication: On multicolor Ramsey numbers and subset coloring of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096590)