Monday, November 23, 2015
Freie Universität Berlin
Institut für Informatik
Takustr.
14195 Berlin
room 005
Lecture - 14:15
Abstract:
In 1990 and 1999, Cameron and Erdős proposed several problems in additive combinatorics. They asked about the number of sum-free sets, the number of maximal sum-free sets, and the number of Sidon sets in [n], as well as the number of subsets of [n] without k-term arithmetic progression. In the talk we survey the recent progress on these questions.
One of the main tools, recently developed by Balogh-Morris-Samotij and Saxton-Thomason, is the container method, which will be discussed separately.
Joint work with Hong Liu, Maryam Sharifzadeh, and Andrew Treglown.
Colloquium - 16:00
Abstract:
The r-neighbor bootstrap process on a graph G starts with an initial set A of "infected" vertices and, at each step of the process, a healthy vertex becomes infected if it has at least r infected neighbors (once a vertex becomes infected, it remains infected forever). If every vertex of G eventually becomes infected, then we say that A percolates.
The main extremal problem in bootstrap percolation is to determine the minimum size of a set which percolates under the r-neighbor bootstrap process on G. When G is the d-dimensional hypercube, Balogh and Bollobás (2001) gave a conjectural asymptotic formula for this number as d tends to infinity. The conjecture has recently been confirmed by Morrison and Noel (2015). Their proof uses linear algebra methods. In this talk I will sketch the proof.