Ramsey-type numbers involving graphs and hypergraphs with large girth

DOI10.1016/J.ENDM.2015.07.076MaRDI QIDQ324890zbMATH OpenOpenAlexFDO

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

Publication date 17 October 2016

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

zbMATH Keywords

monochromatic arithmetic progression

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3477291 (Why is no real title available?)
• scientific article; zbMATH DE number 3537768 (Why is no real title available?)
• Independent sets in hypergraphs
• Large minimal sets which force arithmetic progressions
• On Ramsey families of sets
• On Roth's theorem on progressions
• Restricted Ramsey configurations
• Simple proof of the existence of restricted Ramsey graphs by means of a partite construction
• Sparse Ramsey graphs
• The Ramsey property for graphs with forbidden complete subgraphs
• Threshold Functions for Ramsey Properties

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
• scientific article; zbMATH DE number 6990921 (Why is no real title available?)

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)