Printable PDF
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

****************************