New lower bounds on the size-Ramsey number of a path

Deepak Bal; Louis Debiasio

doi:10.37236/9804

New lower bounds on the size-Ramsey number of a path

Deepak Bal, Louis Debiasio

Mathematics

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

5 Scopus citations

Abstract

We prove that for all graphs with at most (3.75 − o(1))n edges there exists a 2-coloring of the edges such that every monochromatic path has order less than n. This was previously known to be true for graphs with at most 2.5n − 7.5 edges. We also improve on the best-known lower bounds in the r-color case.

Original language	English
Article number	P1.18
Journal	Electronic Journal of Combinatorics
Volume	29
Issue number	1
DOIs	https://doi.org/10.37236/9804
State	Published - 2022

Access to Document

10.37236/9804

Cite this

@article{b622ffde37a44f4cb71eb386d28126c8,

title = "New lower bounds on the size-Ramsey number of a path",

abstract = "We prove that for all graphs with at most (3.75 − o(1))n edges there exists a 2-coloring of the edges such that every monochromatic path has order less than n. This was previously known to be true for graphs with at most 2.5n − 7.5 edges. We also improve on the best-known lower bounds in the r-color case.",

author = "Deepak Bal and Louis Debiasio",

note = "Funding Information: ∗Research supported in part by NSF grant DMS-1954170 Publisher Copyright: {\textcopyright} The authors.",

year = "2022",

doi = "10.37236/9804",

language = "English",

volume = "29",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - New lower bounds on the size-Ramsey number of a path

AU - Bal, Deepak

AU - Debiasio, Louis

N1 - Funding Information: ∗Research supported in part by NSF grant DMS-1954170 Publisher Copyright: © The authors.

PY - 2022

Y1 - 2022

N2 - We prove that for all graphs with at most (3.75 − o(1))n edges there exists a 2-coloring of the edges such that every monochromatic path has order less than n. This was previously known to be true for graphs with at most 2.5n − 7.5 edges. We also improve on the best-known lower bounds in the r-color case.

AB - We prove that for all graphs with at most (3.75 − o(1))n edges there exists a 2-coloring of the edges such that every monochromatic path has order less than n. This was previously known to be true for graphs with at most 2.5n − 7.5 edges. We also improve on the best-known lower bounds in the r-color case.

UR - http://www.scopus.com/inward/record.url?scp=85123526980&partnerID=8YFLogxK

U2 - 10.37236/9804

DO - 10.37236/9804

M3 - Article

AN - SCOPUS:85123526980

SN - 1077-8926

VL - 29

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - P1.18

ER -

New lower bounds on the size-Ramsey number of a path

Abstract

Access to Document

Other files and links

Fingerprint

Cite this