Department of

# Mathematics

Seminar Calendar
for events the day of Tuesday, April 21, 2020.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
      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

1:00 pm in Zoom,Tuesday, April 21, 2020

#### The size-Ramsey number of a path

###### Louis DeBiasio (Miami University)

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.