Ramsey-type numbers involving graphs and hypergraphs with large girth

DOI10.1016/J.ENDM.2015.07.076zbMATH Open1347.05118arXiv1604.05066OpenAlexW2963476552MaRDI QIDQ324890FDOQ324890

Authors: Hiệp Hàn, Troy Retter, Vojtěch Rödl, M. Schacht 

Publication date: 17 October 2016

Abstract: A question of ErdH{o}s asks if for every pair of positive integers $r$ and $k$, there exists a graph $H$ having $extrmgirth(H)=k$ and the property that every $r$-colouring of the edges of $H$ yields a monochromatic cycle $C_k$. The existence of such graphs was confirmed by the third author and Ruci'nski. We consider the related numerical problem of determining the smallest such graph with this property. We show that for integers $r$ and $k$, there exists a graph $H$ on $R^{10k^2}{k}^{15k^3}$ vertices (where $R=R(C_k;r)$ is the $r$-colour Ramsey number for the cycle $C_k$) having $extrmgirth(H)=k$ and the Ramsey property that every $r$-colouring of $E(H)$ yields a monochromatic $C_k$. Two related numerical problems regarding arithmetic progressions in sets and cliques in graphs are also considered.

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

Recommendations

• Ramsey-type numbers involving graphs and hypergraphs with large girth
• On Ramsey families of sets
• Colourings of uniform hypergraphs with large girth and applications
• 2-colorings of hypergraphs with large girth
• Hypergraph Ramsey numbers: triangles versus cliques

zbMATH Keywords

monochromatic arithmetic progression

Mathematics Subject Classification ID

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

Cites Work

• Independent sets in hypergraphs
• Large minimal sets which force arithmetic progressions
• Simple proof of the existence of restricted Ramsey graphs by means of a partite construction
• Restricted Ramsey configurations
• The Ramsey property for graphs with forbidden complete subgraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Threshold Functions for Ramsey Properties
• On Roth's theorem on progressions
• Sparse Ramsey graphs
• On Ramsey families of sets

Cited In (4)

• Ramsey-type numbers involving graphs and hypergraphs with large girth
• There exist graphs with super‐exponential Ramsey multiplicity constant
• On Ramsey families of sets
• Title not available (Why is that?)

This page was built for publication: Ramsey-type numbers involving graphs and hypergraphs with large girth

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