Invited speakers

• Martin Grötschel  (ZIB and TU Berlin)
• Pavol Hell  (Simon Fraser)
• Richard M. Karp  (Berkeley)
• Yoshiharu Kohayakawa  (São Paulo)
• Bruce Reed  (McGill)
• Carsten Thomassen  (Denmark)

Abstracts of invited talks

Telecommunication, graphs, and combinatorial optimization

Martin Grötschel  (ZIB and TU Berlin)

ABSTRACT:  Telecommunication is an area that offers an almost infinite number of opportunities for mathematics. There are, in particular, very many challenging tasks for discrete mathematicians. Some examples: design of devices and network components, location planning, design of network topologies, network capacity planning, traffic routing, interference reduction.

This talk will survey some of the discrete optimization problems that arise in telecommunication and will focus on issues in which graph theory and combinatorial optimization play a particular role. Among these problems are issues such as the design of low cost telecommunication networks that provide sufficient capacity to serve a given demand, satisfy various technical side constraints, and survive certain failure situations. Another very important problem is the channel assignment problem that arises in various versions in mobile communication – depending on the type of technology employed.

This talk is based on work of the telecommunication research group at Konrad-Zuse-Zentrum, Berlin. Most of the examples discussed come from joint projects with various telecommunication companies.

From colouring to constraint satisfaction

Pavol Hell  (Simon Fraser)

ABSTRACT:  I will describe a general problem set-up which contains graph colourings, as well as homomorphisms, and general constraint satisfaction problems. The main focus will be on classifying the complexity of these problems according to the structure of the fixed target template. Emphasis will be on the so called "full" problems which correspond to homomorphisms of structures with coloured substructures.

Fair bandwidth allocation

Richard M. Karp  (Berkeley)

ABSTRACT:  A fundamental goal of Internet congestion control is to ensure fairness by selectively dropping packets from flows that are receiving more than their fair share of bandwidth. The most effective known algorithms for detecting and selectively dropping high-rate flows at a router are based on random hashing or random sampling of packets and give only probabilistic guarantees. The known deterministic algorithms either require excessive storage or fail to guarantee fairness. In a simplified theoretical setting we show that the detection and selective dropping of high-rate flows can be accomplished deterministically without maintaining an excessive amount of state. Given an arriving stream of packets, each labeled with the name of its flow, our algorithm drops the minimum number of packets required to guarantee that, in every consecutive subsequence of the output stream, no flow has significantly more than its fair share of the packets.

The main results of the paper are tight bounds on the worst-case storage requirement of this algorithm. These bounds follow from the analysis of a nondeterministic process that generates a sequence of multisets S(0), S(1), ...  The process depends on two positive integer parameters, B and d, with B greater than d. S(0) is the empty set, and S(t+1) is obtained nondeterministically from S(t) by the following sequence of steps: Adjoin the element 0 to S(t); increment at most one element of the resulting multiset by 1; decrement every element by 1; finally, delete all elements outside the range [1,B]. The maximum storage requirement of the algorithm is exactly the maximum cardinality of a multiset that can be generated by this process, and the maximum storage requirement after t packets have been placed in the output stream is exactly the maximum possible cardinality of S(t).

On a theorem of Luczak

Yoshiharu Kohayakawa  (São Paulo) 

ABSTRACT:  For graphs  L1, . . . , Lk,  the Ramsey number R(L1, . . . , Lk) is the minimum integer N such that, in any colouring of the edges of the complete graph on N vertices by k colours, there exists a colour i for which the corresponding colour class contains Li as a subgraph. 

Let Cn denote the cycle of length n.  In 1973, Bondy and Erdös conjectured that if n is odd, then R(Cn,Cn,Cn) ≤ 4n–3, which would be best possible if true.  A great deal later, in 1999, a breakthrough was finally achieved by Luczak: he proved that R(Cn,Cn,Cn) = (4+o(1))n, where o(1) → 0 as n → ∞.  In this talk, we shall outline a proof for the sharp inequality R(Cn,Cn,Cn) ≤ 4n–3 for all large enough n.  This proof is heavily inspired on Luczak's proof, but gives the sharper result by exploiting certain stability results for extremal colourings.

Some recent related developments due to other authors will be discussed.

Joint work with M. Simonovits (Budapest) and J. Skokan (São Paulo).

Packings and coverings of odd cycles

Bruce Reed  (McGill)

ABSTRACT:  We discuss the relationship between the maximum size of a set of vertex disjoint odd cycles and the minimum number of vertices whose removal leaves the graph bipartite for various special classes of graphs.

On the number of colorings of a graph

Carsten Thomassen  (Technical University of Denmark)

ABSTRACT:  The chromatic polynomial P(G,k) of a graph G is the number of colorings of G with k available colors. The chromatic polynomial was introduced by Birkhoff in 1912 in order to study the 4-Color Problem. Although the chromatic polynomial has not been very successful for coloring problems, it has been studied for several other reasons, primarily by mathematicians but also by physicists. In this talk, some basic properties of the chromatic polynomial will be discussed. Special attention will be given to the case k=5 for graphs on a fixed surface, and the case k=3 for triangle-free planar graphs.