DIMACS/DIMATIA REU 2007 – Prague Programme

Participants will be provided with office space in the seminar room S6. Computers with internet access are available. To connect your laptop, please contact wizards at kam dot mff dot cuni dot cz or in office 322.

The programme will be subject to frequent unexpected changes.

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