[Facets-of-complexity] Monday Lecture & Colloquium - Dec 17, 2018

[Günter Rote <rote@inf.fu-berlin.de>]

You are invited to our Monday Lecture & Colloquium on Dec 17th
at 14:15 h & 16:00 h at FU Berlin.

Lecture: Monday, Dec 17th - 14:15 h
   ===============================================
   Shagnik Das (Freie Universität Berlin):

   Randomly perturbed Ramsey problems
   ===============================================

Abstract:
The combinatorial properties much-loved Erdős-Rényi random graph G(n,p), which has n
vertices and whose edges are present independently with probability p, have been
comprehensively studied in the decades since its introduction.  In recent years, much
research has been devoted to the randomly perturbed graph model, introduced in 2003 by
Bohman, Frieze and Martin.  In this talk we shall present and motivate this new model of
random graphs, and then focus on the Ramsey properties of these randomly perturbed graphs.
 More precisely, given a pair of graphs (F,H), we ask how many random edges must be added
to a dense graph G to ensure that any two-colouring of the edges of the perturbed graph
has either a red copy of F or a blue copy of G.  This question was first studied in 2006
by Krivelevich, Sudakov and Tetali, who answered it in the case of F being a triangle and
H being a clique.  We generalise these results, considering pairs of larger cliques, and,
should the audience be willing (but even otherwise), shall take a quick look at some of
the ideas required in our proofs.

This is joint work with Andrew Treglown (Birmingham).

Coffee & Tea Break

Colloquium: 16:00 h
   ===============================================================
   Marie Brandenburg (Freie Universität Berlin):

   Product-Mix Auctions, Competitive Equilibrium and Lattice Polytopes
   ===============================================================

Abstract:
In 2007, when the credit crisis began, the Bank of England approached the economist Paul
Klemperer with the need of a new auction design that would enable them to give liquidity
to all banks in an economically efficient way. Since then, Klemperer’s Product-Mix Auction
design became more and more relevant, with particular interest in when competitive
equilibrium exists, that is, when a set of (indivisible) goods can be split such that
exactly one bid of each bidder is fulfilled. Originally being a question of economics,
this can be translated into a question of specific lattice polytopes that rely on
underlying graphs. I will present the Product-Mix Auction setting, the translation to
polytopes and first results on when competitive equilibrium exists.

Location:
Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin