On the size Ramsey number of all cycles versus a path

Deepak Bal; Ely Schudrich

doi:10.1016/j.disc.2021.112322

On the size Ramsey number of all cycles versus a path

Deepak Bal
, Ely Schudrich

Mathematics

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We say G→(C,P_n) if G−E(F) contains an n-vertex path P_n for any spanning forest F⊂G. The size Ramsey number Rˆ(C,P_n) is the smallest integer m such that there exists a graph G with m edges for which G→(C,P_n). Dudek, Khoeini and Prałat proved that for sufficiently large n, 2.0036n≤Rˆ(C,P_n)≤31n. In this note, we improve both the lower and upper bounds to 2.066n≤Rˆ(C,P_n)≤5.25n+O(1). Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Prałat. We also have a computer assisted proof of the upper bound [Figure presented].

Original language	English
Article number	112322
Journal	Discrete Mathematics
Volume	344
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2021.112322
State	Published - May 2021

Keywords

Ramsey Theory
Size Ramsey
Sparse Graphs

Access to Document

10.1016/j.disc.2021.112322

Cite this

@article{95334363e5b5400b9ec3586ce277b9cd,

title = "On the size Ramsey number of all cycles versus a path",

abstract = "We say G→(C,Pn) if G−E(F) contains an n-vertex path Pn for any spanning forest F⊂G. The size Ramsey number Rˆ(C,Pn) is the smallest integer m such that there exists a graph G with m edges for which G→(C,Pn). Dudek, Khoeini and Pra{\l}at proved that for sufficiently large n, 2.0036n≤Rˆ(C,Pn)≤31n. In this note, we improve both the lower and upper bounds to 2.066n≤Rˆ(C,Pn)≤5.25n+O(1). Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Pra{\l}at. We also have a computer assisted proof of the upper bound [Figure presented].",

keywords = "Ramsey Theory, Size Ramsey, Sparse Graphs",

author = "Deepak Bal and Ely Schudrich",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = may,

doi = "10.1016/j.disc.2021.112322",

language = "English",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - On the size Ramsey number of all cycles versus a path

AU - Bal, Deepak

AU - Schudrich, Ely

PY - 2021/5

Y1 - 2021/5

N2 - We say G→(C,Pn) if G−E(F) contains an n-vertex path Pn for any spanning forest F⊂G. The size Ramsey number Rˆ(C,Pn) is the smallest integer m such that there exists a graph G with m edges for which G→(C,Pn). Dudek, Khoeini and Prałat proved that for sufficiently large n, 2.0036n≤Rˆ(C,Pn)≤31n. In this note, we improve both the lower and upper bounds to 2.066n≤Rˆ(C,Pn)≤5.25n+O(1). Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Prałat. We also have a computer assisted proof of the upper bound [Figure presented].

AB - We say G→(C,Pn) if G−E(F) contains an n-vertex path Pn for any spanning forest F⊂G. The size Ramsey number Rˆ(C,Pn) is the smallest integer m such that there exists a graph G with m edges for which G→(C,Pn). Dudek, Khoeini and Prałat proved that for sufficiently large n, 2.0036n≤Rˆ(C,Pn)≤31n. In this note, we improve both the lower and upper bounds to 2.066n≤Rˆ(C,Pn)≤5.25n+O(1). Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Prałat. We also have a computer assisted proof of the upper bound [Figure presented].

KW - Ramsey Theory

KW - Size Ramsey

KW - Sparse Graphs

UR - https://www.scopus.com/pages/publications/85100607156

U2 - 10.1016/j.disc.2021.112322

DO - 10.1016/j.disc.2021.112322

M3 - Article

AN - SCOPUS:85100607156

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

M1 - 112322

ER -

On the size Ramsey number of all cycles versus a path

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this