Doccourse 2004: Program for predoctoral and doctoral students

Andrea Hoffkamp hoffkamp at
Wed Jun 4 16:22:56 PDT 2003

Call for Applications

                    DOCCOURSE BERLIN-PRAGUE 2004
          Programme for pre-doctoral and doctoral students in
          ===== Combinatorics, Geometry, and Computation ====
                        January-June 2004
       (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.

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>, J. Matousek (Charles University, Prague,
matousek <at>, and J. Nesetril (Charles University,
Prague, nesetril <at>

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

either electronically (preferable), in an open format
(Postscript, PDF), to "matousek" at the domain "",

or by mail to

Jiri Matousek
Department of Applied Mathematics
Malostranske nam. 25
118 00 Praha 1
Czech Republic

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


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


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
Guenter M. Ziegler (TU Berlin)
Berlin, April - May 2004


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


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

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list