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

2019/09/13 by Bal, Deepak, DeBiasio, Louis · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1909.06354

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.

Cited by

• Three-color online Ramsey numbers r(P₃,P₃,P_ℓ) and r(P₃, P₃, C_ℓ)
• Size-Ramsey numbers of tight paths

Related

• The size Ramsey number of a directed path
• Note on the multicolour size-Ramsey number for paths
• A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs
• Lower Bound on the Size-Ramsey Number of Tight Paths
• The multicolour size Ramsey number of a path