Department of

March 2020 April 2020 May 2020 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 1 2 3 4 1 2 8 9 10 11 12 13 14 5 6 7 8 9 10 11 3 4 5 6 7 8 9 15 16 17 18 19 20 21 12 13 14 15 16 17 18 10 11 12 13 14 15 16 22 23 24 25 26 27 28 19 20 21 22 23 24 25 17 18 19 20 21 22 23 29 30 31 26 27 28 29 30 24 25 26 27 28 29 30 31

Tuesday, April 21, 2020

**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.