• CARMA-GTA DISCRETE MATHEMATICS INSTRUCTIONAL SEMINAR
  • Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
  • Title: Dependent Random Choice II
  • Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Thu, 17th Nov 2011
  • Abstract:

    We look at (parts of) the survey paper Dependent Random Choice by Jacob Fox and Benny Sudakov: http://arxiv.org/abs/0909.3271. The abstract of the paper says "We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this survey we discuss some of them." My plan for the seminar is to start with a quick recap of the classics of extremal (hyper)graph theory (i.e. Turan, Ramsey, Ramsey-Turan), then look at some simple examples for the probabilistic method in action, and finally come to the striking applications mentioned in the quoted abstract. Only elementary probability is required.


  • [Permanent link]