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