DOCCOURSE BERLIN-PRAGUE 2004

Programme for pre-doctoral and doctoral students in

Combinatorics, Geometry, and Computation

January 1 - March 31 Prague, April 1 - June 30 Berlin

Supported by the the European Graduate Program "COMBINATORICS, GEOMETRY, AND COMPUTATION", by the EU network COMBSTRU, and by DIMATIA Prague.

Call for applications

The European Graduate Program "COMBINATORICS, GEOMETRY, AND COMPUTATION" in Berlin and DIMATIA Centre at the Charles University Prague offer a one-semester study programme for PhD. students and students preparing to enter a PhD. programme in areas: Combinatorics and Graph Theory; Discrete and Computational Geometry; Combinatorial Optimization; Discrete Structures.

The programme in 2004 includes four research-oriented courses and a project; see the schedule, speakers (including guests P. Cameron and M. Sharir), and topics below.

The contact persons and the leaders of the programme are H. Alt (FU Berlin, alt [at] inf.fu-berlin.de), J. Matousek (Charles University, Prague, matousek [at] kam.mff.cuni.cz), and J. Nesetril (Charles University, Prague, nesetril [at] kam.mff.cuni.cz).

A limited number of scholarships of approximately EUR 1000/month are available for students with a diploma or master degree in a field related to the topics of the programme (mathematics, computer science). Advanced diploma or master students can be considered as well if a feasible arrangement with their home institutions can be made. Students wishing to participate in the programme using other financial resources are also encouraged to apply; the acceptance will be limited by the capacity of the courses.

The accepted students are expected to participate in all of the programme (January - March in Prague, April - June in Berlin).

Pre-doctoral students may prepare a PhD. research proposal during the programme, and after the programme there is a possibility of applying for a PhD. scholarship at one of the institutions of the COMBSTRU network or at the graduate programme CGC.

The language of the programme is English. The programme is open to applicants of all nationalities.

Applications with curriculum vitae, copies of certificates, thesis, areas of interest, and a letter of recommendation from the thesis advisor should be sent

Application deadlines are July 15, 2003, and September 30, 2003. Applicants are notified of results about one month after the respective deadline. This stepwise procedure allows students to obtain a commitment at an early stage, while leaving some options also for later applicants.

COURSES

Courses will be held two days a week, for a five-week period. Every day includes about 3 hours of lectures, exercises in groups, and a discussion of exercises.

Permutation groups, structures, and polynomials

Peter Cameron (London)
Prague, January - February 2004

Abstract:

The course will begin by discussing the basic concepts of permutation groups, both finite and infinite. Many examples of infinite permutation groups are obtained from homogeneous or omega-categorical structures, and the course will describe some of these. Finite permutation groups occur in enumeration theory; the cycle index of a permutation group has some connections with the Tutte polynomial of a matroid. The theory of species relates these two areas, studying an infinite structure by its finite subsets.

Arrangements in Computational and Combinatorial Geometry

Micha Sharir (Tel Aviv)
Prague, January - February 2004

Abstract:

The course studies combinatorial and algorithmic problems related to arrangements of curves and surfaces in the plane and in higher dimensions. Arrangements arise in many applications, and have a rich combinatorial structure. The topics covered by the course include the study of substructures in arrangements, such as lower envelopes, single cells, zones, levels, and more; Davenport-Schinzel sequences; Algorithms for 2-dimensional arrangements; The Zone Theorem in higher dimensions; Randomized techniques in geometry; Incidences between points and curves; Geometric partitioning and range searching.

Convex Polytopes

Günter M. Ziegler (TU Berlin)
Berlin, April - May 2004

Abstract:

This will be a ``steep'' but hands-on introduction to the theory of convex polytopes and their combinatorial properties. This will start with an extensive discussion and analysis of examples. On this basis we will develop the fundamental combinatorial facts (face lattices, polarity). Then we concentrate on 3-dimensional polytopes (rather well-understood) and on 4-dimensional polytopes (active field of research). A survey of f-vector theory will lead us to discuss ``extremal'' polytopes.

Random generation and approximate counting

Volker Kaibel (TU Berlin)
Berlin, April - May 2004

Abstract:

The first part of the course will be an introduction to the theory of random walks for generating combinatorial objects randomly with a prescribed distribution. In particular, we will focus on methods for analyzing the speed of convergence of Markov chains on finite state spaces (like 'canonical paths' and 'coupling from the past').

In the second part, the tools developed in the first part will be exploited in order to build algorithms for randomized approximate counting of combinatorial objects. Among the topics will be recent achievements such as the randomized approximation algorithm for computing the permanent, due to Jerrum, Sinclair and Vigoda (2001).

Maintained by: Jan Hubicka (hubicka@kam.ms.mff.cuni.cz)