Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
|
locations | Term schedule | history
|
predoc-courses | schools | block-courses | workshops
partners


Monday Lecture and Colloquium


Monday, November 23, 2015

Freie Universität Berlin
Institut für Informatik
Takustr.
14195 Berlin
room 005



Lecture - 14:15

József Balogh - University of Illinois at Urbana-Champaign


On some problems of Cameron and Erdős in additive combinatorics

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

Tuan Tran - Freie Universität Berlin


Bootstrap percolation in the hypercube

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.




Letzte Aktualisierung: 10.11.2015