Date:           Wed, 11 Feb 1998 17:11:11 MET
Reply-To:       bfelsner@inf.fu-berlin.de
From:           DMANET <dmanet@math.utwente.nl>
Subject:        Announcement for Summer School on Discrete Mathematics
To:             DMA-LIST@NIC.SURFNET.NL

Graduate Program "COMPUTATIONAL DISCRETE MATHEMATICS"
Graduiertenkolleg "ALGORITHMISCHE DISKRETE MATHEMATIK"

In connection with the Graduate Program "Computational Discrete Mathematics" (Graduiertenkolleg "Algorithmische Diskrete Mathematik"), a

Summer School
on
Discrete Mathematics

will be held from April 26 to April 30, 1998. The aim of the Summer School is to present new trends and ideas in discrete mathematics and to give students working in this fields or closely related areas, the opportunity to meet other students with common research interests and career goals. We assume only basic knowledge of discrete mathematics.

The program will be presented by the following four lecturers: (for a preliminary program and abstracts see below)

Each lecturer will present a lecture of two hours in length in English. In addition, exercises will be handed out, solved in small groups and discussed later in special sessions.

The Summer School will take place in Chorin, a picturesque site near the ruins of an old monastery about 50 km northeast of Berlin. We will travel together from Berlin on 26 April in the afternoon and back on 30 April in the morning. The costs per participant are DM 150,00 and include transportation between Chorin and Berlin and full board during the Summer School. The number of participants is limited to 30. Applications with a short curriculum vitae (incl. scientific background) and a short letter of recommendation from a university faculty member should be sent to:

Prof. Dr. Hans Jürgen Prömel
Humboldt-Universitaet zu Berlin
Institut für Informatik
Unter den Linden 6,
D-10099 Berlin

The deadline for receipt of application materials is March 6, 1998.

Further information can be obtained from Bettina Felsner (phone: 030/838 75 104; e-mail: bfelsner@inf.fu-berlin.de).

Summer School "Discrete Mathematics", April 26-30, 1998 Preliminary program

Sunday April 26

ca. 15:00 Depature from Berlin to Chorin 18:30 Dinner; Introduction lecturers and participants

Monday April 27

8:30 Tom Trotter, Graphs, hypergraphs and partial Orders (lecture I)

We explore interconnections between these three discrete structures. Topics which link them include planar graphs, hamiltonian cycles and paths, graph and hypergraph coloring, on-line algorithms, intersection graphs, inclusion orders, random methods and ramsey theory.

10:30 Exercise I

12:30 Lunch

13:30 Continuation of Exercise I

14:30 Discussion of Exercise I

16:00 Johan Håstad, PCP and testing (lecture II)

We discuss and analyze some of the protocols for testing various basic properties. The kind of properties we test are low degree tests and some types of consistency. Apart from being of inherent interest these tests are crucial for the strong inapproximability results obtained through the PCP machinery.

18:00 Exercise II

19:00 Dinner

20:00 Continuation of Exercise II

Thuesday April 28

9:00 Discussion of Exercise II

10:00 Bela Bollobas, Judicious partitions of graphs and hypergraphs (lecture III)

Many classical problems in graph theory demand that a certain quantity be maximized or minimized. For instance, given a graph G, the Max Cut problem asks for the largest bipartite subgraph of G. In the lectures we shall consider problems in which several quantities must be minimized or maximized simul- taneously. For example, given m >= 1, what is the smallest integer, f(m), such that every graph with m edges has a bipar- tition in which each vertex class contains at most f(m) edges? Or, for hypergraphs, is it true that, for every r >= 1, the vertex set of every r-uniform hypergraph with m edges can be partitioned into r classes such that every class meets at least rm/(2r-1) edges? Problems of this type are in general more difficult, since the quantities are not usually independent. After a review of a good many related theorems, we shall present some recent results obtained with Alexander Scott, and pose numerous unsolved problems.

12:00 Exercise III

13:00 Lunch

14:00 Group Excursion

19:00 Dinner

20:00 Continuation of Exercise III

Wednesday April 29

9:00 Discussion of Exercise III

10:00 Victor Klee, Some unsolved problems in discrete geometry (lecture IV)

Discrete geometry is a rich source of problems that are close to the surface in the sense that they have immediate intuitive appeal, but which nevertheless have for many years withstood attempts at solution. Some of the speaker's favorites will be presented, along with indications of known partial results.

12:00 Exercise IV

13:00 Lunch

14:00 Continuation of Exercise IV

17:00 Discussion of Exercise IV

19:00 Dinner

Thursday April 30

ca. 8:30 Departure