Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

Tue, 14/10/2008
16:00 		Simon Griffiths (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Subgraphs of Oriented Graphs
How can one guarantee the presence of an oriented four-cycle in an oriented graph G? We shall see, that one way in which this can be done, is to demand that G contains no large `biased. subgraphs; where a `biased. subgraph simply means a subgraph whose orientation exhibits a strong bias in one direction. Furthermore, we discuss the concept of biased subgraphs from another standpoint, asking: how can an oriented graph best avoid containing large biased subgraphs? Do random oriented graphs give the best examples? The talk is partially based on joint work with Omid Amini and Florian Huc.
Tue, 21/10/2008
14:30 		Roy Meshulam (Technion) Combinatorial Theory Seminar Add to calendar L3
Domination numbers, homology and hypergraph matching
The homological Hall lemma is a topological tool that has recently been used to derive Hall type theorems for systems of disjoint representatives in hypergraphs. After outlining the general method, we.ll describe one such theorem in some detail. The main ingredients in the proof are: 1) A relation between the spectral gap of a graph and the topological connectivity of its flag complex. 2) A new graph domination parameter defined via certain vector representations of the graph. Joint work with R. Aharoni and E. Berger
Tue, 28/10/2008
14:30 		Andy Twigg (Oxford) Combinatorial Theory Seminar Add to calendar L3
Distance labeling on graphs
Given a graph G, we are asked to preprocess G and compute labels L(u) for vertices such that given L(x) and L(y) we can efficiently answer d_G(x,y). I will describe some results in this area and some open problems.
Tue, 11/11/2008
14:30 		Colin McDiarmid (Oxford) Combinatorial Theory Seminar Add to calendar L3
Random graphs from a minor-closed class
Tue, 25/11/2008
14:30 		Artur Czumaj (Warwick) Combinatorial Theory Seminar Add to calendar L3
Testing expansion in bounded degree graphs really fast
In the first part of the talk we will introduce the notion of property testing and briefly discuss some results in testing graph properties in the framework of property testing. Then, we will discuss a recent result about testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion:  
an $ a $-expander is a graph $ G = (V,E) $ in which every subset $ U $ of $ V $ of at most $ |V|/2 $ vertices has a neighborhood of size at least $ a|U| $. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately $ O(n^{1/2}) $. We design a property testing algorithm that accepts every $ a $-expander with probability at least 2/3 and rejects every graph that is $ \epsilon $-far from an $ a^* $-expander with probability at least 2/3, where $ a^* = O(a^2/(d^2 log(n/\epsilon))) $, $ d $ is the maximum degree of the graphs, and a graph is called $ \epsilon $-far from an $ a^* $-expander if one has to modify (add or delete) at least $ \epsilon d n $ of its edges to obtain an $ a^* $-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is $ O(d^2 n^{1/2} log(n/\epsilon)/(a^2 \epsilon^3)) $. This is a joint work with Christian Sohler.
Tue, 02/12/2008
14:30 		Paul Hunter (Oxford) Combinatorial Theory Seminar Add to calendar L3
Strategy Improvement for Parity Games: A combinatorial perspective
Parity games are simple two-player, infinite-move games particularly useful in Computer Science for modelling non-terminating reactive systems and recursive processes.  A longstanding open problem related to these games is whether the winner of a parity game can be decided in polynomial time.  One of the most promising algorithms to date is a strategy improvement algorithm of Voege and Jurdzinski, however no good bounds are known on its running time. In this talk I will discuss how the problem of finding a winner in a parity game can be reduced to the problem of locally finding a global sink on an acyclic unique sink oriented hypercube.  As a consequence, we can improve (albeit only marginally) the bounds of the strategy improvement algorithm. This talk is similar to one I presented at the InfoSys seminar in the Computing Laboratory in October.

For any corrections/updates to these listings, please contact seminars [-at-] maths [dot] ox [dot] ac [dot] uk.

Syndicate content