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, January 11, 2016

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



Lecture - 14:15

Jochen Koenemann - University of Waterloo

Network Bargaining - Where Bargaining & Matching Theory Meet

Abstract:
Bargaining is a central topic of study in economics and in the social sciences. In the most basic setting, two agents A & B negotiate how to split a dollar. Assume the agents have monetary outside options a & b, respectively, that they receive, should negotiations fail; Nash's famous bargaining solution predicts that in an equilibrium, the agents each receive their outside options, and that the remainder is split evenly; i.e., the agents receive x_A and x_B such that x_A-a=x_B-b.

In this talk we will look at a natural generalization of Nash bargaining to agents interacting in social networks. We will present a natural equilibrium concept extending Nash's condition, and present Kleinberg & Tardos' recent characterization of graphs that admit equilibria. We will present connections between bargaining theory, cooperative games, and matching theory and use these to derive elegant algorithms for the computation of equilibria.




Colloquium - 16:00

Laura Gellert - Universität Ulm

Edge colouring and treewidth

Abstract:
We discuss a connection between the chromatic index χ'(G) and the treewidth of a simple graph G. The treewidth of a graph measures the graph's similarity to a tree and χ'(G) gives the number of distinct colours needed to properly colour the edges of G. The chromatic index equals either the maximal degree Δ(G) or Δ(G) + 1, but its determination is non-trivial. We conjecture that any graph G with treewidth k and Δ(G) ≥ k + √k satisfies χ'(G) = Δ(G). To support our conjecture we prove its fractional version. We show the proposed bound is tight and that χ'(G ) = Δ(G) if Δ(G) ≥ 2k-1.
This is joint work with Henning Bruhn and Richard Lang.



Letzte Aktualisierung: 05.01.2016