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.
@article{10_37236_9804,
author = {Deepak Bal and Louis DeBiasio},
title = {New lower bounds on the {size-Ramsey} number of a path},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {1},
doi = {10.37236/9804},
zbl = {1481.05106},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9804/}
}
TY - JOUR
AU - Deepak Bal
AU - Louis DeBiasio
TI - New lower bounds on the size-Ramsey number of a path
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9804/
DO - 10.37236/9804
ID - 10_37236_9804
ER -
%0 Journal Article
%A Deepak Bal
%A Louis DeBiasio
%T New lower bounds on the size-Ramsey number of a path
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9804/
%R 10.37236/9804
%F 10_37236_9804
Deepak Bal; Louis DeBiasio. New lower bounds on the size-Ramsey number of a path. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/9804
