On the cover Ramsey number of Berge hypergraphs

DOI10.1016/J.DISC.2020.111972zbMATH Open1443.05122arXiv1901.09058OpenAlexW3027053007MaRDI QIDQ776301FDOQ776301

Linyuan Lu, Zhiyu Wang

Publication date: 8 July 2020

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

Abstract: For a fixed set of positive integers $R$, we say $mathcalH$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. An $R$-graph $mathcalH$ is emph{covering} if every vertex pair of $mathcalH$ is contained in some hyperedge. For a graph $G=(V,E)$, a hypergraph $mathcalH$ is called a extit{Berge}-$G$, denoted by $BG$, if there exists an injection $f:E(G)oE(mathcalH)$ such that for every $einE(G)$, $esubseteqf(e)$. In this note, we define a new type of Ramsey number, namely the emph{cover Ramsey number}, denoted as $hat{R}^R(B{G}_1,B{G}_2)$, as the smallest integer $n_0$ such that for every covering $R$-uniform hypergraph $mathcalH$ on $ngeq{n}_0$ vertices and every $2$-edge-coloring (blue and red) of $mathcalH$ , there is either a blue Berge-$G_1$ or a red Berge-$G_2$ subhypergraph. We show that for every $kgeq2$, there exists some $c_k$ such that for any finite graphs $G_1$ and $G_2$, $R(G_1,G_2)leqhat{R}^{[k]}(B{G}_1,B{G}_2)leq{c}_{k}cdotR(G_1,G_2{)}^3$. Moreover, we show that for each positive integer $d$ and $k$, there exists a constant $c=c(d,k)$ such that if $G$ is a graph on $n$ vertices with maximum degree at most $d$, then $hat{R}^{[k]}(BG,BG)leqcn$.

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

Recommendations

• On the cover Turán number of Berge hypergraphs
• Ramsey numbers of Berge-hypergraphs and related structures
• A note on Ramsey numbers for Berge-\(G\) hypergraphs
• Ramsey problems for Berge hypergraphs
• On Berge-Ramsey problems

zbMATH Keywords

hypergraphRamsey numbershadow graphBerge hypergraphcovering Ramsey numberSzemeredi regularity lemma

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic lower bounds for Ramsey functions
• Title not available (Why is that?)
• Hypergraph extensions of the Erdős-Gallai theorem
• The Ramsey number of a graph with bounded maximum degree
• On resolvable designs
• 3-uniform hypergraphs avoiding a given odd cycle
• Hypergraphs with no cycle of a given length
• Extremal Results for Berge Hypergraphs
• An Erdős-Gallai type theorem for uniform hypergraphs
• A note on Ramsey numbers for Berge-\(G\) hypergraphs
• The existence of resolvable BIBD with \(k\) even and \(\lambda=1\)
• General lemmas for Berge-Turán hypergraph problems
• Turán numbers for Berge-hypergraphs and related extremal problems
• On Berge-Ramsey problems
• Ramsey numbers of Berge-hypergraphs and related structures
• On \(r\)-uniform hypergraphs with circumference less than \(r\)
• Avoiding long Berge cycles
• Ramsey Problems for Berge Hypergraphs
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs

Cited In (5)

• Multicolor Ramsey numbers for Berge cycles
• Ramsey numbers of path-matchings, covering designs, and 1-cores
• Random cyclic triangle-free graphs of prime order
• On the cover Turán number of Berge hypergraphs
• A note on the uniformity threshold for Berge hypergraphs

This page was built for publication: On the cover Ramsey number of Berge hypergraphs

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