pith. sign in

arxiv: 1604.05066 · v1 · pith:SOMYCN2Anew · submitted 2016-04-18 · 🧮 math.CO

Ramsey-type numbers involving graphs and hypergraphs with large girth

classification 🧮 math.CO
keywords everygirthgraphgraphspropertycolouringcycleexists
0
0 comments X
read the original abstract

A question of Erd\H{o}s asks if for every pair of positive integers $r$ and $k$, there exists a graph $H$ having $\textrm{girth}(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 $\textrm{girth}(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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.