Monday, July 23


9:10  arrival in Prague, transfer to hotel

Tuesday, July 24


10:00  opening and welcome speeches

10:15  J. Nešetřil: Homomorphisms to the Pentagon

11:45  J. Kratochvíl: Locally bijective homomorphisms

13:00  lunch

Wednesday, July 25


10:00  J. Matoušek: Sums, products, and crossings

 We will investigate mainly the following question: If we
draw a given graph in the plane, what is the smallest number of edge crossings that we
have to make? We will also mention a remarkable connection of this problem to a
numbertheoretic question about sums and products.

12:30  lunch

Thursday, July 26


10:00  D. Kráľ: Chains and antichains

 We will present basic theorems on chains and antichains in
partially ordered sets. In particular, Dilworth's theorem on the number of chains
needed to cover the support set. Several applications will be presented.
Further problems to consider (in the form of exercises) on the topic
will be given at the end of the lecture.

12:00  lunch

Friday, July 27


10:00  M. Mareš: The surprises of random walks

 We will consider random walks on various graphs and study
their properties,
especially the average time of reaching a given vertex or of covering the
whole graph. This will turn out to be a nice tool for studying behavior
of algorithms and for proving existence of several surprising objects.

11:30  J. Fiala: Algorithms for geometric intersection graphs

 We will explore several classes of intersection graphs (disk
graphs, unit disk graphs, etc.) and approximate some graph parameters, e.g.
independence number and chromatic number, on these graph classes.

13:00  lunch

14:30  a tour of the National Gallery (J. Nešetřil)Make sure to be in front
of the university building in time.

Week from July 30 to August 3


 Midsummer Combinatorial
Workshop

 Talks start at 9am.

Weekend from August 3 to August 5


 Field Trip

Monday, August 6


10:00  M. Klazar: Counting lattice points in polytopes
(Ehrhart polynomials)

 I will explain a classical method in enumerative
combinatorics, based on geometric arguments, using which one
can show for many problems that
the function counting given objects or structures is a
polynomial. These objects may be magic squares, ways to exchange
some amount into coins of given denomination and others.

11:30  J. Foniok: Menelaus' Theorem and Céva's Theorem

 I will state and proof the two theorems about certain length
ratios in a triangle. These theorems have many consequences in elementary geometry,
e.g. the existence of a barycentre.

13:00  lunch
