Ramsey numbers of trees versus odd cycles

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Trees (05C05) Paths and cycles (05C38) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: Burr, ErdH{o}s, Faudree, Rousseau and Schelp initiated the study of Ramsey numbers of trees versus odd cycles, proving that

R (T_{n}, C_{m}) = 2 n - 1

for all odd

m g e 3

and

n g e 756 m^{10}

, where

T_{n}

is a tree with

n

vertices and

C_{m}

is an odd cycle of length

m

. They proposed to study the minimum positive integer

n_{0} (m)

such that this result holds for all

n g e n_{0} (m)

, as a function of

m

. In this paper, we show that

n_{0} (m)

is at most linear. In particular, we prove that

R (T_{n}, C_{m}) = 2 n - 1

for all odd

m g e 3

and

n g e 50 m

. Combining this with a result of Faudree, Lawrence, Parsons and Schelp yields

n_{0} (m)

is bounded between two linear functions, thus identifying

n_{0} (m)

up to a constant factor.

Review text

Summary: \textit{S. A. Burr} et al. [Trans. Am. Math. Soc. 269, 501--512 (1982; Zbl 0543.05047)] initiated the study of Ramsey numbers of trees versus odd cycles, proving that \(R(T_n, C_m) = 2n - 1\) for all odd \(m \geqslant 3\) and \(n \geqslant 756m^{10}\), where \(T_n\) is a tree with \(n\) vertices and \(C_m\) is an odd cycle of length \(m\). They proposed to study the minimum positive integer \(n_0(m)\) such that this result holds for all \(n \geqslant n_0(m)\), as a function of \(m\). In this paper, we show that \(n_0(m)\) is at most linear. In particular, we prove that \(R(T_n, C_m) = 2n - 1\) for all odd \(m \geqslant 3\) and \(n \geqslant 25m\). Combining this with a result of \textit{R. J. Faudree} et al. [Discrete Math. 10, 269--277 (1974; Zbl 0293.05120)] yields \(n_0(m)\) is bounded between two linear functions, thus identifying \(n_0(m)\) up to a constant factor.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Ramsey numbers of trees versus odd cycles

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