Department of Mathematics,
University of California San Diego
****************************
Graduate Student Combinatorics Seminar
Nicholas Sieger
UCSD
The Differential Equations Method and Ramsey Lower Bounds
Abstract:
One method of building extremal objects is a random construction subject to constraints. For instance, one can build a tree by randomly adding edges as long as they do not form a cycle. However, analyzing these constructions is rarely so simple and even finding good asymptotic bounds can be difficult. The Differential Equations Method provides a powerful tool for analyzing random constructions subject to constraints by building a tractable system of differential equations out of a combinatorial construction, solving the system, and then proving that the random process is 'close' to the system solution with high probability. We present the differential equations method and give an application in finding lower bounds for graph Ramsey number asymptotics. Following the treatment in Bohman and Keevash (2013), we sketch the proof that R(3,t) $>$ ((1/4) - o(1))t$^2$/log(t).
November 16, 2018
9:00 AM
AP&M B412
****************************