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.
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.
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.
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.