Abstract: Given a graph $H$, the size-Ramsey number of $H$ is the minimum $m$ such that there exists a graph $G$ with $m$ edges such that in every $2$-coloring of $G$, there exists a monochromatic copy of $H$. Paul Erdos offered $ \$ $100 simply to determine the correct order of magnitude of the size-Ramsey number of $P_n$, the path on $n$ vertices, and Beck solved this problem by showing that the size-Ramsey number of $P_n$ is between $2.25n$ and $900n$. (Note that a trivial lower bound is $2(n-2)$ and when one first thinks about the problem, it seems surprisingly hard to even improve the lower bound to something like $2.0001n$.) The best lower and upper bounds, after many incremental improvements, stood at $2.5n$ and $74n$, both due to recent work of Dudek and Pralat.
We improve the lower bound to $3.75n$; that is, we prove that every graph with at most $3.75n$ edges has a $2$-coloring such that there are no monochromatic $P_n$'s. We also discuss the $r$-color version of the problem.
Joint work with Deepak Bal.
Please email SEnglish@illinois.edu for the zoom ID and password.