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

Monday Lecture and Colloquium

Monday, October 23, 2017

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Timothy Roughgarden- Stanford University

How Computer Science Informs Modern Auction Design

Economists have studied the theory and practice of auctions for decades. How can computer science contribute? Using the recent U.S. FCC double-auction for wireless spectrum as a case study, I'll illustrate the many answers: novel auction formats, algorithms for NP-hard problems, approximation guarantees for simple auctions, and communication complexity-based impossibility results.

Colloquium - 16:00

Andrew Treglown - University of Birmingham

On sum-free and solution-free sets of integers

A sum-free set is simply a set of integers which does not contain any solution to x+y=z. In this talk we discuss a range of recent developments concerning sum-free sets. We give a sharp count on the number of maximal sum-free subsets in [n], thereby answering a question of Cameron and Erdős. We also consider similar questions in the setting of solution-free sets (that is now we forbid solutions to some other fixed equation). Related complexity results will also be discussed.

The talk includes joint work with Jozsi Balogh, Hong Liu and Maryam Sharifzadeh; Robert Hancock; and Kitty Meeks.

Letzte Aktualisierung: 17.10.2017