|
13h October 2006
|
Peter Allen
Forbidden induced bipartite graphs
Talk Slides (70Kb)
Abstract
Let H be a bipartite graph. Let Forbn(H) be the number of bipartite graphs on n vertices which do not contain H as an induced subgraph. We study the rate of growth of Forbn(H). We are especially interested in bounds of the form ncn.
|
|
20th October 2006
|
Bernhard von Stengel
Correlated equilibria - existence via LP duality
Abstract
The concept of correlated equilibrium, due to Aumann (1974), generalises Nash equilibrium, where each player randomises independently, by allowing for correlated randomisation between the players. The set of correlated equilibria is a polytope described by a small number (relative to the game description) of inequalities. This polytope is nonempty because Nash equilibria, which exist by a fixed point argument, are a special case. We give an elegant existence proof due to Nau/McCardle and, independently, Hart/Schmeidler from 1990 that only uses LP duality. We then mention recent algorithmic implications for succintly specified games by Papadimitriou (STOC 2005).
|
|
27th October 2006
|
Anne Balthasar
The fundamental group
Abstract
I want to explain what the fundamental group of a topological space is and then use this concept to prove a two-dimensional version of Brouwer's fixed point theorem
|
|
3rd November 2006
|
Luis Cereceda
On the complexity of mixing 3-colourings in bipartite graphs
Abstract
For a 3-colourable graph G, let C3(G) be the 3-colour-graph of G. This is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. If C3(G) is connected, we say G is 3-mixing. We are interested in the computational complexity of the following decision problem: given G, is G is 3-mixing?
Given that 3-chromatic graphs are not 3-mixing, we restrict our attention to bipartite graphs. For these, the problem is known to be in the complexity class coNP. Moreover, for bipartite planar graphs, the question is answerable in polynomial time. In this talk, we settle the computational complexity of the decision problem for general bipartite graphs.
|
|
10th November 2006
|
Viresh Patel
Cutting Graphs Simultaneously
Abstract
For G=(V,E) a graph with subsets A,B of V, let eG(A,B) denote the set of edges in G that have one end in A and the other in B. When B=Ac, eG(A,Ac) is called a cut of G. It is easy to show for every graph G=(V,E), with |E|=m, that there exists a subset A of V such that
|eG(A,Ac)| > m/2.
Now suppose we have k graphs, Gi=(V,Ei), i= 1, ..., k, on the same vertex set V, and let mi=|Ei|. We prove that there exists a subset A of V such that for every i = 1, ..., k, we have
eGi(A,Ac) > mi/2 - \sqrt{kmi}/2.
Although the proof is probabilistic, we can use it to give a polynomial time algorithm for constructing a subset A of V satisfying the above.
|
|
17th November 2006
|
Petra Berenbrink (Simon Fraser University)
Distributed Selfish Load Balancing
Abstract
Suppose that a set of m tasks are to be shared as equally as possible amongst a set of n resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a ``selfish agent'', and require each agent to select a resource, with the cost of a resource being the number of agents to select it. Agents would then be expected to migrate from overloaded to underloaded resources, until the allocation becomes balanced.
Recent work has studied the question of how this can take place within a distributed setting in which agents migrate selfishly without any centralized control. Here, we discuss a natural protocol for the agents which combines the following desirable features: It can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties. Using a martingale technique we show a bound on the convergence time of the protocol. We also look at a lower bound for the convergence time, as well as an exponential lower bound for a variant of this protocol that allows the agents to migrate even if they do not strictly improve their situation.
|
|
24th November 2006
|
Marianne Fairthorne
Permutation Capacity of Graphs
Abstract
|
|
1st December 2006
|
Zibo Xu
Value and strategy of zero-sum stochastic games with limit average payoffs
Abstract
Stochastic games model repeated play with symmetric information. We analyze their values and ε-optimal strategies in the zero-sum case, and illustrate the Big Match as an example to reveal their general structure and propositions. To show the qualitative difference of the value in stochastic games between the finite states case and the countably many states case, we give an example extending from the Big Match, whose value calculated in the context of the lim sup average payoff and the lim inf average payoff optimal strategies are no longer the same. Moreover, we can also conclude that not all zero-sum stochastic games with countable state space have uniformly converging ε-optimal strategies.
|
|
8th December 2006
|
Martin Marciniszyn (ETH Zurich)
Online Ramsey Games in Random Graphs
Abstract
Consider the following generalized notion of graph colourings: a vertex colouring of graph G is valid w.r.t. some fixed nonempty graph F if no colour class induces a copy of F in G, i.e., there is no monochromatic copy of F in G. We propose and analyze an algorithm for computing valid colourings of a random graph Gn, p on n vertices with edge probability p in an online fashion. For a large family of graphs F including cliques and cycles of arbitrary size, the proposed algorithm is optimal in the following sense: for any integer r > 1, there is a constant β=β(F,r) such that the algorithm a.a.s. (asymptotically almost surely) computes a valid r-colouring of Gn, p w.r.t. F online if p << n-β, and any online algorithm will a.a.s. fail to do so if p >> n-β. That is, we observe a threshold phenomenon determined by the function n-β.
This is joint work with Angelika Steger and Reto Spöhel.
|