Time table (updated on Dec. 5) >>Program (pdf)
Titles (updated on Dec. 5)
Abstracts
December 17 (Wed)
14:00-15:30, December 17 (Wed)
Bjarne Toft (University of Southern Denmark, Denmark)
The Game of Hex
The board game HEX was invented independently by the Danish designer and
poet Piet Hein and the American mathematician John Forbes Nash (who won
the Nobel prize in economics in 1994). There has in recent years been
detailed studies related to the history and theory of the game in
particular by Thomas Maarup at the University of Southern Denmark and by
Ryan Hayward and Jack van Rijswijck at the University of Alberta in
Canada. In this lecture I shall focus on HEX's relations to the history of
graph theory and combinatorics , the interesting theoretical properties of
the game, some unsolved problems relating to HEX, but also on the general
achievements of Piet Hein. A new simple proof of the fact that not both
players can lose in a game of HEX will be presented. The statement that
this fact is equivalent to Brouwer's Fix Point Theorem will be discussed.
16:00-17:30, December 17 (Wed)
Mikkel Thorup (AT&T Labs-Research, USA)
Approximate Distance Oracles for Planar DiGraphs and Avoiding Obstacles in the Euclidean Plane
We show how to preprocessed a planar digraph in near-linear
time, producing a simple near-linear space oracle that can answer
reachability queries in constant time. The oracle can be distributed as
an O(log n) space label for each vertex and then we can determine
if one vertex can reach another considering their two labels only.
The approach generalizes to a near-linear space approximate
distances oracle for a weighted planar digraph. With weights
from {0,...,N}, it approximates distances within a factor
(1+a) in O(loglog (nN)+1/a) time. Our scheme can be
extended to find and route along correspondingly short dipaths.
Next we extend our approach provide approximate distances avoiding
obstacles in the Euclidean plane. The points queried can be at arbitrary
positions.
December 18 (Thu)
9:30-10:30, December 18 (Thu)
R. Ravi (Carnegie Mellon University, USA)
Iterative Methods in Combinatorial Optimization
In this talk, I will describe a simple iterative method for
proving a variety of results in combinatorial optimization. It
is inspired by Jain's iterative rounding method for designing
approximation algorithms for survivable network design
problems, and augmented with a relaxation idea in the work of
Lau, Naor, Salvatipour and Singh in their work on designing an
approximation algorithm for its degree bounded version. Its
application was further refined in recent work of Bansal,
Khandekar and Nagarajan on degree-bounded directed network
design.
In this talk, I will describe its application to showing the
integrality of Edmonds's characterization of the spanning tree
polyhedron and then extend the argument to show a simpler proof
of the Lau-Singh approximation algorithm for its degree
constrained versions. I will conclude by showing how Jain's
original proof can be much simplified by the new perspective,
by unifying its treatment with that for the STSP problem.
This talk describes work of all the above authors interpreted
in collaboration with Lau, Nagarajan and Singh.
11:00-12:30, December 18 (Thu)
Carsten Thomassen (Technical University of Denmark, Denmark)
On the Number of Spanning Trees, Orientations, and Cycles
(abstract in pdf)
One of the most fundamental properties of a connected graph is the existence of a spanning tree.
Also the number $\tau(G)$ of spanning trees is an important graph invariant.
It plays a crucial role in Kirchhoff's classical theory of electrical networks,
for example in computing driving point resistances.
More recently, $\tau(G)$ is one of the values of the Tutte polynomial
which now plays a central role in statistical mechanics. So are $a(G)$,
the number of acyclic orientations, and $c(G)$,
the number of orientations in which every edge is in a directed cycle.
As a first step towards convexity properties of the Tutte polynomial,
Merino and Welsh conjectured that $\tau(G) \leq max\{a(G),c(G)\}$
for every loopless and bridgeless multigraph $G$.
We shall here prove that $\tau(G) \leq c(G)$ for all loopless and bridgeless multigraphs
with $n$ vertices and at least $4n$ edges and
that $\tau(G) \leq a(G)$ for all loopless multigraphs with $n$ vertices and at most $16n/15$ edges.
We also verify the conjecture for cubic graphs (which are in between these two bounds).
14:00-15:30, December 18 (Thu)
Bojan Mohar (Simon Fraser University, Canada )
Coloring-flow Duality for Graphs on Surfaces
There is a nice duality relation between colorings of a planar
graph and nowhere-zero flows in its geometric dual. In this lecture we
shall learn to what extent this duality can be extended to graphs
embedded in other surfaces.
16:00-17:30, December 18 (Thu)
Mikkel Thorup (AT&T Labs-Research, USA)
Efficient Cuts via Greedy Tree Packing
We study a simple greedy tree packing of a graph and use it to derive
better algorithms for fully-dynamic min-cut and for the static k-way
cut problem.
A greedy tree packing is a sequence of spanning tree where each new
tree is a minimum spanning tree with respect to the edge loads from
the previous trees, that is, the load of an edge is the number of
times it has been used by the previous trees.
A minimum k-way cut is a minimum set of edges whose removal splits
the graph in k components. A min-cut is a minimum 2-way cut.
If the (unknown) edge connectivity of the graph is c, we show that if
we pack c^7*log^3 m trees, then some min-cut is crossed exactly once
by some tree. This leads to the best fully-dynamic min-cut algorithm
(presented at STOC'01)
If we pack k^3*log n trees, then every minimum k-way cut is crossed
2k-2 times by some tree. This leads to the best determinstic algorithm
for k-way cut (to be presented at STOC'08)
December 19 (Fri)
9:30-10:30, December 19 (Fri)
Magnus Halldorsson (Reykjavik University, Iceland)
Word-representable Graphs
A graph G=(V,E) is said to be representable if there exists a
word over the alphabet V such that u and v are adjacent if and only if
the occurrences of u and v in the word alternate.
We give an alternative representation of these graphs as those that
can be oriented to satisfy a certain semi-transitivity property.
This allows us to characterize the types of graphs that are representable, in particular
showing that they include 3-colorable graphs.
We also obtain bounds on the size of the word-representation,
in that n occurrences of each letter suffice to represent any representable
graph, while n/2 may be necessary.
It follows that deciding if a graph is representable is in NP, whereas
it is still open if it is in P.
This is joint work with Artem Pyatkin (Sobolev Institute of Mathematics)
and Sergey Kitaev (Reykjavik University).
11:00-12:30, December 19 (Fri)
Bojan Mohar (Technical University of Denmark, Denmark)
Finding Shortest Cycles with Restricted Homotopy
It is easy to find a shortest cycle in a graph. One way for
this task is to employ a breadth-first search from each vertex and
record a shortest cycle found in each search. A similar approach works
if one wants to obtain a shortest non-contractible cycle in an embedded
graph since non-contractible cycles satisfy Thomassen's 3-path property.
In this lecture we shall review a variety of problems asking for a
shortest cycle that satisfies certain properties.
14:00-15:30, December 19 (Fri)
Robin Thomas (Georgia Institute of Technology, USA)
Pfaffian Orientations of Graphs
(abstract in pdf)
An orientation of a graph $G$ is {\sl Pfaffian} if every even cycle $C$
such that $G\backslash V(C)$ has a perfect matching has an odd number of edges
directed in either direction of the cycle.
Pfaffian orientations
were introduced by Kasteleyn, Fisher and Temperley in the 1960s.
Their significance stems from the fact that if a graph has one,
then the number of perfect matchings (a.k.a.\ the dimer problem)
can be computed in polynomial time.
The question of which bipartite graphs have Pfaffian orientations
is equivalent to many other problems of interest, such as a permanent
problem of P\'olya, the even directed cycle problem, or the sign-nonsingular
matrix problem for square matrices. These problems are now reasonably
well-understood. We will survey their equivalence and their solution.
On the other hand, it is not known how to efficiently test if a general
graph is Pfaffian, but there are some interesting connections with
crossing numbers, tree-width of directed graphs, signs of edge-colorings
of regular graphs, and even the Four-Color Theorem.
We will explore these connections and discuss the prospects for
characterizing graphs that have a Pfaffian orientation.
See also http://www.math.gatech.edu/~thomas/SLIDE/FALLSCHOOL/
16:00-17:30, December 19 (Fri)
Carsten Thomassen (Technical University of Denmark, Denmark)
Graph Decomposition
(abstract in pdf)
J\'anos Bar\'at and I made the following conjecture:
For every tree $T$, there is a natural number $k_T$ such that
every $k_T$-edge-connected graph of size divisible by $|E(T)|$
has an edge-decomposition into subgraphs each isomorphic to $T$.
The conjecture is trivial when $T$ has at most two edges.
When we made the conjecture we could not prove it for one single tree with three or more edges.
However, we showed that the conjecture holds
for the claw (the star with three edges) provided Tutte's $3$-flow conjecture is true.
A year ago I verified the conjecture for one tree.
Recently, I have verified it for a second tree.
December 21 (Sun)
9:30-10:00, December 21 (Sun)
Naoyuki Kamiyama (Kyoto University, Japan)
Independent Arborescences in Directed Graphs
Edmondsf theorem on arc-disjoint arborescences is one of the fundamental
min-max results in combinatorial optimization. In this talk, I first review
the extension of this result presented by N. Kamiyama, N. Katoh and A.
Takizawa, and the further extension presented by S. Fujishige. Then, I talk
about independent arborescences which are a vertex-disjoint analogue of
arc-disjoint arborescences. After I overview the known results about independent
arborescences, I show that some results can be extended in the same manner
as the arc-disjoint case. This is a joint work with A. Frank, S.
Fujishige, N. Katoh.
10:00-10:30, December 21 (Sun)
Takehiro Ito (Tohoku University, Japan)
Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
Assume that each vertex of a graph $G$ is assigned a nonnegative integer
weight and that $l$ and $u$ are integers such that $0 \le l \le u$. One
wishes to partition $G$ into connected components by deleting edges from $G$
so that the total weight of each component is at least $l$ and at most $u$.
Such an ``almost uniform'' partition is called an $(l,u)$-partition. We deal
with three problems to find an $(l,u)$-partition of a given graph: the
minimum partition problem is to find an $(l,u)$-partition with the minimum
number of components; the maximum partition problem is defined analogously;
and the $p$-partition problem is to find an $(l,u)$-partition with a given
number $p$ of components. All these problems are NP-hard even for
series-parallel graphs, but are solvable for paths in linear time and for
trees in polynomial time. In this paper, we give polynomial-time algorithms
to solve the three problems for trees, which are much simpler and faster
than the known algorithms. This is a joint work with T. Uno (NII), X. Zhou
(Tohoku U.) and T. Nishizeki (Tohoku U.).
11:00-12:30, December 21 (Sun)
Bjarne Toft (University of Southern Denmark, Denmark)
Graph Coloring Problems Revisited
Fourteen years ago, in December 1994, the book [T.R. Jensen & B. Toft,
Graph Coloring Problems, Wiley Interscience 1995] appeared. It received
good reviews, and up to now between 300 and 400 papers have it as a
reference. Originally it was the intention to keep the book up to date
using the internet, but this unfortunately did not work out properly. The
talk will express thoughts about the book in general, and about its
problems (in particular within the areas edge-colouring, Hadwiger's
Conjecture and critical graphs).
14:00-15:30, December 21 (Sun)
Robin Thomas (Georgia Institute of Technology, USA)
Pfaffian Orientations of Graphs
(abstract in pdf)
See December 19 (Fri)
16:00-17:30, December 21 (Sun)
Bruce Reed (McGill University, Canada)
Algorithms for Minor Containment
We discuss Robertson and Seymour's Seminal Algorithm for minor containment
and a recent faster algorithm.
December 22 (Sun)
9:30-10:30, December 22 (Mon)
Sang-il Oum (KAIST, Korea)
Survey on Rank-width and Clique-width
In this talk, I aim to talk about some highlights of developments on
rank-width of graphs. Rank-width (defined by Oum and Seymour) is one
of the width parameters of graphs, like tree-width. The study of rank-
width is motivated from clique-width defined earlier than rank-width.
Rank-width and clique-width are useful for some applications due to
the fact that many hard graph problems, including all graph problems
expressible by monadic second-order logic, can be solved in polynomial
time if the input graph is restricted to graphs of bounded rank-width.
I am planning to discuss the following: recognition algorithms for
rank-width<=k, relation to branch-width of binary matroids, well-
quasi-ordering theorem for graphs of rank-width<=k by graph pivot-
minors, and some conjectures motivated by Robertson and Seymour's
graph minors project.
11:00-12:30, December 22 (Mon)
Bruce Reed (McGill University, Canada)
Algorithms for Minor Containment
See December 21 (Sun)